[POJ] 1067. 取石子游戏

題目連結:http://poj.org/problem?id=1067
我通靈不出來,盯了他一個晚上只發現對於每個$i$都有一個$j$使他慘掉(?,而且似乎有個1.6左右的比例,但我就不會了QAQ
正解是這個:威佐夫遊戲
結論就是只要看符不符合$i < j \land (j-i)\frac{1+\sqrt{5}}{2} == i$就可以了。
我缺少知識QQ
#include <iostream>
#include <cmath>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	long double TongLing = (sqrt((long double)5)+1)/2;
	int n, m;
	while(cin>>n>>m){
		if(n > m) swap(n, m);
		cout << ((int)((m-n)*TongLing) != n) << '\n';
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology