13848번 - 나누는 자가 지배한다 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 (추가 시간 없음) | 512 MB | 126 | 26 | 22 | 24.176% |
문제
"Divisor is the Conquerer"은 혼자 할 수 있는 카드 게임이다. 보통 이런 단순한 게임은 시간을 보내기 좋은 방법이지만, 프로그래머인 당신은 그 시간에 프로그래밍을 하고 싶을 것이다. 당신의 과제는 "Divisor is the Conquerer" 게임을 자동으로 해결하는 컴퓨터 프로그램을 만드는 것이다. 아래에 게임 규칙이 있다.
먼저, 무작위로 N개의 카드를 카드 덱에서 뽑는다 (1 ≤ N ≤ 52). 게임은 뽑은 카드들만을 이용해서 진행되고, 다른 카드들은 사용되지 않을 것이다.
그뒤 반복해서 한 장씩 카드를 바닥에 내려놓는다. 맨 처음 내려놓을 때는 어떤 카드이든 내려놓을 수 있다. 그 뒤에는 내려놓은 카드들을 "지배하는" 카드만을 내려놓을 수 있다. 어떤 카드가 카드들의 집합을 지배한다는 것은 카드가 의미하는 수가 카드 집합의 수들의 합을 나눈다는 것이다. 예를 들어, 카드 7은 집합 {5, 11, 12}를 지배하지만, 카드 11은 집합 {5, 7, 12}를 지배하지 않는다.
처음에 고른 N개의 카드를 모두 내려놓으면 게임에 승리하게 된다. 이것에 실패하면, 즉 중간에 카드를 내려놓을 수 없게 되면 패배한 것이다.
입력
입력은 여러 개의 테스트 케이스로 구성된다.
각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 카드의 개수를 의미하는 정수 N (1 ≤ N ≤ 52) 이 있다. 두 번째 줄은 각 카드가 의미하는 숫자를 뜻하는 N개의 정수 c1 , . . . , cN (1 ≤ ci ≤ 13) 로 구성된다. 한 테스트 케이스에서 같은 수를 의미하는 카드의 개수가 최대 4개까지라는 것을 가정해도 된다.
0이 입력되면 입력이 끝난다.
출력
각각의 테스트 케이스에 대해 한 줄씩 출력한다. 입력된 초기 조건에서 이길 수 있는 전략이 있으면, 가능한 전략 중 아무거나 N개짜리 정수 목록으로 공백으로 구분하여 출력한다.
만약 이길 수 있는 방법이 없으면, “No”라고 출력한다.
예제 입력 1
5 1 2 3 3 7 4 2 3 3 3 0
예제 출력 1
3 3 1 7 2 No
출처
Contest > ICPC Japanese Alumni Group > JAG Practice Contest for ICPC Asia Regional > JAG Practice Contest 2005 D번
- 문제를 번역한 사람: 2a2aq
- 문제의 오타를 찾은 사람: silvercube
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호