Roundabout Rounding

题目描述

奶牛 Bessie 又回到学校了！她开始做数学作业，其中要求她把正整数四舍五入到 $10$ 的幂。 要把正整数 $a$ 四舍五入到最接近的 $10^b$（其中 $b$ 为正整数），Bessie 会先找到从右往左数第 $b$ 位数字。令 $x$ 表示这一位数字。 如果 $x \geq 5$，Bessie 就给 $a$ 加上 $10^b$。 然后，Bessie 将从右往左数第 $b$ 位及其右边的所有数字都设为 $0$。 例如，如果 Bessie 想把 $456$ 四舍五入到最接近的 $10^2$（百位），她会先找到从右往左数第 $2$ 位数字是 $5$，即 $x = 5$。由于 $x \geq 5$，她给 $a$ 加上 $100$。最后，她把 $a$ 中从右往左数第 $2$ 位及其右边的所有数字设为 $0$，得到 $500$。 然而，如果 Bessie 要把 $446$ 四舍五入到最接近的 $10^2$，她会得到 $400$。 看了 Bessie 的作业后，Elsie 认为她发明了一种新的取整方式：链式四舍五入（chain rounding）。要链式四舍五入到最接近的 $10^b$，Elsie 会先四舍五入到最接近的 $10^1$，再四舍五入到最接近的 $10^2$，依此类推，直到四舍五入到最接近的 $10^b$。 Bessie 认为 Elsie 是错的，但她忙于数学作业无法验证自己的怀疑。她让你统计有多少个整数 $x$ 满足 $2 \le x \le N$（$1 \leq N \leq 10^{9}$），使得将 $x$ 四舍五入到最接近的 $10^P$ 的结果与将 $x$ 链式四舍五入到最接近的 $10^P$ 的结果不同，其中 $P$ 是满足 $10^P \geq x$ 的最小整数。

输入格式

你需要回答多组测试用例。 输入第一行包含一个整数 $T$（$1 \leq T \leq 10^5$），表示测试用例数。接下来是 $T$ 个测试用例。 每个测试用例的第一行也是唯一一行，包含一个整数 $N$。同一输入文件中的所有 $N$ 保证互不相同。

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。 每行应为一个整数，表示在 $2$ 到 $N$ 之间（含端点）有多少个整数在两种取整方法下得到的结果不同。

4
1
100
4567
3366

0
5
183
60

提示

考虑样例中的第二个测试用例。应当计入 $48$，因为将 $48$ 链式四舍五入到最接近的 $10^2$ 会得到 $100$（$48\to 50\to 100$），但将 $48$ 直接四舍五入到最接近的 $10^2$ 会得到 $0$。 在第三个测试用例中，被计入的两个整数是 $48$ 和 $480$。$48$ 链式四舍五入会得到 $100$ 而不是 $0$，并且 $480$ 链式四舍五入会得到 $1000$ 而不是 $0$。然而，$67$ 不被计入，因为它链式四舍五入得到 $100$，这与将 $67$ 四舍五入到最接近的 $10^2$ 的结果相同。 SCORING: Inputs 2-4: $N\le 10^3$ Inputs 5-7: $N\le 10^6$ Inputs 8-13: 无额外限制。 Problem credits: Weiming Zhou

标签: USACO|2024|Bronze

来源

USACO|2024|Bronze