시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7 3 3 42.857%

문제

홀순이(holsoon)와 짝순이(jjaksoon) 둘이서 숫자 게임을 한다. 정수 1과 3이 주어지고, 이 둘을 통틀어 5번까지 마음대로 사용하여 그 합을 구하여 1,2,3,…을 만드는 놀이다. 먼저, 홀순이가 1 하나만을 사용하여 1을 만든다. 짝순이는 1+1로 1을 두 번 사용하여 2를 만들고, 다시 홀순이는 3을 만들어야하는데 1+1+1로 1을 세 번 사용하거나 3을 한 번 사용하여 3을 만든다. 짝순이는 1+1+1+1, 1+3으로 4를 만든다. 서로 번갈아서 상대방의 수보다 1이 큰 수를 만들어야 한다. 단, 1과 3을 통틀어 최대 5번 사용한다. 이런 식으로 진행하면 13까지는 만들 수 있지만 14를 만들지 못하게 되므로 짝순이가 졌다. 

숫자들과 사용 최대 회수가 주어질 때, 누가 어느 수에서 이기는지를 판별하는 프로그램을 작성하는 것이 문제다. 주어지는 숫자에는 반드시 1이 포함된다. 그렇지 않으면 홀순이가 1을 만들지 못하므로 무조건 지게 된다. 1이 꼭 있으니깐 쉽게 생각하면 상대방이 만든 방법에 1만 한 번 더 쓰면 되지라고 하기 쉽지만 숫자 사용 회수가 정해져 있으므로, 이 방법이 숫자가 커지는 경우에는 잘 되지 않는다. 위에서 13을 홀순이가 만들었지만 짝순이는 숫자 사용 제한 회수 때문에 14를 만들지 못하고 진다.

입력

첫째 줄에 숫자 종류의 개수, 둘째 줄에는 주어지는 숫자들이 작은 것에서 큰 것으로 순서대로 나오며 (1000이하의 수), 세 번째 줄은 숫자 사용 회수(≤50)이 주어진다.

출력

첫째 줄에 누가 몇 번째 숫자에서 이겼는지를 출력한다. (예제에서는 짝순이가 14를 못 만들어서, 홀순이가 14에서 이겼다)

예제 입력

2
1 3
5

예제 출력

holsoon win at 14

힌트

출처

  • 문제를 번역한 사람: author6