AOJ 0198, 0147, 0122, 0177
AOJ 0198
ものすごくめんどくさそうだと思っていたが実装に気をつければそうでもなかった.
おなじ色の面をみつけて, まわりの4 面を回転させて一致するかを見ればOK.
#include <cstdio> #include <string> using namespace std; int rot[6][4] = {{2, 4, 3, 1}, {2, 0, 3, 5}, {5, 4, 0, 1}, {0, 4, 5, 1}, {2, 5, 3, 0}, {3, 4, 2, 1}}; string board[30][6]; bool same(int a, int b) { for (int i = 0; i < 6; i++){ for (int j = 0; j < 6; j++){ if (board[a][i] != board[b][j]) continue; for (int dx = 0; dx < 4; dx++){ bool same = true; for (int k = 0; k < 4; k++){ if (board[a][rot[i][(k + dx) % 4]] != board[b][rot[j][k]]) same = false; } if (same) return (true); } } } return (false); } int main() { int n; while (scanf("%d", &n) && n){ int ct = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < 6; j++){ char tmp[64]; scanf("%s", tmp); board[i][j] = tmp; } bool ok = true; for (int j = 0; j < i; j++) if (same(i, j)) ok = false; ct += ok; } printf("%d\n", n - ct); } }
0147
問題文にかかれているようにシミュレーションをすればよい. ルパン4 世のほうが難しいと思うなあ.
#include <cstdio> #include <queue> #include <cstring> using namespace std; int main() { int n; int ans[100], intime[100]; int chair[17]; queue<int> q; memset(chair, -1, sizeof(chair)); int time = 0; while (1){ if (time % 5 == 0) q.push(time / 5); for (int i = 0; i < 17; i++){ int y = chair[i]; if (y == -1) continue; if (time - intime[y] == 17 * (y % 2) + 3 * (y % 3) + 19) chair[i] = -1; } rep:; if (q.size() > 0){ int x = q.front(); int num; num = 2 + 3 * (x % 5 == 1); for (int i = 0; i <= 17 - num; i++){ bool ok = true; for (int j = i; j < i + num; j++) if (chair[j] != -1) ok = false; if (ok){ intime[x] = time; ans[x] = time - x * 5; if (x == 99) goto end; q.pop(); for (int j = i; j < i + num; j++) chair[j] = x; goto rep; } } } time++; } end:; while (~scanf("%d", &n)) printf("%d\n", ans[n]); return (0); }
0122
ぴょんきちは閉路内をぐるぐるできないとダメだと思っていて問題をinf 倍難しくしていました.
#include <cstdio> #include <queue> #include <algorithm> using namespace std; struct Event { int ty, tx; int t; Event(){} Event(int ty, int tx, int t) : ty(ty), tx(tx), t(t){} }; bool reach[16][16][16]; int main() { int sy, sx; int ty[10], tx[10]; int n; int dx[] = {-1, 0, 1, -2, 2, -2, 2, -2, 2, -1, 0, 1}; int dy[] = {2, 2, 2, 1, 1, 0, 0, -1, -1, -2, -2, -2}; while (scanf("%d %d", &sx, &sy) && sy){ scanf("%d", &n); if (n == 0) puts("NA"); for (int t = 0; t < n; t++){ scanf("%d %d", tx + t, ty + t); } queue<Event> q; bool flag = false; for (q.push(Event(sy, sx, 0)); q.size(); q.pop()){ Event x = q.front(); if (x.t == n){ puts("OK"); flag = 1; break; } for (int i = 0; i < 12; i++){ int ny = x.ty + dy[i], nx = x.tx + dx[i]; if (ny < 0 || ny > 9 || nx < 0 || nx > 9) continue; if (abs(ny - ty[x.t]) <= 1 && abs(nx - tx[x.t]) <= 1){ q.push(Event(ny, nx, x.t + 1)); } } } if (!flag) puts("NA"); } return (0); }
0177
知識がなさすぎて緯度・経度から幾何に落とせませんでした...(公式に頼るクズ
#include <cstdio> #include <cmath> using namespace std; int main() { double a, b, c, d; while (scanf("%lf %lf %lf %lf", &a, &b, &c, &d) && b >= -0.5){ if (b > 180) b = b - 360; if (d > 180) d = d - 360; a = a * M_PI / 180; c = c * M_PI / 180; printf("%d\n", (int)round(6378.1 * acos(sin(a) * sin(c) + cos(a) * cos(c) * cos((d - b) * M_PI / 180)))); } return (0); }