[BZOJ] 3404: [Usaco 2009 오픈] Cow Digit Game 또 디지털 게임 (게임 이론)

http://www.lydsy.com/JudgeOnline/problem.php?id=3404
몇 번 이나 좌절 을 썼 는데...
누 드 게임 이론 이면 됩 니 다.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

 

const int N=1000005;

bool f[N], vis[N];

bool dfs(int x) {

    if(vis[x]) return f[x];

    if(x==0) return 0;

    vis[x]=1;

    int t=x, mx=0, mn=10;

    while(t) {

        int k=t%10;

        t/=10;

        if(k) mx=max(mx, k), mn=min(mn, k);

    }

    if(!dfs(x-mn)) return f[x]=1;

    if(!dfs(x-mx)) return f[x]=1;

    return f[x]=0;

}

int main() {

    int n=getint();

    while(n--) {

        int ans=dfs(getint());

        ans?puts("YES"):puts("NO");

    }

    return 0;

}

 
 
 
 
Description
    베 시 와 존 은 숫자 게임 을 하고 있다. 베 시 는 네가 그녀 를 도와 줄 필요 가 있다.
    게임 은 모두 G (1 ≤ G ≤ 100) 장 을 진행 하 였 습 니 다. i 차 게임 은 하나의 정수 Ni (l ≤ Ni ≤ 1, 000, 000) 에서 시 작 됩 니 다. 게임
연극 규칙 은 다음 과 같다. 쌍방 이 돌아 가면 서 조작 하고 현재 의 숫자 를 한 수 를 빼 면 이 수 는 현재 숫자의 최대 숫자 일 수도 있 고 가장 작은 비 0 디지털 일 수도 있다. 예 를 들 어 현재 의 수 는 3014 이 고 조작 자 는 1 을 빼 면 3013 이 될 수도 있 고 4 를 빼 면 3010 이 될 수도 있다. 만약 에 조작 을 한 후에이 숫자 는 0 이 될 것 이다. 이때 더 이상 조작 할 수 없 는 쪽 은 패자 이다.    베 시 는 항상 먼저 조작 을 시작한다. 베 시 와 존 이 충분히 똑똑 하 다 면 가장 좋 은 전략 을 실행 하 라. 마지막 승 자 를 계산 하 라.
    예 를 들 어 한 게임 은 13 에서 시작 되 었 다. 베 시 는 13 에서 3 을 빼 고 10 으로 변 했다. 존 은 10 에서 1 을 빼 고 9 로 변 했다. 베 시 는 9 에서 9 를 빼 고 0 으로 변 했다. 마지막 에 베 시가 이 겼 다.
Input
    첫 번 째 줄 은 정수 G 를 입력 한 다음 G 줄 한 줄 에 Ni 를 입력 합 니 다.
Output
 
    모든 게임 에 대해 베 시가 이 길 수 있다 면 'YES' 한 줄 을 출력 합 니 다. 그렇지 않 으 면 한 줄 의' NO '에 지 는 것 입 니 다.
Sample Input
2
9
10
Sample Output
YES
NO
HINT

For the first game, Bessie simply takes the number 9 and wins.


For the second game, Bessie must take 1 (since she cannot take 0), and then


FJ can win by taking 9.

Source
Silver