[HOJ 257][POI 19 Stage 3][Interactive]Bidding

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

這題的題目敘述爛掉了......
總之，你覺得少一個字的地方就填N吧(?)
可以發現，pot的石頭數一定是(2^a)*(3^b)
因此，在<30000的範圍pot可能的數字最多O(logN)個
再加上stack，可能的狀態數不超過O(NlogN)個
這樣就可以實現記憶化搜索了
如果不能動任何一步讓對手輸，你就輸了
反之，你就贏了
詳情請參考code

要注意的是，本題的#include "interactive/257.h"之前一定要有#include<cstdio>或#include<stdio.h>，不然會編譯錯誤說你沒定義scanf和printf
=ㄦ=

code:

#include<cstdio>
#include<map>
#include<cassert>
#include"interactive/257.h"
using namespace std;
//int Init(){return 15;}
//void Alois(int v){static int cnt=0;if(cnt>100)exit(0);printf("cnt=%d\n",cnt++);}
//int Byteasar(){return 1;}
int N,POT,STK;
map<pair<int,int>,bool>DP;
bool Win(const int pot,const int stk)
{
    if(pot+stk>=N)return false;
    const auto s=make_pair(pot,stk);
    const auto it=DP.find(s);
    if(it!=DP.end())return it->second;
    if(Win(pot*2,stk)&&Win(pot*3,stk)&&Win(1,stk+pot))return DP[s]=false;
    return DP[s]=true;
}
int main()
{
    N=Init();
    POT=1,STK=0;
    DP.clear();
    for(;;)
    {
        if(!Win(POT*2,STK))Alois(2),POT*=2;
        else if(!Win(POT*3,STK))Alois(3),POT*=3;
        else if(!Win(1,STK+POT))Alois(1),STK+=POT,POT=1;
        else assert(0);
        const int result=Byteasar();
        if(result==2)POT*=2;
        else if(result==3)POT*=3;
        else if(result==1)STK+=POT,POT=1;
        else assert(0);
    }
    return 0;
}