ARC 072 D問題 Alice&Brown
解説
まずこのようなゲーム系の問題は終了時から遡って考えていきます。 そこでゲームが終了する場面を考えてみると
(x, y) = (0, 0), (1, 0), (0, 1),(1, 1)
この4通りぐらいは自分で見つけることができるかと思います。
次にx, yが0~5の6x6の表を書いてみることにします。
そのマスには(x, y)の場面が回ってきた場合に負けならばL, 勝ちならばWとします。
するとあるマスからあるマスへはy=-2xかy=2x上のマスに遷移することはゲームのルールからわかります。
それでもし遷移できる箇所にLのマスがあれば勝つことができ、もしWしかならば負けということになります。(Wの先にはLがあるはずなので)
したがってこの法則に従って表を埋めていくと
|x-y| <= 1 => Brown
|x-y| >= 2 => Alice
がわかるかと思います。
コード
#include <iostream> using namespace std; int main(void){ long long x, y; cin >> x >> y; if(abs(x-y) <= 1){ cout << "Brown" << endl; }else{ cout << "Alice" << endl; } return 0; }