시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB169322015.385%

문제

높이가 H인 포화 이진 트리가 주어진다. 트리의 리프 노드들에는 순서대로 길이 N인 수열 P가 반복되어 나타나며, 부모 노드는 자신의 왼쪽 자식 노드와 오른쪽 자식 노드의 수열들을 순서대로 가지고 있다. 예를 들어, H가 4고 수열 P가 {2, 3, 1}이라면 트리는 아래의 그림처럼 형성된다.

우리는 어떤 특정 깊이 X에서 동일한 수열이 K번 이상 등장할 때 X의 최솟값을 구하려고 한다. 예를 들어, K=2일 때 깊이 3에서 수열 {2, 3}이 두번 등장하고, 그보다 더 작은 깊이에서는 두 번 이상 등장하는 수열이 존재하지 않으므로 최소 깊이는 3이 된다. 위 작업을 수행할 수 있는 프로그램을 작성하시오.

입력

첫째 줄에는 트리의 높이 H(3 ≤ H ≤ 63), 수열 P의 길이 N(1 ≤ N ≤ min(2H-1, 2 x 105)), K(1 ≤ K ≤ 2H-1)가 공백으로 구분되어 주어진다.

둘째 줄에는 수열 P의 원소를 나타내는 N개의 정수가 순서대로 공백으로 구분되어 주어지며, 이 값은 105을 넘지 않는 양의 정수이다.

출력

동일한 수열이 K번 이상 등장하는 최소 깊이를 출력하라. 만약 그러한 깊이가 존재하지 않는다면 -1을 출력하라.

예제 입력 1

4 3 2
2 3 1

예제 출력 1

3

예제 입력 2

4 8 1
1 2 3 4 5 6 7 8

예제 출력 2

1

예제 입력 3

3 4 2
2 7 5 4

예제 출력 3

-1

출처

Contest > BOJ User Contest > 네블컵 > 제2회 네블컵 F번