読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}