[BOJ 33871] 서로소 게임

View as PDF

Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 1G

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

수민이와 송이는 서로소 게임을 하기로 했다. 서로소 게임의 규칙은 다음과 같다.</p>

  • 처음에 칠판에 $1$보다 큰 자연수 $N$이 적혀 있다.
  • 수민이랑 송이가 번갈아 가며 아래의 단계를 반복한다.
  • 현재 칠판에 적힌 수 $x$보다 작으면서 $x$와 서로소인 $1$이 아닌 수 $y$를 하나 골라 $x$를 지우고 적는다.
  • 고를 수 있는 $y$가 존재하지 않을 때 게임에서 지게 된다.

수민이와 송이는 최선을 다해 게임을 진행하고 수민이부터 시작하면 누가 이기게 될지 구해보자.

입력 형식

처음에 적힌 수 $N$이 주어진다. $(2 \leq N \leq 10^{9})$

출력 형식

수민이가 이기면 Soomin, 송이가 이기면 Song이라고 출력한다.

예제 입력 1

2

예제 출력 1

Song

예제 입력 2

5

예제 출력 2

Soomin

Comments

There are no comments at the moment.