ICPC国内予選2008 解答
Eではspaghetti source(http://www.prefield.com/algorithm/index.html)の幾何ライブラリを拝借しています。
A
#include <iostream> using namespace std; main() { int n, m; while (cin >> n >> m, n || m) { int t[n], h[m], tsum = 0, hsum = 0; for (int i = 0; i < n; i++) cin >> t[i], tsum += t[i]; for (int i = 0; i < m; i++) cin >> h[i], hsum += h[i]; int MIN = INT_MAX, _t, _h; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (tsum - t[i] + h[j] == hsum - h[j] + t[i] && MIN > t[i] + h[j]) MIN = t[i] + h[j], _t = t[i], _h = h[j]; if (MIN == INT_MAX) cout << -1 << endl; else cout << _t << " " << _h << endl; } }
B
#include <iostream> #include <vector> #define MAX 300000 using namespace std; int p[MAX + 1] = {0}; vector<int> v; main() { for (int i = 6; i <= MAX; i++) { if ((i % 7 == 1 || i % 7 == 6) && !p[i]) { v.push_back(i); for (int j = i + i; j <= MAX; j += i) { p[j] = 1; } } } int n; while (cin >> n, n != 1) { cout << n << ":"; for (int i = 0; i < v.size() && v[i] <= n; i++) { if (n % v[i] == 0) { cout << " " << v[i]; } } cout << endl; } }
C
#include <iostream> using namespace std; int P, Q, R; typedef pair<int, int> result; result formula (const string &s, int p) { if (isdigit(s[p])) return result(s[p] - '0', p + 1); if (isalpha(s[p])) return result(s[p] == 'P' ? P : s[p] == 'Q' ? Q : R, p + 1); if (s[p] == '-') { result res = formula(s, p + 1); return result(2 - res.first, res.second); } if (s[p] == '(') { result left = formula(s, p + 1); char op = s[left.second]; result right = formula(s, left.second + 1); if (op == '*') { return result(min(left.first, right.first), right.second + 1); } else { return result(max(left.first, right.first), right.second + 1); } } } main() { string line; while (cin >> line, line != ".") { int sum = 0; for (P = 0; P <= 2; P++) for (Q = 0; Q <= 2; Q++) for (R = 0; R <= 2; R++) if (formula(line, 0).first == 2) sum++; cout << sum << endl; } }
D
#include <iostream> #include <queue> using namespace std; int dp[30][30][4], table[30][30], w, h, cost[4]; int dr[4] = {0, 1, 0, -1}; int dc[4] = {1, 0, -1, 0}; struct S { int r, c, state, w; bool operator < (const S &s) const { return w > s.w; } int &ref() { return dp[r][c][state]; } int &op() { return table[r][c]; } }; inline bool valid (int r, int c) { return 0 <= r && r < h && 0 <= c && c < w; } main() { while (cin >> w >> h, w || h) { for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> table[i][j]; for (int i = 0; i < 4; i++) cin >> cost[i]; memset(dp, -1, sizeof(dp)); S init; init.ref() = init.r = init.c = init.state = init.w = 0; priority_queue<S> que; que.push(init); while (1) { S here = que.top(); que.pop(); if (here.r == h - 1 && here.c == w - 1) { cout << here.w << endl; break; } for (int i = 0; i <= 3; i++) { S there = here; there.state = (there.state + i) % 4; there.r += dr[there.state]; there.c += dc[there.state]; if (!valid(there.r, there.c)) continue; if (here.op() != i) there.w += cost[i]; if (there.ref() == -1 || there.w < there.ref()) { there.ref() = there.w; que.push(there); } } } } }
E
#include <iostream> #include <vector> #include <complex> #define sq(x) ((x)*(x)) using namespace std; const double EPS = 1e-6; typedef complex<double> P; double cross(const P &a, const P &b) { return imag(conj(a) * b); } double dot (const P &a, const P &b) { return real(conj(a) * b); } struct L : public vector<P> { L(const P &a, const P &b) { push_back(a); push_back(b); } }; int ccw(P a, P b, P c) { b -= a, c -= a; if (cross(b, c) > 0) return +1; if (cross(b, c) < 0) return -1; if (dot(b, c) < 0) return +2; if (norm(b) < norm(c)) return -2; return 0; } bool intersectSS (const L &s, const L &t) { return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 && ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0; } bool intersectSP (const L &s, const P &p) { return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; } P projection(const L &l, const P &p) { double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]); return l[0] + t * (l[0] - l[1]); } double distanceSP(const L &s, const P &p) { const P r = projection(s, p); if (intersectSP(s, r)) return abs(r - p); return min(abs(s[0] - p), abs(s[1] - p)); } double distanceSS(const L &s, const L &t) { if (intersectSS(s, t)) return 0; return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])), min(distanceSP(t, s[0]), distanceSP(t, s[1]))); } main() { int N; while (cin >> N, N) { double sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; L course(P(sx, sy), P(ex, ey)); double MINTMP = 1e50; for (int i = 0; i < N; i++) { double minx, miny, maxx, maxy, h; cin >> minx >> miny >> maxx >> maxy >> h; // 包含判定 if (minx < min(sx, ex) && max(sx, ex) < maxx && miny < min(sy, ey) && max(sy, ey) < maxy) MINTMP = 0; vector<L> lines; lines.push_back(L(P(maxx, miny), P(maxx, maxy))); lines.push_back(L(P(minx, maxy), P(maxx, maxy))); lines.push_back(L(P(minx, maxy), P(minx, miny))); lines.push_back(L(P(minx, miny), P(maxx, miny))); double MIN = 1e50; for (int j = 0; j < 4; j++) { MIN <?= distanceSS(course, lines[j]); // 交差判定 if (intersectSS(course, lines[j])) MINTMP = 0; } MINTMP <?= MIN > h ? (sq(h) + sq(MIN)) / (2 * h) : MIN; } printf("%.4lf\n", MINTMP); } }