ez_code   4년 전

문제

배스킨 라빈스 21 게임이 아이들에게 유행입니다. 게임은 다음과 같이 진행됩니다: 첫 번째 플레이어가 1 또는 2 중 하나의 수 n0을 말합니다. 두 번째 플레이어는 n1 ∈ {n0 + 1, n0 + 2}인 수 n1을 말할 수 있습니다. 플레이어가 순서를 돌아가며 이 과정을 반복하되, 항상 전 사람이 말한 수보다 1 또는 2가 큰 수만 말할 수 있습니다. 21을 말하는 플레이어가 이깁니다. 수열이 될 수 있는 하나의 경우는 다음과 같습니다: 1, 3, 5, 6, 7, 9, 11, 12, 14, 15, 16, 18, 19, 21. 이 게임에서 두 번째 플레이어가 어떻게 하면 이기는지 알 경우 첫 번째 플레이어는 항상 집니다.

세대가 거듭할수록 아이들은 똑똑해집니다. 현재 많은 아이들은 배스킨 라빈스 21이 너무 쉬워 재밌다고 여기지 않고 배스킨 라빈스 N으로 게임을 일반화하려고 합니다. 21을 대신해 정수 N이 주어질 때, 첫 번째 플레이어는 1 또는 2를 말할 수 있습니다. 플레이어가 순서를 돌아가며 이전 수에 1 또는 2를 더해가, 한 명이 N을 말해 이기면 게임이 끝납니다. 두 플레이어가 모두 똑똑해 게임을 아주 잘 안다고 할 때, 당신은 첫 번째 플레이어가 게임에서 이기기 위해 첫 수로 무슨 수를 골라야 하는지 판정해야 합니다.

입력

한 줄에 배스킨 라빈스 N에서 N 자리에 들어갈 정수 N(3 <= N <= 10 ^ 100)이 입력됩니다.

출력

{1, 2} 중 첫 번째 플레이어가 무조건 게임에서 이기기 위해 선택해야 하는 수를 나타내는 하나의 정수를 한 줄에 출력합니다. 이기는 것이 불가능하다면, 0을 출력합니다.

댓글을 작성하려면 로그인해야 합니다.