| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 301 | 9 | 6 | 10.909% |
Darkest night, I'll confront you here....
이 문제는 투 스텝 인터랙티브 문제입니다.
히카리와 타이리츠는 협동 게임을 하여 그들의 우정을 증명하고자 한다.
게임은 $n$개의 직선이 있는 평면에서 진행된다. 어떠한 두 직선도 평행하지 않으며, 어떠한 세 직선도 한 점에서 만나지 않으며, 모든 직선은 $x$축, 혹은 $y$축과 평행하지 않는다.
어떠한 위치 $(x_0, y_0)$ 이 직선 $y = ax + b$ 위에 있다는 것은, $y_0>ax_0+b$를 만족한다는 것이다. 반대로, 어떠한 위치 $(x_0,y_0)$ 이 직선 $y = ax + b$ 아래에 있다는 것은, $y_0<ax_0+b$를 만족한다는 것이다. 이에 따라, 평면 상에서 직선에 속하지 않는 모든 점들은 각 직선의 위에 있거나 아래에 있다.
어떠한 두 점 $p, q$ 가 $n$ 개의 직선에 대해서 항상 같이 위에 있거나 같이 아래에 있다면, 두 점 $p, q$ 는 같은 구역에 속한다고 한다. 상술한 문제 조건에 따라서, 평면은 정확히 $\frac{n(n+1)}{2}+1$ 개의 구역들로 분할됨을 증명할 수 있다.
두 서로 다른 구역 $e, f$ 가 인접하다는 것은, $e, f$ 에 속하는 임의의 두 점 $p(e), p(f)$ 에 대해서 $p(e)$ 와 $p(f)$ 사이를 정확히 하나의 직선만을 가로질러 이동할 수 있음을 뜻한다. 서로 다른 인접한 쌍은 정확히 $n^2$ 개임을 증명할 수 있다.
게임은 히카리가 각 구역들에 특정한 표시를 남긴 후, 타이리츠가 이 표시를 통해서 구역 간을 이동하는 식으로 이루어진다.
히카리의 차례를 먼저 설명한다. 히카리가 각 구역들에 표시를 남기는 것은 다음과 같은 인터랙션을 통해 이루어진다.
이제 타이리츠의 차례를 설명한다. 타이리츠의 목표는 평면의 어떤 구역에서 게임을 시작하여, 다른 어떤 구역으로 이동해야 한다. 일련의 이동 과정은 다음과 같은 인터랙션을 통해 이루어진다.
타이리츠의 차례를 진행할 때, 타이리츠가 도착하고 싶은 구역과 첫 번째 정수와 두 번째 정수가 동일한 어떤 구역에 도달했다고 하더라도, 해당 구역이 타이리츠가 도착하고 싶은 구역은 아닐 수도 있음에 유의하라.
게임을 성공할 수 있게, 히카리와 타이리츠의 전략을 수행하는 프로그램을 작성하여라. 히카리가 처음에 선언하는 정수 $M$이 작으면 작을수록 더욱 큰 점수를 얻을 수 있다.
첫 번째 줄에는 입력의 종류를 나타내는 정수 $T(T\in \left\{ 0,1 \right\})$가 주어진다. $T=0$인 경우 프로그램은 히카리의 전략을 수행해야 하고, $T=1$인 경우 타이리츠의 전략을 수행해야 한다.
$T=0$인 경우, 당신은 히카리의 전략을 수행해야 한다.
당신은 첫 줄에 $1\,000$ 이하의 양의 정수 $M$을 출력해야 한다. 이는 히카리가 처음에 선언하는 정수를 의미한다.
이후 인터랙터는 다음과 같은 정보들을 순서대로 제공한다:
해당 입력들을 받고 나서, 당신은 총 $\frac{n(n+1)}{2}+1$개의 줄에 걸쳐 두 정수 $a,b$를 공백으로 구분하여 출력해야 하는데, $i$번째 줄의 출력은 히카리가 $i$번 구역의 첫 번째 정수를 $a$로, 두 번째 정수를 $b$로 설정하겠다는 것이다.
$T=1$인 경우, 당신은 타이리츠의 전략을 수행해야 한다.
첫 번째 줄에 $n$이 주어지고, 다음 줄에 네 개의 정수 $x,y,z,w$가 공백으로 구분되어 주어진다. 이는 현재 타이리츠가 위치한 구역의 첫 번째, 두 번째 정수가 각각 $x,y$라는 것이고, 타이리츠가 도달하고자 하는 구역의 첫 번째, 두 번째 정수가 각각 $z,w$라는 것이다.
그 뒤, 이동이 진행된다. 매 이동은 다음과 같이 진행된다:
만약 위와 같은 형식이 아닌 인터랙션을 시도하거나, 이동을 반복한 횟수가 $6n$을 초과한다면 틀린 것으로 간주한다.
두 실행을 통틀어서, 프로그램의 모든 출력 이후에는 반드시 버퍼를 비워야 한다.
Subtask 2에서는 당신이 사용한 $M$의 최댓값에 따라서 당신의 점수가 결정된다. $M'$을, 당신이 모든 테스트케이스를 통틀어서 사용한 $M$의 최댓값이라고 하자. 이때, Subtask 2에서 받는 점수는 다음과 같다.
| 조건 | 점수 |
|---|---|
| $1\,000<M'$ | $0$ |
| $600<M'\le 1\,000$ | $18$ |
| $60 < M' \le 600$ | $18+45\times \frac{600-M'}{540}$ |
| $28 < M' \le 60$ | $63+27\times \frac{60-M'}{32}$ |
| $M' \le 28$ | $90$ |
0 3 -6 0 0 6 -6 0 6 -2 0 6 6 -2 000 100 010 001 110 011 111 1 2 1 3 1 4 2 5 3 5 3 6 4 6 5 7 6 7
7 1 0 2 1 3 2 4 3 5 3 6 2 7 3
입력에서 주어진 $3$개의 직선에 의해 전체 구역은 다음의 그림과 같이 분할된다.
해당 입출력은 인터랙션의 가독성을 위해 임의로 빈 줄을 추가한 것으로, 실제 인터랙션에서는 빈 줄을 입출력하는 것을 포함하지 않음에 유의하라.
1 3 3 2 4 3 1000110 0 0101000 1
1 4
맨 처음에 타이리츠는 3번 구역에서 시작하고, 4번 구역으로 가야 한다. 3번 구역은 1,5,6번 구역과 인접해 있기 때문에, 첫 번째 정수가 1,5,6인 구역과 인접해있다는 정보를 타이리츠에게 제공한다. 타이리츠는 해당 정보를 받고, 첫 번째 정수가 1인 구역으로 이동한다.
이제 타이리츠는 1번 구역에 있다. 1번 구역은 타이리츠가 도착해야 하는 구역이 아니기 때문에, 인터랙터는 0을 입력하고 다시 길이 7의 이진수열을 입력한다. 1번 구역은 2,3,4번 구역과 인접해있지만, 3번 구역은 직전에 방문했기 때문에 인터랙터는 첫 번째 정수가 2,4인 구역과 인접해있다는 정보를 타이리츠에게 제공한다. 타이리츠는 이를 받고 첫 번째 정수가 4인 구역으로 이동한다.
이제 타이리츠는 4번 구역에 있다. 이는 타이리츠가 도착해야 하는 구역이므로, 인터랙터는 1을 출력하고 인터랙션이 종료된다.
해당 입출력은 인터랙션의 가독성을 위해 임의로 빈 줄을 추가한 것으로, 실제 인터랙션에서는 빈 줄을 입출력하는 것을 포함하지 않음에 유의하라.
출력 버퍼를 비우는 방법은 다음과 같다.
fflush(stdout)std::cout << std::flushSystem.out.flush()sys.stdout.flush()이외의 언어에 대해서는 언어별 명세를 참고해야 한다.
University > KAIST > KAIST RUN Spring Contest > 2025 KAIST RUN Spring Contest I번
