BUET Inter-University Programming Contest - 2011 D, UVa-12427 : Donkey of the Sultan

UVa その他のコンテスト

問題概要

山が3つあって、それぞれの山には石がx, y, z個置いてある。先手と後手の人が交互に以下のいずれかの処理をする。

  • xの石をひとつyの山に移す。
  • yの石をひとつzの山に移す。
  • zの石をひとつ取り除く。
  • xの石をひとつyの山に移し、zの石をひとつ取り除く。

操作ができなくなった方の負けである。
初期盤面の候補は(x,y,z) in [a1,a2]*[b1,b2]*[c1,c2]である(各変数は10^6以下)。後手勝ちの初期盤面はいくつあるか求める問題。

解法

実験してみると、xとzがともに偶数のとき後手の勝ちであることが分かる。こういうのを証明するには勝ちの状態から負けの状態に必ず行けて、負けの状態からは勝ちの状態にしか行けないことをしめせばよい。それは簡単。

acceptされたコード

計算量O(1)。

#include <cstdio>
using namespace std;

typedef long long int64;

int main(){
	int T;
	scanf("%d", &T);
	for(int i=0; i<T; i++){
		int64 A1, A2, B1, B2, C1, C2;
		scanf("%lld%lld%lld%lld%lld%lld", &A1, &A2, &B1, &B2, &C1, &C2);

		int64 ans = (B2 - B1 + 1) * (A2/2 + 1 - (A1?(A1-1)/2 + 1:0)) * (C2/2 + 1 - (C1?(C1-1)/2+1:0));
		printf("Case %d: %lld\n", i+1, ans);
	}

	return 0;
}