Cookie Exchanges [ AtCoder Grand Contest 014 A ]

atcoder.jp

問題

最初、3人はクッキーを A,B,C 個持っている。
操作を1回おこなうごとに、それぞれの人は「他の2人が持っているクッキーの個数の平均値」を同時に受け取る。

いずれかの人のクッキーが奇数になるまで操作をおこなうとき、操作は何回可能か。
無限回可能なら、-1を出力せよ。

考察

A <= B <= C とします。
このとき、最大値と最小値の差の絶対値は |C-A| です。
操作を1回おこなうと、A,B,C は

・(A+B)/2, (A+C)/2, (B+C)/2

となり、最大値と最小値の差の絶対値は |(C-A)/2| になります。

つまり、操作を1回おこなうごとに「最大値と最小値の差の絶対値」が半分になります。

操作はいずれかの値が奇数になったときに不可能になります。
よって、考えうる限り最も操作回数が多くなる差（536870912 = 2^29）の場合でも、高々29回の操作で差を奇数にできるので、愚直にシミュレーションすればよいです。

以下のプログラムでは、操作をシミュレーションするたびにそれぞれの値が奇数になったかどうか判定し、もし操作回数が35回を超えるような場合には -1 を出力しています。

コード

void solve (FastScanner in, PrintWriter out) {
	
	double[] abc = {in.nextDouble(), in.nextDouble(), in.nextDouble()};

	for (int i=0; i<35; i++) {
		
		if (isEnd(abc) == true) {
			out.println(i);
			return;
		}
		
		double a = (abc[1]+abc[2])/2;
		double b = (abc[0]+abc[2])/2;
		double c = (abc[0]+abc[1])/2;
		abc[0]=a; abc[1]=b; abc[2] = c;
		
	}
	
	out.println(-1);

}

static boolean isEnd (double[] ar) {
	for (int i=0; i<3; i++) {
		if (ar[i]%2 != 0) return true;
	}
	return false;
}