Problem F1 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1520/problem/F1

나는 이 문제 내용을 이해하는데 너무 어려워서 포기했다가 다시 풀었다.

문제를 간단히 설명하자면 Polycarp이 게임을 하는데 이 게임에는 숨겨진 배열이 있다.

이 배열은 0과 1로 이루어져 있다.

그리고 숨겨진 배열에서 k 번째 0은 몇 번째 위치에 있는지 찾아내라는 문제가 나온다.

Polycarp는 게임 시스템에 특정 규칙에 맞는 질문을 최대 20번까지 할 수 있다.

? l r 형식대로 출력하는 방식으로 질문을 하면 배열의 l 위치부터 r 위치까지의 원소를 더한 값이 입력되는 방식으로 답을 준다.

이 문제는 easy 버전이므로 문제는 1개가 나온다. 문제의 답은 ! x 형식으로 출력한다.

이 문제는 이분 탐색을 사용해 해결했다.

탐색하고 싶은 내용은 처음 위치부터 r 위치까지의 0의 개수가 k 개 이상인 r 중 가장 작은 값.

배열의 길이는 최대 20만이므로 이분 탐색 과정에서 질문은 최대 18개를 넘지 않는다.

이분 탐색을 끝냈다면 위치 x를 찾았다는 의미인데 이 x는 k 번째 0의 위치이거나 바로 오른쪽의 위치이다.

그렇기 때문에 마지막으로 ? x x 질문을 통해 위치 x의 값이 0인지 확인하여 0이라면 답이 x,

아니라면 x - 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
 
using namespace std;
 
int main() {
 
    int n, t;
    cin >> n >> t;
 
    while (t--) {
 
        int k;
        cin >> k;
 
        int s = 1, e = n, m;
        int pos = n;
 
        while (s <= e) {
            m = (s + e) / 2;
            cout << "? " << 1 << " " << m << endl;
            int num;
            cin >> num;
            if (m - num >= k) {
                e = m - 1;
                if (pos > m)
                    pos = m;
            }
            else {
                s = m + 1;
            }
        }
 
        int val;
        cout << "? " << pos << " " << pos << endl;
        cin >> val;
        if (val == 0)
            cout << "! " << pos << endl;
        else
            cout << "! " << pos - 1 << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기