이진 트리와 수열
시간 제한3초메모리 제한256 MB
주기적인 잎 문자열이 붙은 완전 이진 트리에서 어떤 노드의 문자열이 K번 이상 나타나는 최소 깊이를 찾습니다.
문제
높이가 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 10^5)), K(1 ≤ K ≤ 2H-1)가 공백으로 구분되어 주어진다.
둘째 줄에 수열 P의 원소 N개가 순서대로 공백으로 구분되어 주어지며, 각 값은 10^5을 넘지 않는 양의 정수이다.
출력
같은 수열이 K번 이상 나타나는 최소 깊이를 출력하라. 그러한 깊이가 존재하지 않으면 -1을 출력하라.