n명의 사람에게 n개의 선물을 공평하고 무작위로 나눠야 하는 상황을 생각해 보겠습니다. 이를 위해 아시아에서 널리 사용되는 한 가지 고대 기술이 있는데, 이는 일반적으로 무작위 순열을 나타내는 데 사용됩니다. 중국에서는 이를 귀신다리(畫鬼腳), 일본에서는 부처제비(あみだくじ), 그리고 한국에서는 사다리놀이(使階利)라고 부릅니다. 먼저 몇 가지 용어부터 살펴보겠습니다. 이 사다리는 여러 개의 수직 막대와 두 개의 인접한 수직 막대를 연결하는 수평 막대로 구성되어 있습니다. 각 수직 막대의 꼭대기에서 시작하여 다음 세 단계를 통해 사다리를 따라 경로를 추적합니다.

수직 막대를 따라갈 때는 첫 번째 막대의 끝에 도달할 때까지 아래로 계속 이동한 다음 막대를 따라 계속 진행합니다.
막대를 따라갈 때는 막대 끝에 도달할 때까지 계속 따라간 다음, 수직 막대를 따라 계속 내려가세요.
수직 막대의 바닥에 도달할 때까지 1단계와 2단계를 반복합니다.

그림 D.1(a)는 세 개의 수직 막대와 세 개의 막대를 가진 사다리 L을 보여줍니다. 수직 막대는 왼쪽에서 오른쪽으로 1, …, n으로 번호가 매겨져 있습니다. 이 세 개의 수직 막대를 따라가는 경로는 (b), (c), (d)에 나와 있습니다. 입력 (1, 2, 3)은 사다리 L에 의해 최종적으로 πL = (3, 2, 1)로 순열됩니다. 두 개의 인접한 수평 막대가 특정 지점에서 만나는 경우(그림 D.1(e)의 w처럼)는 해당 지점에서 따라가는 고유한 방법이 없으므로 허용하지 않습니다.

순열 πL을 이루는 사다리 L이 주어졌습니다. 특정 막대를 포함하는 막대 집합을 제거한 후에도 순열 πL이 변하지 않으면, 해당 막대는 πL에 대해 중복된다고 합니다. πL에 대해 모든 중복 막대를 찾는 것이 과제입니다. 이는 L에서 모든 중복 막대를 제거하여 최소 사다리를 구성하는 것과 같습니다. L의 최소 사다리에서, 사다리에서 공집합이 아닌 막대 집합을 제거하면 πL과 다른 순열이 생성됩니다.

#4387 upload 11 done 1 how_to_reg 1

Ladder Game timer 1s memory 512MB

#4387

Ladder Game 1s 512MB