#1269. [USACO 2024 DEC Bronze A] Roundabout Rounding
[USACO 2024 DEC Bronze A] Roundabout Rounding
题目描述
奶牛 Bessie 回到学校了!她开始做她的数学作业,在作业中她被要求将正整数四舍五入到 的幂。
要将一个正整数 四舍五入到最接近的 ,其中 为正整数,Bessie 首先找到从右往左数第 个数位。令 为这个数位。
如果 ,Bessie 将 增加 。
然后,Bessie 将从右侧开始直至第 个数位的所有数位均设置为 。
例如,如果 Bessie 想要将 四舍五入到最接近的 (百位),Bessie 会首先找到从右往左数第 个数位 。这意味着 。然后由于 ,Bessie 将 增加 。最后,Bessie 将 中从右侧开始直至第 个数位的所有数位设置为 ,结果为 。
但是,如果 Bessie 将 四舍五入到最接近的 ,她将得到 。
在看了 Bessie 的作业后,Elsie 认为她已经发明了一种新的舍入方式:链式舍入。要链式舍入到最接近的 ,Elsie 将首先舍入到最接近的 ,然后舍入到最接近的 ,以此类推,直至舍入到最接近的 。
Bessie 认为 Elsie 是错误的,但她太忙于数学作业,无法确认她的怀疑。她请你计算出存在多少个不小于 且不超过 的整数 (),使得将 四舍五入到最接近的 与链式舍入到最接近的 的结果不同,其中 是满足 的最小整数。
输入格式
你需要回答多个测试用例。
输入的第一行包含一个整数 (),为测试用例的数量。以下是 个测试用例。
每个测试用例的输入仅有一行,包含一个整数 。输入保证同一测试点中的所有 各不相同。
输出格式
输出 行,第 行包含第 个测试用例的答案。每行包含一个整数,表示存在多少个不小于 且不超过 的整数在使用两种舍入方法时会得到不同的结果。
样例解释
考虑样例中的第二个测试用例。 应当被计算在内,因为 链式舍入到最接近的 是 (),但 四舍五入到最接近的 是 。
在第三个测试用例中, 和 是两个被计算在内的整数。 链式舍入到 而不是 , 链式舍入到 而不是 。但是, 不被计算在内,因为它链式舍入到 ,与 四舍五入到最接近的 相同。
数据范围
测试点 :样例。
测试点 :。
测试点 :。
测试点 :没有额外限制。