102906: [Atcoder]ABC290 G - Edge Elimination
Description
Score : $600$ points
Problem Statement
Solve the following problem for $T$ test cases.
We have a perfect $K$-ary tree of depth $D$ (with $1+K+K^2+\dots+K^D$ vertices).
Your objective is to cut some of the edges to obtain a connected component with exactly $X$ vertices.
At least how many edges must be cut to achieve the objective?
Constraints
- All values in the input are integers.
- $1 \le T \le 100$
- $1 \le D$
- $2 \le K$
- $\displaystyle 1 \le X \le \sum_{i=0}^{D} K^i \le 10^{18}$
Input
The input is given from Standard Input in the following format:
$T$ $case_1$ $\vdots$ $case_T$
Here, $case_i$ denotes the $i$-th test case.
Each test case is given in the following format:
$D$ $K$ $X$
Output
Print $T$ lines.
The $i$-th line should contain the answer to the $i$-th test case as an integer.
Sample Input 1
11 2 2 1 2 2 2 2 2 3 2 2 4 2 2 5 2 2 6 2 2 7 1 999999999999999999 1 1 999999999999999999 2 1 999999999999999999 999999999999999999 1 999999999999999999 1000000000000000000
Sample Output 1
1 2 1 1 2 1 0 1 999999999999999998 1 0
Input
题意翻译
#### 题目描述 给定一颗满 $K$ 叉树，深度为 $D$，即整棵树有 $1+K+K^2+\dots+K^D$ 个节点。 现在你可以选定若干条边并将其删除（也可以选择不删）。删除后将得到一个森林。求使森林中存在一棵树的节点数为 $X$ 的最小删除边数。 #### 输入格式 第一行一个整数 $T$，表示有 $T$ 组数据。 接下来 $T$ 行，每行三个整数 $D,K,X$。中间用空格隔开。 #### 输出格式 输出共 $T$ 行，每组数据输出一行。对于每组数据，输出最少要删除的边数。 @[robinyqc](https://www.luogu.com.cn/user/338632) 翻译。Output
分数：$600$ 分
问题描述
为$T$个测试用例解决以下问题。
我们有一个深度为$D$的完美$K$-ary树（有$1+K+K^2+\dots+K^D$个顶点）。
你的目标是剪掉一些边，得到一个恰好有$X$个顶点的连通分量。
要实现目标，至少需要剪掉多少条边？
约束条件
- 输入中的所有值都是整数。
- $1 \le T \le 100$
- $1 \le D$
- $2 \le K$
- $\displaystyle 1 \le X \le \sum_{i=0}^{D} K^i \le 10^{18}$
输入
输入从标准输入按以下格式给出：
$T$ $case_1$ $\vdots$ $case_T$
其中，$case_i$表示第$i$个测试用例。
每个测试用例按以下格式给出：
$D$ $K$ $X$
输出
打印$T$行。
第$i$行应包含第$i$个测试用例的答案，即一个整数。
样例输入 1
11 2 2 1 2 2 2 2 2 3 2 2 4 2 2 5 2 2 6 2 2 7 1 999999999999999999 1 1 999999999999999999 2 1 999999999999999999 999999999999999999 1 999999999999999999 1000000000000000000
样例输出 1
1 2 1 1 2 1 0 1 999999999999999998 1 0