[CF 1194D] 1-2-K Game

[CF 1194D] 1-2-K Game - 1700

문제 설명 : 

0번째부터 n번째 칸이 있는 판이 있다. n번째 칸부터 시작하여 두 사람이 번갈아가며 게임을 하면서 매 시행마다 1칸 혹은 2칸 혹은 k칸을 현재 칸에서 왼쪽으로(작은 값)움직일 수 있다. 그래서 본인 차례에서 말이 0번째 칸에 위치한 사람이 패배하게 되는 게임이다. 두 사람은 최적으로 게임한다고 할 때 누가 이기는지 찾는 문제이다.

풀이 : 

이런 게임문제의 유형에서 누가 이기냐를 정할 때는 항상 두 사람이 최적으로 플레이한다고 하는데 이 말을 풀어쓰면 이렇다. 

'맨 처음에 시작하는 사람이 반드시 이길 수 있는가?'를 묻는 것과 같다. 만약 반드시 이길 수 없다면 그 다음 사람이 이기게 되는 것과 같다 이 문제에서는 처음 시작하는 사람이 Alice이므로 n번째 칸에서 시작했을 때, Alice가 반드시 이길 수 있는 전략이 존재하는지 묻는 것과 같다. 

이 게임은 0번째 칸이 본인 차례일 때 패배한다. 그래서 만약 본인 차례가 1칸이나 2칸이면 말을 0번째 칸에 놓고 상대방에 턴을 넘기면 본인이 승리한다. 하지만 본인 차례에 3칸에 있다면 어떨까? 만약 k=3이라면 바로 0칸으로 움직여서 승리할 수 있지만, k>3이라면 반드시 지게 된다. 여기서 한 가지 관찰이 가능하다. 만약 k가 3의 배수가 아니면서 본인 차례에 3의 배수 칸(0,3,6,9,12..)에 위치한다면 본인은 반드시 패배할 수밖에 없다. 게임의 필승 전략은 상대방 턴에 3의 배수 칸이 되도록 말을 가져다 두는 것인데, 이 상황에서는 절대로 말을 3의 배수 칸에 가져다 놓을 수 없기 때문이다. 따라서 k가 3의 배수가 아닐 때 n=0,3,6,9...라면 Bob이 승리하고 n이 3의 배수가 아닐 때는 Alice가 승리한다.

그렇다면 k가 3의 배수일 때를 생각해보자. n<k일 때까지는 BAABAABAA...패턴이 반복될 것이다. 그러다가 n==k인 순간에는 반드시 Alice가 승리할 수 있다(현재 n칸에서 바로 k칸을 왼쪽으로 움직이면 0칸이므로). 그리고 n==k+1칸일 때를 보자. 1칸, (k-1)칸,k칸 모두 상대방에게 넘기면 본인이 패배하게 된다. n==k+2,k+3칸일 때는 말을 k+1칸에 가져다 놓으면 되므로 다시 본인이 승리할 수 있다. 즉 n==k칸 이후로는 0번째 부터 시작되었던 사이클이 반복된다. 

주의할 점 : 

-

배운 점 : 

이런 게임 유형에서는 congruence(합동)이론이 쓰인다. 

게임의 필승 전략은 상대방에게 0칸을 가져다 놓으면 본인이 승리한다. 움직일 수 있는 방법이 1칸,2칸,k칸이므로 본인 차례에 1칸,2칸,k칸에 위치한다면 승리할 수 있는 것이다. 이를 바탕으로 k에 대한 규칙성을 찾으면 된다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
string exm;
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
template <typename T>
inline void showAll(vector<T> &v,string sep=""){
    for(T &here:v) cout<<here<<sep;}
template <typename T>
inline vector<int> int_seperation(T N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
// const int SIZE=
 
int main(){
    int t;  scanf("%d",&t);
 
    while(t--){
        int n,k;    scanf("%d %d",&n,&k);
        int ans=0;
 
        if(k%3){
            if(n%3==0) ans=2;
            else ans=1;
        }
        else{
            if(n<k){
                if(n%3==0) ans=2;
                else ans=1;
            }
            else{
                if(n>k) n=n%(k+1);
                if(n==k) ans=1;
                else{
                    if(n%3==0) ans=2;
                    else ans=1;
                }
                
            }
        }
 
        printf("%s\n",(ans==1)?"Alice":"Bob");
    }
 
    return 0;
}
/*

*/