시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 4994 | 627 | 326 | 9.758% |
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 가져갈 수 있는 돌의 개수는 정해져있다. 돌을 올바른 개수만큼 가져갈 수 있는 방법이 없는 사람이 게임을 지게 된다.
M과 가져갈 수 있는 돌의 개수가 주어졌을 때, 창영이가 이기는 N중에서 1보다 크거나 같고, M보다 작거나 같은 것의 개수를 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
첫째 줄에 M이 주어진다. (1 ≤ M ≤ 109)
둘째 줄에는 가져갈 수 있는 방법의 수 K가 주어진다. (1 ≤ K ≤ 22)
셋째 줄에는 가져갈 수 있는 돌의 개수가 공백으로 구분되어서 주어진다. 개수는 1보다 크거나 같고, 22보다 작거나 같으며, 중복되는 수는 없다. 또, 오름차순으로 주어진다.
창영이가 이기는 N의 개수를 출력한다. (1 ≤ N ≤ M)
20 3 1 2 3
5
999 1 1
499
1000000000 2 1 2
333333333
6543 5 2 4 7 11 20
1637