FizzBuzz(AOJ No.0221), Prime Quadruplet(AOJ No.0222), Stray Twins(AOJ No.0223)

リポジトリ

FizzBuzz(AOJ No.0221)

m,n,とn個の発言内容が与えられる。
1-mのIDが振られたm人がFizzBuzzを1からnまで順番に行っていく。
間違ったことを言えばその人は脱落して、次の人は、間違ったところの次から始める。
発言する順番は1,2,...,m,1,2...という輪環の順(脱落している人は飛ばされる)
nまで順番に発言したときの、残留プレイヤーのIDを出力する。
ただし、プレイヤーが一人になった時点で終了(それ以降の発言は無かったものとする)
制約

コード

import java.util.*;
public class aoj0221 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while (true) {
			int m = stdin.nextInt(), n = stdin.nextInt();
			if ((m|n) == 0) break;
			List<Integer> p = new LinkedList<Integer>();
			for (int i = 1; i <= m; ++i) p.add(i);
			int pi = 0;
			for (int i = 1; i <= n; ++i) {
				String l = stdin.next();
				if (p.size() == 1) continue;
				String a = i % 15 == 0 ? "FizzBuzz" : i % 3 == 0 ? "Fizz" : i % 5 == 0 ? "Buzz" : i+"";
				if (a.equals(l)) { 
					pi = (pi + 1) % p.size();
				} else {
					p.remove(pi); pi = pi % p.size(); 
				}
			}
			StringBuilder sb = new StringBuilder();
			for (int x : p) sb.append(" " + x);
			System.out.println(sb.substring(1));
		}
	}
}

Prime Quadruplet(AOJ No.0222)

nが与えられ、

• a+8 < n+1,
• a, a+2, a+6, a+8は全て素数

を満たす、最大のa+8を求める。
制約

コード

import java.util.*;
public class aoj0222 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 10000000;
	static boolean[] p = sieve(N + 1);
	public static void main(String[] args) {
		while (true) {
			int n = stdin.nextInt();
			if (n == 0) break;
			while (!(p[n] && p[n-2] && p[n-6] && p[n-8])) n--;
			System.out.println(n);
		}
	}
	public static final boolean[] sieve(int n){
		boolean[] ret = new boolean[n]; Arrays.fill(ret, true);
		ret[0] = ret[1] = false;
		for(int i = 2; i*i < n; ++i)
			if(ret[i]) for(int j = i*i; j < n; j+=i) ret[j] = false;
		return ret;
	}
}

Stray Twins(AOJ No.0223)

Y 行 X 列の(移動可 or 不可を示す)マップと、A,B二人の初期座標(1はじまり)が与えられる。
A, は4近傍に移動できて、BはAの逆方向に移動する。
移動不可のマップに進もうとする場合は、その場にとどまる。
最低、何回移動すると、A, Bは同じ座標にたどり着くかを答える。
100回以上になるようならNAと答える。
制約
0 < X,Y < 51

コード

幅優先

import java.util.*;
public class aoj0223 {
	static final Scanner stdin = new Scanner(System.in);
	static final int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, D = 4;
	static class T {
		int x1, y1, x2, y2, cost;
		T(int x1, int y1, int x2, int y2, int cost) {
			this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; this.cost = cost;
		}
	}
	public static void main(String[] args) {
		while (true) {
			int w = stdin.nextInt(), h = stdin.nextInt();
			if ((w|h) == 0) break;
			boolean map[][] = new boolean[h+2][w+2], visited[][][][] = new boolean[h+2][w+2][h+2][w+2];
			T p = new T(stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), stdin.nextInt(), 0);
			for (int i = 1; i <= h; ++i) for (int j = 1; j <= w; ++j) map[i][j] = stdin.nextInt() == 0;
			Queue<T> q = new LinkedList<T>();
			q.add(p);
			String ans = "NA";
			visited[p.y1][p.x1][p.y2][p.x2] = true;
			while (!q.isEmpty()) {
				T t = q.poll();
				if (t.cost > 100) continue;
				if (t.x1 == t.x2 && t.y1 == t.y2) { ans = t.cost + ""; break; }
				for (int i = 0; i < D; ++i) {
					T n = new T(t.x1 + dx[i], t.y1 + dy[i], t.x2 + dx[(i+2)%D], t.y2 + dy[(i+2)%D], t.cost + 1);
					if (!map[n.y1][n.x1]) { n.x1 = t.x1; n.y1 = t.y1; }
					if (!map[n.y2][n.x2]) { n.x2 = t.x2; n.y2 = t.y2; }
					if (!visited[n.y1][n.x1][n.y2][n.x2]) { 
						q.offer(n); 
						visited[n.y1][n.x1][n.y2][n.x2] = true;
					}
				}
			}
			System.out.println(ans);
		}
	}
}