갑돌이와 갑순이는 구슬게임을 하고 있다. 게임의 규칙은 다음과 같다: 갑돌이와 갑순이는 각각 일정 수의 구슬을 가지고 시작한다. 갑돌이는 자신의 손에 A개의 구슬을 내밀고, 갑순이는 A가 짝수인지 홀수인지 맞춘다.

만약 갑순이가 맞추면, 그녀는 갑돌이에게서 A개의 구슬을 얻는다.

반대로 틀리면, 갑순이는 자신이 가진 구슬 A개를 잃고 갑돌이에게 준다. 만약 갑순이가 A개의 구슬보다 적게 가지고 있다면, 그녀는 남은 모든 구슬을 잃는다.

한 플레이어가 모든 구슬을 잃으면 패배한다.

몇 번의 턴이 지나고 난 후, 갑순이는 N개의 구슬을 가지고 있다. 그녀는 이기기 어렵다고 느끼지만, 패배하지 않으려고 게임을 계속하고 있다. 갑순이는 갑돌이의 습관을 잘 파악하여, 턴 i에서 갑돌이가 내미는 구슬의 개수가 K개의 서로 다른 값 중 하나라는 것을 알고 있다. 또한, 갑돌이는 M번의 턴이 지나면 지루해져서 게임을 멈춘다.

갑순이가 어떤 방식으로든 패배하지 않도록 보장할 수 있는 사전순으로 가장 작은 턴 시퀀스를 찾아야 한다.

#8143 upload - done - how_to_reg - call_split Subtask

구슬게임 필승법 timer 1s memory 1024MB

#8143
Subtask

구슬게임 필승법 1s 1024MB