Informatica Online Judge

  좀 더 새로운 트리 순회 [1295 / 050F]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 29   Total Tried : 34


The Champion of this Problem (C++) : gs13068 - 0ms / 695byte
My Best Submission (C++) : N/A

[koistudy.net (32nd 백승진)]

Background

완전 $N$진 트리에서 단말 노드들 중에서 원하는 $K$ 노드를 찾기 위해 필요한 방문 노드의 수를 찾는 문제이다.

한번은 $i$번째 노드를 방문하면 다음번은 $i+1$번째 노드 방문하기를 무한히 반복하여 원하는 단말노드를 찾는다.
(단, 어떤 노드를 방문할 때마다 $i$는 1씩 증가한다. 그리고 $i$의 값의 범위는 $1≤i≤n$이며 $n$ 다음 수는 다시 $1$이 된다.)

(0) 루트 노드에서 방문을 시작한다. 이 때 $i = 1$ 이다.
(1) 자식 노드를 방문할 때의 순서는 현재 $i$값에 의해 결정되며, 왼쪽으로부터 $i$번째 자식노드를 방문한다.
(2) 방문한 단말 노드가 찾는 단말 노드가 아니면 현재 노드의 부모 노드로 돌아간다.
(3) 방문한 단말 노드가 찾는 단말 노드이면 종료한다.


예를 들어 완전 4진 트리가 주어진다면 아래 그림과 같은 방문의 순서가 결정된다.





트리의 높이 H는 0부터 시작된다.

또한, 찾고자 하는 단말노드는 $1$에서부터 $N^H$까지로 매겨질 때, 단말노드의 번호 $K$를 찾을 때까지 방문한 노드의 수를 출력하는 프로그램을 작성하시오.

Input

세 정수 $N,H,K$가 각각 한 줄로 주어진다.
$N$과 $H$는 $10$진수, $K$는 $N$진수 형태로 주어진다.
자리수가 $10$보다 클 경우, $10$은 $A$, $11$은 $B$, ..., $35$는 $Z$로 주어진다.

[입력값의 정의역]
$2≤N≤36$
$1≤H≤10,000$
$1≤K≤N^H$

[SubTask Info]
#1 : (25%) $N=2$
#2 : (25%) $N^H≤10,000,000$
#3 : (50%) 다른 제약 조건이 없다.

Output

단말노드 $K$를 찾는데 필요한 방문 노드수를 $N$진수 형태로 출력한다.

IO Example

입력 1
4
2
12

출력 1
22

입력 2
4
2
32

출력 2
102

입력 3
12
2
A3

출력 3
B3

입력 4
26
20
9I3HOO98K1M3GL0N9IO9

출력 4
9I2FMM75GNHOAEJG19F9


Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]