51NOD1070 BASH game V4

Problem

There are N stones in a pile. A and B take turns to take, A takes first. The minimum amount taken each time is 1, and the maximum shall not exceed twice the amount taken by the opponent last time (A must not take all of them when he takes the first time). The one who gets the last stone wins. Assuming that both A and B are very smart, there will be no mistakes in the process of picking up stones. Give N and ask who will win the game in the end.

For example, N = 3. A can only get 1 or 2 stones, so B can get the last stone.

Solution

I have been typing and writing for a long time, and I will come back to make up when I see how to prove it.

Code

#include
#include
#include
#define ll long long
#define inf 0x7fffffffffffffff
#define mem(a, x) memset(a,x,sizeof(a))
#define io_opt ios::sync_with_stdio(false);cin. tie(0);cout.tie(0)
typedef std::pair Pii;
typedef std::pair Pll;
ll power( ll a, ll b,ll p) {ll res = 1; for (; b> 0; b >>= 1) {if (b & 1) res = res * a% p; a = a * a% p ;} return res; }
ll gcd(ll p, ll q) {return q == 0? p: gcd(q, p% q); }
ll _abs(ll x){return x <0? -x: x;}
using namespace std;
int T,n;
bool fg;
int dfs(int cur,int cnt){
 if(cur==0) return 0;
 if(cur==1) return 1;
 if(cur==2) return 1;
 bool fg2=fg;< br /> fg=false;
 for(int i=1;i<=min(2*cnt,cur);i++){

 if(fg2&&i==cur) break; //cout<<"*"< if(!dfs(cur-i, i)) return 1;
 }
 return 0 ;
}< br />ll s[120]={0,1,1,2,3};
int main(){
 io_opt;
 /*for(int i=1;i <=100;i++){
 //if(i==3)cout<<"!!!"< fg=true;
 if(i!=2 ) cout< else{
 cout<<"2:0
";
 }
 //if(i==3) cout<<"!!!"< }*/
 for(int i=5;i<=100&&s[i-1] <10000000000;i++){
 s[i]=s[i-1]+s[i-2];
 }
 cin>>T;
 while(T --){
 cin>>n;
 bool k=false;
 for(int i=2;i<=100;i++){
 if(s[i ]==n){
 k=true;
 break;
 }
 }
 if(k){
 cout<<"B
 ";
 }
 else{
 cout<<"A
";
 }
 }
 return 0;
}