boj 24553 팰린드롬 게임

https://www.acmicpc.net/problem/24553

 

N개의 돌 중에 팰린드롬 수만큼의 돌을 가져갈 수 있으며, 마지막에 모든 돌을 가져가는 사람이 이깁니다.

 

우선 1 ~ 9는 팰린드롬이므로 무조건 먼저하는 사람이 이깁니다.

N = 10이라면 1 ~ 9개를 가져가더라도 9 ~ 1개는 무조건 남기 때문에 먼저하는 사람이 집니다.

그리고 N = 11 ~ 19는 1 ~ 9를 적절하게 뺀다면 다음 사람에게 10을 넘겨줄 수 있으므로 무조건 이길 수 있습니다.

이런식으로 간다면 10의 배수가 아닐때는 무조건 선공이 이긴다는 것을 알 수 있습니다.

0으로 시작하는 수는 없으므로 10의 배수는 팰린드롬이 올 수 없으므로 다른건 고려하지 않아도 됩니다.

 

 

#include <iostream>
using namespace std;
typedef long long ll;
 
ll N;
 
void func() {
    if (N % 10) cout << "0\n";
    else cout << "1\n";
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}