| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 75 | 20 | 16 | 59.259% |
이 문제는 인터랙티브 문제이다.
주어진 양의 정수 $n\le 15$과, 1ドル\le m\le 2n$에 대해서, RUN game이라는 것은 "방어자"가 "공격자"의 공격을 방어하는 컨셉으로 이루어지는 2인용 경쟁 게임이다. 그 진행방식은 다음과 같이 기술된다:
조건: 임의의 1ドル\le i\le n$에 대해서, $B_x,B_y,B_z$중 적어도 하나는 $i$번째 원소가 2ドル$이다. 또한, $B_x,B_y,B_z$에 속한 2ドル$의 개수의 총합이 $m$ 이하여야 한다.
히카리와 타이리츠는 RUN game을 플레이하려고 한다. 이들의 게임은 다음과 같이 진행될 것이다.
일단, 맨 처음 $n,m$이 주어지고 나면 타이리츠는 공격자를 할지 방어자를 할지 결정한다.
타이리츠가 방어자를 하기로 결정했다면, 일반적인 RUN game의 룰대로 타이리츠는 히카리에게 2ドル^n-1$개의 수열을 제공하고, 히카리는 그중 조건을 만족하지 않는 $x,y,z$를 찾는다.
그러나, 타이리츠가 공격자를 하기로 결정했다면, 타이리츠는 1ドル$ 이상 2ドル^n-1$ 이하인 $x$에 대해 히카리에게 다음과 같은 질문을 최대 20ドル$개 할 수 있다:
? $A_x$: 히카리가 생각한 $B_x$를 반환받는다.최대 20ドル$번의 질문 이내에 만약 타이리츠가 조건을 만족하지 않는 $x,y,z$를 찾았다면, 타이리츠는 그 이진전개를 선언하고 승리할 수 있다. 만약 20ドル$번 이내에 이를 찾지 못했다면, 히카리가 승리한다.
타이리츠의 전략을 수행하는 프로그램을 작성하여라.
맨 처음, 그레이더는 $n,m$을 공백으로 구분하여 프로그램에게 제공한다. 프로그램은 이를 받고, 방어자를 선택할 것이라면 0을, 공격자를 선택할 것이라면 1을 출력한다.
만약 방어자를 선택한 경우, 그 다음 $i$번째 줄에는 타이리츠가 결정할 $B_i$를 공백없이 출력한다.
만약 공격자를 선택한 경우, 프로그램은 1ドル$ 이상 2ドル^n-1$ 이하인 $x$에 대해 다음과 같은 쿼리에 대한 답을 최대 20ドル$번 받을 수 있다:
? $A_x$: 히카리가 결정한 $B_x$가 공백없이 다음 줄에 입력된다.만약 조건을 만족하지 않는 세 정수 $x,y,z$를 발견했다면,
! $A_x$ $A_y$ $A_z$과 같은 형식으로 세 정수의 이진전개를 출력하고 승리를 선언한다.
두 쿼리 전부에 대해서, 어떤 정수의 길이 $n$의 이진전개를 출력할 때에는, $n$개의 원소를 공백없이 한 줄에 출력한다. 매 질의 혹은 선언 이후에는 반드시 버퍼를 비워야 한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $m=2n$ |
| 2 | 10 | $n\le 3$ |
| 3 | 10 | $n\le 5$ |
| 4 | 20 | $n\le 7$ |
| 5 | 10 | $n\le 10$ |
| 6 | 10 | $n\le 12$ |
| 7 | 30 | 추가적인 제약 조건이 없다. |
3 6
0 221 212 211 122 121 112 111
타이리츠는 $n=3,ドル $m=6$을 받고, 방어자를 선택하였다. 세 정수 $x=1,y=2,z=4$를 생각하자. 이들은 $x+y+z=7=2^n-1$을 만족하며, 이들 중 어느 두 개를 선택하여도 그 bitwise AND가 0ドル$이다. 또한, 이 세 정수는 "조건"을 만족하는데, 왜냐하면 임의의 1ドル\le i\le 3$에 대해서 $i$번 원소가 2ドル$인 수열이 있고, $B_1,B_2,B_4$의 2ドル$의 개수의 총합은 6ドル$인데, 이는 $m=6$을 초과하지 않기 때문이다.
3 2 021 212 100
1 ? 001 ? 010 ? 100 ! 010 001 100
해당 입출력은 인터랙션의 가독성을 위해 임의로 빈 줄을 추가한 것으로, 실제 인터랙션에서는 빈 줄을 입출력하는 것을 포함하지 않음에 유의하라.
어떤 정수 0ドル\le t<2^n$에 대해서, $t$의 길이 $n$의 이진전개라는 것은 길이 $n$의 이진수열 $a_na_{n-1}...a_1$인데, 이때 $a_i$는 $\left\lfloor \frac{t}{2^{i-1}} \right\rfloor$가 홀수라면 1ドル$이고, 그렇지 않다면 0ドル$이다. 간단히 말해서, $a_i$는 $t$의 $i$번째 비트이다.
출력 버퍼를 비우는 방법은 다음과 같다.
fflush(stdout)std::cout << std::flushSystem.out.flush()sys.stdout.flush()이외의 언어에 대해서는 언어별 명세를 참고해야 한다.
University > KAIST > KAIST RUN Spring Contest > 2025 KAIST RUN Spring Contest G번