백준10837 동전 게임

작성일 | In

문제 링크

  • http://icpc.me/10837

문제 출처

  • 2015 KOI 중등부 1번, 고등부 1번

시간복잡도

  • 각 입력 별로 $O(1)$

풀이

$M = N$인 경우에는 항상 가능합니다. 그렇지 않은 경우를 생각해봅시다.

영희는 첫 $M$번의 차례에서 $M$점을 얻고, 동수는 첫 $N$번의 차례에서 $N$점을 얻었을 때, 남은 라운드($K - \max(M, N)$)동안 두 사람의 점수 차($\vert M - N \vert$)를 메꿀 수 있는지 판별하면 됩니다.

$M > N$인 경우에는 $\vert M - N \vert - (K - \max(M, N)) \leq 2$이면 두 사람의 점수차를 메꿀 수 있고, $M < N$인 경우에는 $\leq 1$이면 두 사람의 점수차를 메꿀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int K, T; cin >> K >> T;
    while(T--){
        int M, N; cin >> M >> N;
        if(M == N){ cout << "1\n"; continue; }
        int rem = K - max(M, N), d = abs(M - N);
        if(M > N && d - rem <= 2) cout << "1\n";
        else if(M < N && d - rem <= 1) cout << "1\n";
        else cout << "0\n";
    }
}