高僧鬥法

問題描述

　　古時喪葬活動中經常請高僧做法事。儀式結束後，有時會有“高僧鬥法”的趣味節目，以舒緩壓抑的氣氛。

　　節目大略步驟為：先用糧食（一般是稻米）在地上“畫”出若幹級台階（表示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;
}