4342번 - 유클리드 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1432 | 437 | 328 | 33.469% |
문제
유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, 큰 수는 음이 아닌 정수가 되어야 하며 전보다 작아져야 한다. 그런 다음 동규는 동혁이가 한 것과 똑같이 큰 수를 작은 수의 배수만큼 뺀다. 이런식으로 두 플레이어는 서로 번갈아가면서 게임을 한다. 이때, 큰 수를 0으로 만든 사람이 게임을 승리하게 된다.
예를 들어, 다음과 같이 (25, 7)로 시작한 게임을 생각해보자.
- 25 7
- 11 7
- 4 7
- 4 3
- 1 3
- 1 0
위와 같이 게임을 하게 되면, 동혁이가 이기게 된다. (큰 수와 작은 수는 각 턴에서 큰 수와 작은 수이다.)
시작하는 두 자연수가 주어졌을 때, 두 플레이어가 최적의 방법으로 게임을 할 때, 누가 이기는지 구하는 프로그램을 작성하시오.
입력
입력은 여러 줄로 이루어져 있다. 각 줄은 게임을 시작하는 두 숫자이다. 항상 동혁이가 먼저 게임을 시작한다. 두 자연수는 231-1보다 작거나 같다. 입력의 마지막 줄에는 0 두 개가 주어진다.
출력
각 입력에 대해서 동혁이가 이기면 A wins를, 동규가 이기면 B wins를 출력한다.
예제 입력 1
34 12 15 24 0 0
예제 출력 1
A wins B wins
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호