找出伪币
题目描述
给你一个装有 $n$ 枚硬币的袋子。$n$ 枚硬币中有一个是伪造的,并且那个伪造的硬币和真的硬币重量不一样。你的任务是找出这枚伪造的硬币。
为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,比如天平。利用这台仪器,可以知道两组硬币的重量是否相同。
输入输出格式
输入格式
第一行,一个正整数 $T$,表示有 $T$ 组数据。
接着 $T$ 行,每行三个正整数 $k,p,n$。
$p=-1$:伪币偏轻;$p=1$:伪币偏重;$p=0$:你不知道伪币与真币的重量对比关系。
$n$ 为一个 $k$ 位十进制正整数(没有前导 $0$)。
输出格式
输出 $T$ 行,每行一个整数 $m$,表示至少要称量 $m$ 次就一定能找出伪币。
输入输出样例
输入样例 #1
2
1 1 6
1 0 6
输出样例 #1
2
3
说明
对于 $40\%$ 的数据,$n\leq 10^5$。
对于 $100\%$ 的数据,$k\leq 10^4$,$3\lt n\lt 10^{10001}$,$1\leq T\leq 40$。
当 $p=0$ 时,你还需要知道伪币与真币相比是轻是重