문제
“분할 콩”이라는 특별한 콩은 분할 시간이 되면
현재 위치로부터 점프한 후 자신을 두개의 같은 콩으로 나누는 콩을 말한다.
N개의 접시가 나란히 놓여있고, 각 접시는 임의 수의 분할 콩을 담고있는 장면을 상상해보자.
가장 왼쪽 접시의 좌측에는 벽이 놓여진다.
분할 시간이 왔을 때, 모든 콩들은 담겨진 접시로부터 점프한 후,
그들 자신을 두 개의 같은 콩으로 나눈다. 각각의 나누어진 콩은
좌우측의 이웃한 접시에 하나씩 나누어 떨어진다.
예)
위의 그림에서 5개의 접시가 좌측에서 우측으로 일렬로 놓여져 있고,
3번째 접시가 하나의 분할 콩을 담고있다.
우리는 이와 같은 형태를 (0, 0, 1, 0, 0)으로 표시한다.
분할의 한 단계가 지난 후에, 다음 그림과 같은 (0, 1, 0, 1, 0)의 형태가 만들어진다.
위의 그림에서 다시 한 단계를 더 거치게 되면 (1, 0, 2, 0, 1)과 같은 구조가 만들어진다.
이 형태는 접시의 좌측과 우측에 각각 1개의 분할 콩을 담고 있는 상태이다.
다음 단계에서 가장 좌측의 접시에 담겨진 콩은 두 개의 콩으로 분할된 후,
좌측의 벽으로 인해 원래의 접시와 우측의 접시에 각각 나누어진 콩을 분배한다.
가장 우측의 접시에 있는 콩은 분할된후 좌측의 접시에만 분배되고 나머지 하나의 콩은 버려진다.
따라서 다음 단계의 상태는 아래 그림과 같이 (1, 3, 0, 3, 0)이 된다.
상태 (1,2,3,4,5)는 한 번의 분할 후에 (3,4,6,8,4)가 된다.
이 때, 우리는 (1,2,3,4,5)를 (3,4,6,8,4)의 조상이라 한다.
대부분의 상태는 유일한 조상을 가지게되지만, 몇몇 상태는 조상을 가지지 못한다.
(1,2,3,4,5) 나 (0,0,1,0,0)는 조상이 없는 예이다. 우리는 이와 같은 상태를 초기 상태라 부른다.
지금 임의의 초기 상태로부터 몇 번의 분할 단계를 거친 후의 상태가 주어진다고 가정하자.
여러분의 과제는 입력으로 주어진 상태를 얻기 위해 초기 상태로부터 거쳐야 하는
분할 단계의 횟수를 계산하는 프로그램을 작성하는 것이다.
입력
입력의 첫 번째 줄은 계산할 상태의 수(1 ~ 10,000)를 나타낸다.
다음 줄부터 각 상태에 대해 두 개의 줄이 할당된다.
첫 번째 줄은 사용되는 접시의 수(2 ~ 1,000)를 의미하며,
다음 줄은 가장 좌측 접시부터 담겨진 콩의 수(0 ~ 1,000,000)를 보여준다.
출력
입력으로 주어진 각 상태에 대해,
초기 상태로부터 각 상태를 얻기 위해 진행되어질 단계의 수를
입력 순서대로 각 줄에 하나씩 명시한다.
예제
4
5
1 3 0 3 0
5
3 4 6 8 4
6
4 1 6 0 4 0
15
10 45 1 120 0 210 0 252 0 210 0 120 0 44 0
3
1
4
10
로그인해야 코드를 작성할 수 있어요.