AOJ-2189: Addition Game (足し算ゲーム)

問題概要

1000桁以下の数が与えられる。数が2桁以上の時、連続する2つの数字をその和で置き換える。数が1桁の時自分の番だと負け。先手が勝つか後手が勝つか判定する問題。

解法

実は戦略関係ない。なので適当に戦略を決め打ちしてシミュレーションしてやればよい。問題は、戦略関係ないということにどう気づくか。自分の場合はサンプルを色々いじってみて何となく検討つけた後帰納法で証明したけど、できれば戦略関係ないということを論理的に導き出したい。

#include <cstdio>
#include <vector>
using namespace std;

char buf[1009];

bool solve(){
	vector<int> st;
	for(int i=0; buf[i]; i++){
		st.push_back(buf[i]&15);
	}

	bool ret = false;
	while((int)st.size() > 1){
		int x = st.back(); st.pop_back();
		int y = st.back(); st.pop_back();
		int z = x + y;
		if(z <= 9){
			st.push_back(z);
		}
		else{
			st.push_back(1);
			st.push_back(z%10);
		}
		ret = !ret;
	}
	return ret;
}

int main(){
	int T;
	scanf("%d\n", &T);
	while(T--){
		scanf("%[^\n]%*c", buf);
		printf("%s wins.\n",solve()?"Fabre":"Audrey");
	}
	return 0;
}