바둑돌 색 바꾸기

면접 대비

시간 제한1초메모리 제한128 MB

요약

이웃한 두 돌의 xor를 원형 간격마다 채우는 과정을 k번 반복한 뒤 흰 돌 개수를 구합니다.

문제

상자에 검은 바둑돌과 흰 바둑돌이 잔뜩 들어 있다. 이 상자에서 바둑돌 $n$ 개를 꺼낸다. 먼저 꺼낸 $m$ 개는 모두 흰 돌이고 나머지는 모두 검은 돌이다. 꺼낸 순서 그대로 원을 따라 일정한 간격으로 $n$ 개를 늘어놓는다.

그다음에는 원에 놓인 돌의 색을 보고 상자에서 새 돌을 꺼내 새 원을 만든다. 원을 한 바퀴 돌면서 이웃한 두 돌 사이마다 새 돌을 하나씩 놓는데, 규칙은 이렇다.

돌 사이가 $n$ 군데이므로 새 원에도 돌이 $n$ 개 놓인다. 새 돌을 다 놓으면 원래 있던 돌 $n$ 개를 모두 걷어낸다. 여기까지가 한 번의 반복이고, 남은 원을 가지고 같은 과정을 되풀이한다.

$k$ 번 반복한 뒤 원에 남은 흰 돌이 몇 개인지 구하라.

아래 그림은 $n = 8$ , $m = 2$ , $k = 2$ 인 경우다. 왼쪽부터 처음 배치, 첫 번째 반복 뒤, 두 번째 반복 뒤이다.

$n$ 과 $k$ 는 자연수이고 $0 < n < 129$ , $k < 10001$ 이다. $m$ 은 $1 \le m \le n$ 을 만족한다.

한 줄에 데이터 한 묶음이 주어진다. 각 줄에는 자연수 $n$ , $m$ , $k$ 가 쉼표 하나로 구분되어 주어지며 공백은 없다. 마지막 데이터 다음 줄에는 입력이 끝났음을 뜻하는 -1이 주어진다.

데이터 한 묶음마다 한 줄씩 출력한다. 각 줄에는 입력받은 데이터를 n,m,k 꼴 그대로 먼저 쓰고, 콜론과 공백 하나를 쓴 다음, 계산한 흰 돌의 개수를 쓴다.