구슬게임 timer 1s memory 128MB

상민이와 영호는 N개의 구슬을 가지고 다음의 게임을 하고자 한다.

처음에 상민이가 먼저 시작하고, 그 다음에는 영호가, 세번째에는 상민이가 차례를 번갈아가면서 진행한다. 상민이는 처음에 1개 이상 N개 이하의 구슬을 가져갈 수 있다. 처음을 제외하고는 1개 이상 바로 이전 차례에 상대가 가져간 갯수의 2배 이하의 구슬을 가져갈 수 있다. 마지막에 남은 자갈을 모두 가져가게 되는 사람이 게임을 이기게 된다. 다음의 게임을 진행할 때 상민이가 반드시 이기기 위해 처음에 가져가야 할 구슬의 개수를 구하는 프로그램을 작성하라.

상민이와 영호 모두 서로 최적의 게임을 진행한다 가정하며, 이길 수 있는 처음에 가져가는 구슬의 개수가 여럿일 경우 그중 가장 작은 것을 출력한다.