高僧斗法

问题描述

　　古时丧葬活动中经常请高僧做法事。仪式结束后，有时会有“高僧斗法”的趣味节目，以舒缓压抑的气氛。

　　节目大略步骤为：先用粮食（一般是稻米）在地上“画”出若干级台阶（表示N级浮屠）。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人，其它任意。(如图1所示)

　　两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶，但会被站在高级台阶上的小和尚阻挡，不能越过。两个小和尚也不能站在同一台阶，也不能向低级台阶移动。

　　两法师轮流发出指令，最后所有小和尚必然会都挤在高段台阶，再也不能向上移动。轮到哪个法师指挥时无法继续移动，则游戏结束，该法师认输。

　　对于已知的台阶数和小和尚的分布位置，请你计算先发指令的法师该如何决策才能保证胜出。 输入格式 　　输入数据为一行用空格分开的N个整数，表示小和尚的位置。台阶序号从1算起，所以最后一个小和尚的位置即是台阶的总数。（N<100, 台阶总数<1000） 输出格式 　　输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。若有多个解，输出A值较小的解，若无解则输出-1。 样例输入 1 5 9 样例输出 1 4 样例输入 1 5 8 10 样例输出 1 3

本题涉及到的博弈类型与nim博弈类似。 我们可以先分析一下nim博弈

Nim游戏的概述：

还记得这个游戏吗？

给出n列珍珠，两人轮流取珍珠，每次在某一列中取至少1颗珍珠，但不能在两列中取。最后拿光珍珠的人输。

后来，在一份资料上看到，这种游戏称为“拈（Nim）”。据说，它源自中国，经由被贩卖到美洲的奴工们外传。辛苦的工人们，在工作闲暇之余，用石头玩游戏以排遣寂寞。后来流传到高级人士，则用便士（Pennies），在酒吧柜台上玩。

最有名的玩法，是把十二枚便士放成3、4、5三列，拿光铜板的人赢。后来，大家发现，先取的人只要在3那列里取走2枚，变成了1、4、5，就能稳操胜券了，游戏也就变得无趣了。于是大家就增加列数，增加铜板的数量，这样就让人们有了毫无规律的感觉，不易于把握。

直到本世纪初，哈佛大学数学系副教授查理士•理昂纳德•包顿（Chales Leonard Bouton）提出一篇极详尽的分析和证明，利用数的二进制表示法，解答了这个游戏的一般法则。

一般规则是规定拿光铜板的人赢。

它的变体是规定拿光铜板的人输，只要注意某种特殊形态（只有1列不为1），就可以了！

有很多人把这个方法写成计算机程序，来和人对抗，不知就理的人被骗得团团转，无不惊叹计算机的神奇伟大。其实说穿了，只因为它计算比人快，数的转化为二进制其速度快得非人能比，如此罢了。

（以上来自K12教育论坛）

例子1:（0，4，8）我们会发现只要从8中取4，变成（0，4，4），让两个相等就能 稳操胜券了； 例子2:（3，4，5）先取的人只要在3那列里取走2枚，变成了1、4、5， 例子3:（0，0，4）变成（0，0，0） 这里可能就要引入一个规律了，就是每一堆 数量的异或运算的和如果为0；那么当前局势就是必胜局势，（哈佛大学数学系副教授查理士•理昂纳德•包顿（Chales Leonard Bouton）提出一篇极详尽的分析和证明，利用数的二进制表示法） 所以如果当前局势异或运算和为0的话就是必败，没有挽回的余地了，如不为0，我们可以调整一个堆的数量，将其变成必胜局势。

再来分析高僧斗法，

题目用例的1 5 8 10； 其实你可以发现，在第二个数（5）与第三个数（8）得距离多少对结果是毫无影响的， 因为当你将第二个数的位置往前提的时候，你的对手只要将第一个数往前提相同位数就可以了，一个轮回可以变成3 7 8 10； 所以可以发现2n位置上的和尚和2n+1位置上的和尚距离多少是可以不用管的。 我们只要提取2n-1位置上的和尚和2n位置上的距离，就可以建立nim博弈的模型了 所以1 5 8 10的nim模型为 3（5-1-1） 1（10-8-1）； 我们可以把1和5 间的距离减小2个单位 所以 1移动到3位置 我们也可以把8和10 间的距离增加2个单位 所以 8移动到6位置

而且上例中的1和8 移动的都是可移动范围。 所以输出a较小的值就是1 3

接下来贴代码

//
//  main.cpp
//  高僧斗法
//  http://blog.csdn.net/mymilkbottles/article/details/51362703部分参考
//  log.csdn.net/qiankun1993/article/details/6765688
//  Created by zjt on 2017/1/10.
//  Copyright © 2017年 zjt. All rights reserved.
//

#include <iostream>
#include<string.h>
using namespace std;
int arr[110];
int num[55];
int numlong;

void print(int n)
{
    int i=0;
    int ans;
    ans=0;
    for(i=0;i<numlong;i++)
    {
        if(i!=n)
        {
            ans^=num[i];
        }
    }
//    cout<<ans<<" " <<num[n]<<endl;
    if(ans>num[n])
    {
        if((arr[n*2+2]-arr[n*2+1])>(ans-num[n]))
        {
            cout<<arr[n*2+1]<<" "<<arr[n*2+1]+(ans-num[n])<<endl;
            return;
        }
        else
        {
            print(n+1);
        }
    }
    else
    {
        if((arr[n*2+1]-arr[n*2])>(num[n]-ans))
        {
            cout<<arr[n*2]<<" "<<arr[n*2]+(num[n]-ans)<<endl;
            return;
        }
        else
        {
            print(n+1);
        }
    }
}
int main(int argc, const char * argv[]) {
    // insert code here...
//    std::cout << "Hello, World!\n";
    int y,j;
    j=0;
    memset(arr, 0, sizeof(arr));
    int i=0;
    char s;
    while(1)
    {
        scanf("%d%c",&arr[i++],&s) ;
        if(s=='\n') break;
    }
        memset(num,0,sizeof(num));
    for(y=1;y<i;y+=2)
    {
        num[j++]=arr[y]-arr[y-1]-1;
    }
    int ans;
    numlong=j;
    j=0;
    while(num[j]!=0)
    {
        ans^=num[j++];
//        cout<<num[j-1]<<endl;
    }
    if(ans==0){
        cout<<"-1"<<endl;
    }
    else
    {
        print(0);
    }
    return 0;
}