Chewbacca
레이팅 미적용의견: 0
\(4^{th}\) round, December \(19^{th}\) 2015
You are given a tree of order \(K\) with \(N\) nodes or, in other words, each node can have at most \(K\)
children. The tree is constructed so it’s of the "lowest energy": the nodes are placed in a new depth
of the tree only when all the places (from left to right) in the previous depth have been filled. This is
also the order of enumerating the nodes, starting with 1. Image depicts an example of a tree of order
3 with 9 nodes.
You need to output answers to \(Q\) queries in the form of \(x\) \(y\), where the answer is the minimal number
of steps needed to get from node \(x\) to node \(y\).
In test cases worth 20% of total points, it will hold 1 ⩽N, Q ⩽1 000.
In test cases worth 50% of total points, it will hold 1 ⩽N, Q ⩽100 000.
The first line of input contains the integers \(N\) (1 ⩽\(N\) ⩽\(10^{15}\)), \(K\) (1 ⩽\(K\) ⩽1 000) i \(Q\) (1 ⩽\(Q\) ⩽
100 000) from the task.
Each of the following \(Q\) lines contains pairs \(xy\) (1 ⩽x, y ⩽N, x̸ = \(y\)) from the task.
Output \(Q\) lines, each line containing the answer to a query from the task.
7 2 3
1 2
2 1
4 7
9 3 3
8 9
5 7
8 4output
1
1
4
2
2
3Clarification of the first example: You are given a complete binary tree. Node 2 is a direct child of node
1 so the distance between them is exactly 1. Nodes 4 and 7 are on complete opposite sides of the tree, so the
distance between them is 4: 4 →2 →1 →3 →7.
Clarification of the second example: This example corresponds to the image.
평가 및 의견
Chewbacca
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Chewbacca