문제
모든 잎(leaf)의 깊이가 같고, 모든 내부 노드의 차수(degree)가 k인(즉, 분기계수가 k인) 트리를 k진 완전트리(complete k-ary tree)라고 한다.
그런 트리에 대해서는 노드의 개수를 쉽게 결정할 수 있다.
k진 완전 트리의 깊이와 분기계수가 주어졌을 때 트리의 노드에 번호를 붙일 수 있는 모든 가능한 방법의 수를 결정해야 한다.
이때 각 노드의 레이블은 자손의 레이블보다 작아야 한다.
이진 힙(binary heap)으로 이루어진 우선 순위 큐 자료 구조가 바로 이런 속성을 가진다(이진트리이므로 k=2).
N개의 노드가 있는 트리에 번호를 붙일 때 1에서 N까지의 레이블을 붙일 수 있다고 가정하자.
입력
입력은 여러 줄로 구성 된다. 각 줄에는 두 개의 정수 k와 d가 들어있다. k>0이며, 이 값은 k진 완전트리의 분기계수를 나타낸다. 또한 d>0며, k진 완전 트리의 깊이를 나타낸다. k×d≤21인 모든 k와 d에 대해 작동하는 프로그램을 만들어야 한다. k와 d에 0이 들어갈 경우 입력을 종료하며, 최대 1,000줄의 입력이 들어올 수 있다고 가정하자.
출력
입력된 각 줄에 대해 한 줄의 결과를 출력한다. 그 줄에는 위에서 설명한 조건을 만족시키면서 진 트리에 레이블을 붙이는 경우의 수를 출력한다.
예제1
입력
22
101
00
출력
80
3628800
출처
uva 10247 Complete Tree Labeling