자동 인형은 동일한 과정을 자동으로 반복하는 인형이다.

일본에서는 여러가지 자동 인형이 오래 전 부터만들어져 왔다.

자동 인형의 동작은 장치들로 구성된 회로에 의해 조정된다.

장치들은 튜브로 연결되어 있다.

각 장치는 몇 개의 진입구와 한 개 혹은 두 개의 출구를 가진다.

각 장치가 가질 수 있는 진입구의 개수에는 제한이 없다 (0개일 수 있음).

각 튜브는 어떤 장치의 출구와 어떤 장치의 진입구를 연결한다.

한 장치의 출구와 동일한 장치의 진입구를 연결하는 것도 가능하다.

각 출구와 각 진입구에는 정확히 하나씩의 튜브가 연결되어 있다.

자동 기계의 동작을 설명해 보자.

공 하나가 어떤 장치에 있다고 하자.

이 공은 회로를 돌아다니게 된다.

각 스텝에서 공은 현재 공이 위치한 장치의 출구 중 하나로 나와서 튜브를 따라 이동한 다음 어떤 장치의 진입구로 들어간다.

장치는 시작, 트리거, 스위치의 3가지 종류가 있다.

시작 장치는 정확히 1개, 트리거는 M개, 스위치는 S개가 있다. (S는 0일 수 있다.)

S의 값은 당신이 결정해야 한다.

각 장치는 유일한 일련번호를 가진다.

시작 장치는 공이 최초에 놓이는 장치이다.

시작 장치는 1개의 출구를 가진다.

시작 장치의 일련번호는 0이다. (앞으로 단순히 시작이라고 부른다.)

트리거 장치는, 공이 들어갈 때마다 인형이 재미있는 동작을 하게 만드는 장치이다.

트리거 장치는 1개의 출구를 가진다.

트리거 장치의 일련번호는 1부터 M까지이다. (앞으로 단순히 트리거, 혹은 트리거 i라고 부른다.)

스위치 장치는 'X'와 'Y'라고 불리는 개의 출구를 가진다.

스위치 장치의 상태는 'X'나 'Y' 중 하나이다.

공이 스위치 장치에 들어가면 공은 그 스위치 장치의 상태와 같은 출구로 나간다.

직후에, 스위치 장치의 상태는 다른 상태로 바뀐다.

초기에 모든 스위치 장치의 상태는 'X'이다.

스위치 장치의 일련번호는 -1부터 -S까지이다. (앞으로 단순히 스위치, 혹은 스위치 -j라고 부른다.)

트리거의 개수 M이 입력으로 주어진다.

또, 길이 N인 수열 (혹은 배열) A가 주어진다.

수열 A의 원소는 트리거의 일련번호들이다.

각 트리거의 일련번호는 수열 A에 몇 번 (혹은 0번) 나타난다.

당신은 다음 조건을 만족하는 회로를 구성해야 한다.

- 공은 몇 번의 스텝을 거친 다음에 시작으로 돌아와야 한다.

- 공이 최초로 시작에 다시 돌아올 때, 모든 스위치의 상태는 'X'이어야 한다.

- 공이 최초로 시작에 다시 돌아올 때까지 공은 트리거를 정확히 N번 지나야 한다. 또, 공이 트리거들을 지나간 순서의 일련번호는 A₀, A₁, ... , A_N-1와 완전히 같아야 한다.

- P를 공이 최초로 시작에 돌아올 때까지 스위치들의 상태가 바뀐 총 횟수라고 하자. P는 20,000,000이 넘으면 안된다.

당신이 사용하는 스위치의 개수 S는 S ≤ N + log₂N 을 만족하여야 한다.

Mechanical Doll timer 1s memory 256MB

Mechanical Doll 1s 256MB