왼쪽 접시와 오른쪽 접시가 있는 특별한 양팔 저울이 있고, 두 접시는 처음에 모두 비어 있다. 또한 서로 동일한 1그램 구슬이 들어 있는 상자가 있다. 구슬은 총 N개이며 1번부터 N번까지 번호가 매겨져 있다.

이 저울은 매우 민감해서, 어느 순간이든 왼쪽 접시의 총 무게와 오른쪽 접시의 총 무게 차이가 1그램을 엄격히 초과하면 저울이 부서진다. 예를 들어 어느 순간 한쪽 접시에 구슬이 4개 있다면, 다른 쪽 접시에는 3개, 4개, 또는 5개의 구슬이 있어야 한다.

친구 리브라(Libra)는 당신에게 다음을 저울을 한 번도 부수지 않고 해 보라고 도전했다:

먼저 1번 구슬, 2번 구슬, ... , N번 구슬 순서대로 모든 구슬을 하나씩 저울 위에 올린다. 각 구슬마다 왼쪽 접시에 올릴지 오른쪽 접시에 올릴지 당신이 선택한다.
그 다음 친구가 정해 준 순서 A₁, A₂, ..., A_N에 따라 구슬을 하나씩 저울에서 모두 제거한다. 이 순서는 1, 2, ..., N의 순열이다. i번째로 제거하는 구슬은 번호가 A_i인 구슬이어야 한다.

이를 수행할 수 있는 방법을 찾아라.

불균형 방지 timer 20s memory 1024MB

불균형 방지 20s 1024MB