https://doj.kr/ko/problems/125

아이디어

게임 자체는 '배스킨라빈스 31'의 공략법에서 영향을 받은 것으로 보인다.

'배스킨라빈스 31' 게임은 두 참가자가 1부터 31까지의 숫자를 번갈아가며 연이은 숫자를 한번에 1~3개씩 말하다가, 31을 말하게 되는 사람이 지는 게임이다.

이 게임은 선공 플레이어 A가 후공 B를 반드시 이길 수 있는 필승법이 존재한다.

• A가 첫 자신의 차례에 '1, 2'까지만 말한다.
• B는 1~3개의 연이은 숫자를 아무렇게나 말한다. 이후, A는 이전 턴에 몇 개의 숫자 $i$개를 대답했든 반드시 $4-i$개의 숫자를 말한다.

그렇게 되면, A의 2번째 차례를 마친 뒤 반드시 숫자는 4개를 진행해 6이 된다.

마찬가지의 방법으로 A는 (2, 6), 10, 14, 18, 22, 26, 30으로 차례를 끝낼 수 있다. 이후 B는 31을 말할 수 밖에 없게 되므로 A가 승리한다.

이 필승법은 다음 3가지 사실로 인해 가능한 방법이다.

• "자신의 턴이 돌아올 때 이전 자신의 턴으로부터 반드시 일정하게 4개씩 숫자를 진행시킬 수 있다"
• "30을 4로 나누었을 때 나머지가 2다."
• "항상 선공 플레이어가 '2'를 외칠 수 있다."

이 필승법을 그대로 일반화시켜 '배스킨라빈스 $N$' 게임을 생각해보려 하면 한 가지 문제가 발생하는데,

'배스킨라빈스 $N$' 게임은 두 참가자가 1부터 $N$까지의 숫자를 번갈아가며 연이은 숫자를 한번에 1~$K$개씩 말하다가, $N$보다 큰 수를 말하게 되는 사람이 지는 게임이다.

• A가 첫 자신의 차례에 1~N%(K+1)까지만 말한다 0개의 숫자를 말할 수 없다!
• B는 1~$K$개의 연이은 숫자를 아무렇게나 말한다. 이후, A는 이전 턴에 몇 개의 숫자 $i$개를 대답했든 반드시 $K+1-i$개의 숫자를 말한다.

이 문제에서는 다음과 같은 예외사항을 넣어 문제를 회피했다.

$N−S$가 14의 배수가 되도록 카드를 낼 수 있다면 내고, 그렇지 않다면 마음대로 카드를 낸다.

또 하나의 문제가 있는데, 바로 제출할 프로그램에 해당하는 '행복한 마법소녀'(A)가 '고독한 마법소녀'(B)보다 후공이라는 점이다. 고로 A의 마법을 활용하여, 중간에 무적의 숫자, $N-14i$들을 뺏어오는 수밖에 없다. ($14=K+1$이다.) 그러기 위해서 우린 다음의 사실을 활용할 것이다.

...항상 아래의 전략에 따라 행동한다.
"$N−S$가 14의 배수가 되도록 카드를 낼 수 있다면 내고, ..."

즉, 첫 숫자로는 N % 14가 0이 아니라면 무조건 N % 14를 낸다는 뜻이다. 만약 N % 14가 0이었다고 해도, 이후에 A가 S를 14로 맞춰주지 않는 한 다음 턴에 S가 14의 배수가 되도록 숫자를 내줄 것이다.

B, A, B 순서로 처음 낸 숫자를 i1, o1, i2라고 하자. 이때 i1 + o1가 14가 되지 않도록 o1을 조절하기만 하면, $S=$(i1 + o1 + i2)를 14로 나눈 값으로 무적의 숫자들이 14에 대해 어떤 나머지를 가지는지를 알 수 있다.

이후, 마법을 사용해 B가 목표하는 숫자들을 어긋나게 만들어주자. A의 차례와 마법을 이용하면 한 라운드의 숫자 개수 합을 14보다 작게 만들 수 있고, 이후 부족한 만큼 정확히 말하면 무적의 숫자를 뺏어올 수 있다. 이후는 B가 (아마 별 의미없이) $i$개를 말할 때마다 $14-i$개를 말하면서 남은 숫자를 보내주면 된다.

코드 (Python)

import sys

i1 = int(input())

o1 = 14 - i1 + 1 if i1 != 1 else 1 # play any, but not to be i1 + this = 14.
print(o1, 0)

i2 = int(input()) # now (N-S) % 14 == 0.

print(1, 12) # use magic
input() # 12, now target -1
print(1, 0)

while 1:
    ans = int(input())
    if ans == -1:
        sys.exit(0)
    print(14 - ans, 0)

메모리 및 시간

• 메모리: 57.76 MB
• 시간: 324 ms

후기

• 지인의 창의적인 인터랙티브 문제다.