폴리매스

전구는 그 자신과 연결된 스위치가 켜지면 불이 들어옵니다.

현재 원형파이와 버블몬은 서로 벽을 두고 서 있습니다. (그림 참고)

왼쪽이 버블몬이고 오른쪽이 원형파이라 합시다.

버블몬쪽의 벽에는 스위치가, 원형파이쪽의 벽에는 전구가 있습니다.

전구 하나당 정확히 스위치는 한 개 뿐이고, 스위치 하나당 정확히 전구 한 개 뿐입니다.

전구와 스위치의 쌍은 N개 있습니다.

(네모 = 스위치, 동그라미 = 전구)

각 스위치와 전구에는 번호가 있습니다.

스위치와 전구 각각 1~N까지의 번호를 가집니다.

여기서 T번 스위치를 누르면 T번 전구의 불이 켜집니다.

이 때 밖에서 보이지는 않지만, 같은 번호를 따라 전깃줄이 연결됩니다.

여러분은 최대한 많은 전구의 빛이 들어오도록 해야 합니다.

그러나 만약 벽 내부에서 스위치를 누른 전깃줄끼리 교차하면 모든 스위치와 전구, 전깃줄이 폭발하여 실패합니다.

이 예시의 경우, 아래와 같은 스위치를 누르는 것이 해답이 될 수 있습니다.

여러분에게는 N과 버블몬에게 주어진 스위치의 배열(위 예시에서는 2 1 3 4)와 원형파이에게 주어진 전구의 배열(위 예시에서는 1 2 3 4)가 주어집니다.

원형파이가 볼 수 있는 최대의 빛이 들어온 전구의 개수와 그 때 빛이 들어오는 전구의 번호를 구합니다.

(1)

N = 5

2 4 1 5 3

4 5 1 3 2

(2)

N = 20

3 1 4 8 10 5 7 6 9 2 20 14 15 13 11 17 12 19 16 18

18 17 14 8 10 5 7 6 9 20 2 4 15 13 11 1 12 19 3 16

(3)

N = 10

1 9 6 4 8 2 3 7 5 10

5 1 8 7 2 3 4 9 6 10

(4)

N = 10

4 5 10 3 2 1 7 8 9 6

1 2 3 4 5 6 7 8 9 10