[ACM]hdu 2177取(2堆)石子ゲーム(ウィゾフゲーム)
Problem Description
石が2つ積まれていて、数は任意で、異なってもいいです.ゲームは二人で交代で石を取り始めた.ゲームの規定では、毎回2つの異なる取り方があり、1つは任意の山の中で任意の石を取ることができる.二つ目は、二つの山の中で同じ数の石を同時に取り出すことができることです.最後に石を全部取った者を勝者とする.今、最初の2つの石の数を与えて、もしあなたが先に取る番になったら、双方が最高の策略を取って、最後にあなたが勝者なのか敗者なのかを聞いてみましょう.もしあなたが勝ったら、1回目はどうやって取りますか?
Input
入力はいくつかの行を含み、いくつかの石の初期状況を表し、各行は2つの非負の整数aおよびbを含み、2つの石の数を表し、aおよびbは100000を超えず、a<=bである.a=b=0で終了します.
Output
出力もいくつかの行があり、最後にあなたが敗者であれば0、逆に1を出力し、あなたを勝たせたあなたが1回目に石を取った後に残った2つの石の数x,y,x<=yを出力します.任意の一山の中から石を取り出すことで勝てると同時に同じ数の石を同時に取り出すことでも勝てる、同じ数の石を先に取り出す場合を出力する.
Sample Input
1 2 5 8 4 7 2 2 0 0
Sample Output
0 1 4 7 3 5 0 1 0 0 1 2
Author
Zhousc
Source
ECJTU 2008 Summer Contest
解题思路:
(a,b)奇异态先手必败,非奇异态先手必胜。先判断初始状态,如果为奇异态,则先手必败,否则,要输出先手第一次取石子后,两堆石子各剩下多少个,即由非奇异态转到奇异态。 做法是枚举所有的状态。比如测试数据中的 初始 5 8 是非奇异态,
则先手第一次取石子两堆可能剩下的状态有
一。两堆取相同的石子数
4 7
3 6
2 5
1 4
0 3
二。在第一堆里取
4 8
3 8
2 8
1 8
0 8
三。在第二堆里取
5 7
5 6
5 5
5 4
5 3
5 2
5 1
5 0
代码:
#include
#include
#include
#include
using namespace std;
bool solve(int a,int b)// (a,b)
{
double x=(1+sqrt(5))/2;
int n=b-a;
if(a==(int)(x*n))
return 1;
return 0;
}
int main()
{
int a,b;
while(cin>>a>>b&&(a||b))
{
if(solve(a,b))
{
cout<<0<m)
swap(n,m);
if(solve(n,m))
cout<