Time Limit: 1s
Memory Limit: 128MB
합법적인 이유로 컴퓨터 프로그래밍 시간에 게임을 해보자! 대신 허용하는 게임을 제한하였다. 후후...
혹시 유클리드 알고리즘을 이용해서 gcd(Greatest Common Divisor)를 구하는 법을 알고있는가? 오늘 할 게임은 이 유클리드 알고리즘을 이용해서 하는 숫자게임이다.
게임을 위해선 처음 2개의 숫자 a b가 필요하다. 두 명의 사람이 번갈아가면서 플레이를 하는데, 각 턴마다 작은 숫자의 배수를 큰 숫자에 빼버릴 것이다. 아래의 예시는 a = 25, b = 7 일 때의 플레이 과정이다..
25 7
--> player 1 : a = 25 - 2*7
11 7
--> player 2 : a = 11 - 1*7
4 7
--> player 1 : b = 7 - 1*4
4 3
--> player 2 : a = 4 - 1*3
1 3
--> player 1 : b = 3 - 3*1
1 0
이렇게 되면 2번째 플레이어 차례에 작은 숫자인 0은 아무리 곱해도 0이므로 숫자를 변동시킬 수 없게된다. 따라서 두번째 플레이어는 패배하고, 첫번째 턴에 플레이한 사람이 승리한 것이다.
프로 게이 머인 Gravek**per는 이 게임을 수백만번 플레이해서 필승법을 거의 완벽하게 익혀냈다. 만약 시작할 때 주어진 숫자 a b 가 주어지게 된다면 두 사람이 항상 최선을 다할 때 내가 승리할지 패배할지를 경험적으로 알아낼 수 있다고한다. 하지만 애석하게도 그는 이를 알고리즘화시키진 못했다.
우리는 이 게임의 규칙을 방금 들었다. a와 b가 주어졌을 때 항상 최선을 다하는 두 플레이어중 누가 승리하는지를 알아내는 프로그램을 작성하여 프로 게이 머를 놀래켜보자.
입력은 여러 케이스로 이루어져있다. 각 테스트케이스마다 한줄에 하나씩 게임에서 사용되는 숫자 a b가 주어진다. a,b는 signed int 범위를 벗어나지 않는 자연수이다. 만약 0 0 이 들어온다면 프로그램을 마친다.
각 테스트 케이스마다 어떤 플레이어가 승리하는지를 알려주자. 먼저 플레이하는 플레이어가 승리하면 "Stan wins"을, 나중에 플레이하는 플레이어가 승리하면 "Ollie wins"을 출력하면 된다.
34 12 15 24 0 0
Stan wins Ollie wins