Codeforces #70 (div2) B "Easter Eggs"

問題:http://codeforces.com/contest/78/problem/B

卵の数が与えられる.卵は円形に並んでいて,それらを7色使って塗り替える.4つ連続した卵には同じ色を与えないとして,与えられた卵の数に置ける着色結果を求める.

全探索.n個の卵をそれぞれ見て行って,連続しない色で着色してゆくことを最初の卵から最後の卵まで行う.着色したときにその色で着色した卵の数を数えておいて,最後に全部の色を使ったかどうかで判定する.

public class B {
	public static void main(String[] args) {
		String[] c = { "R", "O", "Y", "G", "B", "I", "V" };
		n = new java.util.Scanner(System.in).nextInt();
		p = new int[n];
		f(0);
		for(int i = 0; i < n; ++i){
			System.out.print(c[p[i]-1]);
		}
		System.out.println();
	}

	static int n;
	static int[] p;
	static int[] bc = new int[8];

	static boolean f(int i) {
		if(i == n){
			for(int j = 1; j <= 7; ++j){
				if(bc[j] < 1){
					return false;
				}
			}
			return true;
		}
		boolean[] b = new boolean[8];
		for (int d = -3; d <= 3; ++d) {
			int j = i + d;
			if(j >= n){
				j -= n;
			}else if(j < 0){
				j += n;
			}
			b[p[j]] = true;
		}
		for (int j = 1; j <= 7; ++j) {
			if (!b[j]){
				p[i] = j;
				++bc[j];
				if(f(i + 1)){
					return true;
				}
				--bc[j];
				p[i] = 0;
			}
		}
		return false;
	}
}