CompleteTreeLabeling

원문보기

---

인기도:C(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:2(1~4)

About CompleteTreeLabeling

Input	standard input
Output	standard output
Time Limit	45 seconds
Memory Limit	32 MB

모든 잎(leaf)의 깊이가 같고 모든 내부 노드의 차수(degree)가 k인(즉 분기계수(branching factor)가 k인) 트리를 k진 완전 트리(complete k-ary tree)라고 한다. 그런 트리에 대해서는 노드의 개수를 쉽게 결정할 수 있다. k진 완전 트리의 깊이와 분기계수가 주어졌을 때 트리의 노드에 번호를 붙일 수 있는 모든 가능한 방법의 수를 결정해야 한다. 이때 각 노드의 레이블은 그 자손의 레이블보다 작아야 한다. 이진 힙 우선 순위 큐 자료 구조가 바로 이런 속성을 가진다(이진 트리이므로 k=2). N개의 노드가 있는 트리에 번호를 붙일 때, 1에서 N까지의 레이블을 붙일 수 있다고 가정하자.

Input

입력 파일은 여러 줄로 구성된다. 각 줄에는 두 개의 정수 k와 d가 들어있다. k>0이며, 이 값은 k진 완전 트리의 분기계수를 나타낸다. d>0며, k진 완전 트리의 깊이를 나타낸다. k X d ≤21인 모든 k와 d에 대해 작동하는 프로그램을 만들어야 한다.

Output

입력된 각 줄에 대해 한 줄의 결과를 출력한다. 그 줄에는 위에서 설명한 조건을 만족시키면서 k진 트리에 레이블을 붙이는 경우의 수를 출력한다.

Sample Input

2 2
10 1

Sample Output

80
3628800

풀이

작성자	사용언어	개발시간	코드
조현태	C	.	CompleteTreeLabeling/조현태
하기웅	C++	1시간 30분	CompleteTreeLabeling/하기웅

쓰레드

으아 너무어려워 ㅠㅠ

---

문제분류 AOI