24682번 - 수식 완성 게임

문제

수식 완성 게임은 16silver가 만든 2인용 게임이다. 게임은 다음과 같이 진행된다.

• 목표 수 $N$을 정한다. 이 값은 1 이상 100 이하의 자연수이다.
• 두 플레이어가 번갈아 가면서, 1 이상 5 이하의 자연수 하나를 쓴다. 이때, 처음 쓴 자연수의 뒤에 이어서 자연수를 하나씩 쓴다. 예를 들면, 선공이 4를 쓰고 후공이 5를 쓴다면 칠판에는 4 5가 적혀 있다. 이때 선공이 3을 쓰면 칠판에는 4 5 3이 쓰여 있게 된다.
• 각 플레이어는 자신이 자연수를 쓸 차례에, 자연수를 쓰는 대신 "가능!"를 외칠 수 있다. "가능!"를 외친 플레이어는 칠판에 쓰여 있는 수에 사칙연산과 괄호를 넣어서 $N$를 만들어야 한다. $N$을 만들 경우 게임에서 승리하며, 만들지 못할 경우 게임에서 패배한다. 예를 들면, 목표 수가 17이고, 칠판에 4 5 3이 쓰여 있다면, 자연수를 쓰는 대신 "가능!"를 외치고 4×5-3이라는 식을 쓸 수 있다.

만들 수 있는 식과 그 계산에 대한 규칙은 다음과 같다.(예시에서 칠판에는 4 5 3이 쓰여 있다고 가정한다.)

1. 곱셈, 나눗셈은 덧셈, 뺄셈보다 먼저 계산하며, 같은 우선순위의 연산자는 왼쪽에서 오른쪽으로 계산한다.

• 4+5×3=27 (X)
• 4+5×3=19 (O)
• (4+5)×3=27 (O)

2. "-" 기호는 단항 연산자로 사용할 수 없다.

• -4+5×3=11 (X)

3. 두 개 이상의 숫자를 연결하여 하나의 수로 사용할 수 없다.

• 45-3=42 (X)

4. 칠판에 있는 숫자의 순서를 바꿀 수 없다.

• 4×3-5=7 (X)

5. 계산 중간 과정의 값은 양의 정수가 아닐 수 있으며, 나눗셈은 실수 나눗셈을 적용한다.

• 4-5+3=2 (O)
• 4/5+3=3 (X)
• 4/5+3=3.8 (O)

6. 연산 과정에서 0으로 나눌 수 없다.

• 4/(3-3) (X)

16silver와 cozyyg가 수식 완성 게임을 한다. 목표 수가 주어지면, 두 플레이어 모두가 최선을 다했을 때 이기는 플레이어를 출력하여라. 게임은 16silver가 먼저 시작한다.

입력

첫 번째 줄에 목표 수 $N$이 주어진다.

출력

첫 번째 줄에 이기는 사람을 출력한다.

제한

• 1ドル \le N \le 100$

힌트