시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
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”라고 출력한다.
5 1 2 3 3 7 4 2 3 3 3 0
3 3 1 7 2 No
Contest > ICPC Japanese Alumni Group > JAG Practice Contest for ICPC Asia Regional > JAG Practice Contest 2005 D번