Mechanical Doll timer 1초 memory 256MB

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

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

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

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

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

각 장치가 가질 수 있는 진입구의 개수에는 제한이 없다 (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 을 만족하여야 한다.​