hdu 2176(m)石取りゲーム

4136 ワード

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2176
題意分析:M堆石を与え、二人が交互に子を取り、先手が勝つかどうかを与える.Noを出力することができず、できればYesを出力し、1回目の取子の個数を与える.典型的なNimゲームは,まずT状態を判断し,非T状態であれば初めての取子の個数を求める.
/* (m )    



Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1956    Accepted Submission(s): 1130





Problem Description

m   ,     .   1   .    .      No.      Yes,        .  5  5,7,8,9,10    ,    1       8       7   1 ,     9        9   0 ,     10        7   3 .

 



Input

     .   1  m,m<=200000.   m      .m=0  .

 



Output

      No.      Yes,        1        .    a             b       a b.  Sample Output.

 



Sample Input

2

45 45

3

3 6 9

5

5 7 8 9 10

0

 



Sample Output

No

Yes

9 5

Yes

8 1

9 0

10 3

 



Author

Zhousc

 



Source

ECJTU 2008 Summer Contest

 

*/

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 200000 + 10;

int N[maxn], m;

void solve()

{

     int flag = N[0], cnt;

     for(int i = 1; i < m; i++) flag ^= N[i];

     if(flag == 0) printf("No
"); else{ printf("Yes
"); for(int i = 0; i < m; i++){ cnt = N[i]^flag; if(cnt < N[i]) printf("%d %d
", N[i], cnt); } } } int main() { while(~scanf("%d", &m) && m){ for(int i = 0; i < m; i++) scanf("%d", &N[i]); solve(); } return 0; }