AT_abc290_g.[ABC290G] Edge Elimination

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一颗满 $K$ 叉树，深度为 $D$ ，即整棵树有 $1+K+K^2+\dots+K^D$ 个节点。

现在你可以选定若干条边并将其删除（也可以选择不删）。删除后将得到一个森林。求使森林中存在一棵树的节点数为 $X$ 的最小删除边数。

输入格式

第一行一个整数 $T$ ，表示有 $T$ 组数据。

接下来 $T$ 行，每行三个整数 $D,K,X$ 。中间用空格隔开。

输出格式

输出共 $T$ 行，每组数据输出一行。对于每组数据，输出最少要删除的边数。

输入输出样例

输入#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

说明/提示

数据范围

$ 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} $

输入解题思路，AI测评打分。不知道怎么写?

首页