51nod Bash 게임 (V1, V2, V3, V4 (피 보 나치 게임)

Bash 게임 V1
한 무더기 의 돌 이 있 는데 모두 N 개가 있다.A. B 는 두 사람 이 돌아 가면 서 들 고 A 가 먼저 든다.매번 최소 1 개, 최대 K 개 를 가 져 가 마지막 돌 1 개 를 가 져 가 는 사람 이 이긴다.A B 가 모두 똑똑 하 다 고 가정 하면 돌 을 잡 는 과정 에서 실수 가 없 을 것 이다.N 과 K 를 주 고 마지막 에 누가 이 길 수 있 는 지 물 어보 세 요.
예 를 들 어 N = 3, K = 2.A 가 어떻게 든 B 는 마지막 돌 을 얻 을 수 있다.
Input

 1 ：   T，               。（1 <= T <= 10000)
 2 - T + 1 ：  2  N，K。       。（1 <= N,K <= 10^9)

Output

 T ，  A    A，  B    B。

입력 예제

4
3 2
4 2
7 3
8 3

출력 예제

B
A
A
B

문제 풀이 방향:
    만약 에 (k + 1) 의 정수 배 라면 먼저 1 ~ k 안의 수 x 를 취하 고 뒷손 으로 (k + 1 - x) 개의 돌 을 취 할 수 있다. 그래서 k + 1 의 정수 배 는 선수 의 필 패 상태 이 고 같은 이치 로 k + 1 의 정수 배가 아 닐 때 먼저 n% (k + 1) 개의 돌 을 취하 여 뒷손 을 반드시 패 하 게 할 수 있다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int n,k,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        if(n%(k+1))
        printf("A
");
        else
        printf("B
");
    }
    return 0;
}

Bash 게임 V2
한 무더기 의 돌 이 있 는데 모두 N 개가 있다.A. B 는 두 사람 이 돌아 가면 서 들 고 A 가 먼저 든다.매번 1, 3, 4 개 만 가 져 갈 수 있 고 마지막 돌 을 가 져 온 사람 이 이긴다.A B 가 모두 똑똑 하 다 고 가정 하면 돌 을 잡 는 과정 에서 실수 가 없 을 것 이다.N 을 주 고 마지막 에 누가 이 길 수 있 는 지 물 어보 세 요.
예 를 들 어 N = 2.A 는 한 개 만 가 져 갈 수 있 기 때문에 B 는 마지막 돌 을 가 져 갈 수 있다.
Input

 1 ：   T，               。（1 <= T <= 10000)
 2 - T + 1 ：  1  N。(1 <= N <= 10^9)

Output

 T ，  A    A，  B    B。

입력 예제

3
2
3
4

출력 예제

B
A
A

문제 풀이 방향:
    이 문 제 는 직접 생각 나 지 않 으 면 sg 함수 로 시 계 를 쳐 서 규칙 을 발견 하여 풀 수 있다.
 sg 함수 와 sg 정리:
     임의의 상태 x 에 대해 SG (x) = mex (S) 를 정의 합 니 다. 그 중에서 S 는 x 의 후계 상태의 SG 함수 의 집합 이 고 mex (s) 는 S 에 없 는 최소 마이너스 정 수 를 표시 합 니 다.예 를 들 어 x 는 6 개의 후계 상태 가 있 고 SG 함수 수 치 는 각각 0, 1, 1, 2, 4, 7 이면 SG (x) = 3 이다. 3 은 후계 상태 SG 함수 값 집합 에 나타 나 지 않 은 첫 번 째 비 마이너스 정수 이기 때문이다.
이 문제 의 sg 함수 코드:

const int maxn=45;
bool vis[maxn];
int sg[maxn];
int a[5]={1,3,4};
void sgs()
{
    for(int i=0;i<maxn;i++)
    {
        memset(vis,false,sizeof(vis));
        for(int j=0;j<3;j++)
        {
            if(i>=a[j])
            vis[sg[i-a[j]]]=true;
        }
        for(int j=0;;j++)
        {
            if(!vis[j])
            {
                sg[i]=j;
                break;
            }
        }
        printf("%d %d
",i,sg[i]);
    }
}

타 표를 통 해 7 의 정수 배 와 n% 7 = = 2 의 필 패 태 를 발견 했다.
증명:
    1, 2 에 대해 서 는 반드시 패 할 것 이다.
    2, 1, 3, 4 에 선 수 는 반드시 이긴다.
    3. 5, 6 에 대해 서 는 먼저 3, 4 를 취하 여 뒷 손 을 필 패 상태 로 들 어 갈 수 있다.
    2. 7 에 대해 먼저 무엇 을 취하 든 후 수 는 필 패 상태 에 들 어가 게 할 수 있다. 먼저 1 을 취하 고 나중에 4 를 취하 여 필 패 상태 에 들 어 갈 수 있다.먼저.       후수
취하 다먼저 4 를 취하 고, 나중에 3 을 취하 면 된다.그래서 7 의 배수 나% 7 여 2 의 것 이 라면 모두 필 패 태, 기타 이다.     모두 필승 적 이다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        if(n%7==0||n%7==2)
        printf("B
");
        else
        printf("A
");
    }
    return 0;
}

Bash 게임 V3
한 무더기 의 돌 이 있 는데 모두 N 개가 있다.A. B 는 두 사람 이 돌아 가면 서 들 고 A 가 먼저 든다.매번 가 져 가 는 수량 은 2 의 정수 차 멱 에 불과 하 다. 예 를 들 어 (1, 2, 4, 8, 16...) 마지막 돌 을 가 진 사람 이 이긴다.A B 가 모두 똑똑 하 다 고 가정 하면 돌 을 잡 는 과정 에서 실수 가 없 을 것 이다.N 을 주 고 마지막 에 누가 이 길 수 있 는 지 물 어보 세 요.
예 를 들 어 N = 3.A 는 한 개 또는 두 개 만 가 져 갈 수 있 기 때문에 B 는 마지막 돌 을 가 져 갈 수 있다.(입력 한 N 은 대수 일 수 있 습 니 다)
Input

 1 ：   T，               。（1 <= T <= 1000)
 2 - T + 1 ：  1  N。(1 <= N <= 10^1000)

Output

 T ，  A    A，  B    B。

입력 예제

3
2
3
4

출력 예제

A
B
A

문제 풀이 방향:
   sg 함수:

const int maxn=1000+100;
int sg[maxn];
bool vis[maxn];
int main()
{
    for(int i=0;i<50;i++)
    {
        memset(vis,false,sizeof(vis));
        for(int j=0;(1<<j)<=i;j++)
        {
            int s=i-(1<<j);
            vis[sg[s]]=true;
        }
        for(int j=0;;j++)
        {
            if(!vis[j])
            {
                sg[i]=j;
                break;
            }
        }
        printf("%d ",sg[i]);
    }
    return 0;
}

3 의 정수 배 면 된다 는 것 을 발견 했다.
증명:
   임의의 1 개 3 의 정수 배 는 2 * n 개 2 의 정수 멱 의 합 으로 바 뀔 수 있다.매 거 를 통 해 알 수 있 듯 이:
   (2^0)%3=1; (2^1)%3=2;(2^2)%3=1;(2^3)%3=2;
   항상 1 과 2, 임의의 1 개% 3 을 1 로 하고% 3 을 2 로 하면% 3 의 수 를 구성 할 수 있다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
char s[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        int n=strlen(s);
        int ans=0;
        for(int i=0;i<n;i++)
        {
            ans=ans+(s[i]-'0');
        }
        if(ans%3)
        printf("A
");
        else
        printf("B
");
    }
    return 0;
}

Bash 게임 V4 (피 보 나치 게임)
한 무더기 의 돌 이 있 는데 모두 N 개가 있다.A. B 는 두 사람 이 돌아 가면 서 들 고 A 가 먼저 든다.매번 가 져 가 는 수량 은 최소 1 개 로 상대방 이 지난번 에 가 져 간 수량의 최대 2 배 를 넘 지 않 는 다 (A 1 차 가 져 갈 때 다 가 져 갈 수 없다 고 요구 함).마지막 돌 을 얻 은 사람 이 이긴다.A B 가 모두 똑똑 하 다 고 가정 하면 돌 을 잡 는 과정 에서 실수 가 없 을 것 이다.N 을 주 고 마지막 에 누가 이 길 수 있 는 지 물 어보 세 요.
예 를 들 어 N = 3.A 는 한 개 또는 두 개 만 가 져 갈 수 있 기 때문에 B 는 마지막 돌 을 가 져 갈 수 있다.
Input

 1 ：   T，               。（1 <= T <= 1000)
 2 - T + 1 ：  1  N。(1 <= N <= 10^9)

Output

 T ，  A    A，  B    B。

입력 예제

3
2
3
4

출력 예제

B
B
A

문제 풀이 방향:
인용 하 다.http://blog.csdn.net/acm_cxlove/article/details/7835016
이 게임 은 Fibonacci Nim 이 라 고 합 니 다. 긍정 과 Fibonacci 수열: f [n]: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89... 밀접 한 관계 가 있다.만약 시험 을 한 번 한 후에 선수 가 이 겼 고 n 만 피 보 나치 수가 아니 라 고 추측 할 수 있다.필 패 태 는 피 보 나치 수열 을 구성 한 다 는 얘 기다.
여 기 는 'Zeckendorf 정리' (지 켄 도 프 정리) 를 빌려 야 한다. 모든 정 수 는 몇 개의 불 연속 적 인 Fibonacci 수의 합 을 나 타 낼 수 있다.
먼저 FIB 수열 의 필 패 증명 서 를 보십시오.
1. i = 2 일 때 먼저 한 개 만 얻 을 수 있 고 분명히 반드시 패 하고 결론 이 성립 된다.
2. i < = k 를 가설 할 때 결론 이 성립 된다.
     i = k + 1 시 f [i] = f [k] + f [k - 1].
     우 리 는 이 돌 더 미 를 두 무더기 로 볼 수 있 는데, 약칭 k 더미 와 k - 1 더미 라 고 부른다.
    (반드시 두 무더기 로 볼 수 있다. 만약 에 먼저 첫 번 째 로 얻 은 돌의 수가 f [k - 1] 보다 크 거나 같 으 면 뒷손 으로 f [k] 를 직접 취 할 수 있 기 때문이다. 왜냐하면 f [k] < 2 * f [k - 1])
     k - 1 더미 에 대해 가설 을 통 해 알 수 있 듯 이 먼저 어떻게 취하 든 뒷손 은 항상 마지막 하 나 를 얻 을 수 있다.다음은 뒷손 에서 마지막 으로 얻 은 돌 수 x 의 상황 을 분석 해 보 자.
     만약 에 첫 번 째 로 얻 은 돌의 수 y > = f [k - 1] / 3 이면 이 작은 더미 에 남 은 돌의 수 는 2y 보다 적 고, 즉 뒷손 으로 직접 얻 을 수 있다. 이때 x = f [k - 1] - y 는 x < = 2 / 3 * f [k - 1].
     2 / 3 * f [k - 1] 와 1 / 2 * f [k] 의 크기 를 비교 해 보 겠 습 니 다.즉 4 * f [k - 1] 와 3 * f [k] 의 크기 는 수학 귀납법 에서 얻 기 어렵 지 않 고 후자 가 크다.
     그래서 우 리 는 x < 1 / 2 * f [k] 를 얻 었 다.
     즉, 후수 가 k - 1 더 미 를 다 뽑 은 후에 먼저 k 더 미 를 한꺼번에 다 뽑 을 수 없 기 때문에 게임 규칙 이 바 뀌 지 않 았 다 면 가설 을 통 해 알 수 있 듯 이 k 더 미 는 후수 가 마지막 하 나 를 얻 을 수 있 기 때문에 후수 가 반드시 이 길 수 있다.
     즉 i = k + 1 시 결론 은 여전히 성립 된다.
FIB 수가 아 닌 것 에 대해 서 는 먼저 분 해 를 진행한다.
분해 할 때 는 최대한 큰 피 보 나치 수 를 취해 야 한다.
예 를 들 어 85: 85 는 55 와 89 사이 에 있 기 때문에 85 = 55 + 30 으로 쓰 고 30, 30 은 21 과 34 사이 에 계속 분해 하기 때문에 30 = 21 + 9 로 쓸 수 있다.
이에 따라 마지막 으로 85 = 55 + 21 + 8 + 1 로 분해 된다.
n 을 쓸 수 있 습 니 다. n = f[a1]+f[a2]+……+f[ap]。（a1>a2>……>ap）
우 리 는 먼저 f [ap], 즉 가장 작은 이 무 더 기 를 다 가 져 오 라 고 명령 했다.각 f 간 연속 되 지 않 기 때문에 a (p - 1) > ap + 1, f [a (p - 1)] > 2 * f [ap] 가 있 습 니 다.즉, 뒷손 으로 f [a (p - 1)] 한 무더기 만 가 져 갈 수 있 고 한 번 에 다 가 져 갈 수 없다.
이때 후 수 는 이 서브 게임 (f [a (p - 1)] 이라는 돌 더미 에 직면 하고 후 수 는 먼저 취한 다) 의 필 패 상태 에 해당 한다. 즉, 선 수 는 반드시 이 더미 의 마지막 돌 을 얻 을 수 있다.
같은 이치 로 알 수 있 듯 이 앞으로 의 모든 더미 에 대해 선 선수 들 이 이 더미 의 마지막 돌 을 가 져 와 게임 의 승 리 를 얻 을 수 있다.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=50;
long long f[50];
int main()
{
    f[1]=1,f[2]=2;
    for(int i=3;i<maxn;i++)
    f[i]=f[i-1]+f[i-2];
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int sign=1;
        for(int i=1;i<maxn;i++)
        {
            if(f[i]>n)
            break;
            if(f[i]==n)
            {
                sign=0;
                break;
            }
        }
        if(sign)
        printf("A
");
        else
        printf("B
");
    }
    return 0;
}