← 返回题目列表

Codeforces · 1857/B

B. 最大舍入

中文机器翻译题面 查看原题

给定一个自然数$$$x$$$。您可以执行以下操作:

- 选择一个正整数 $$$k$$$ 并将 $$$x$$$ 舍入到第 $$$k$$$ 位

请注意,位置从右到左编号,从零开始。如果数字有$$$k$$$位,则认为第$$$k$$$位的数字等于$$$0$$$。

舍入如下:

- 如果第 $$$(k-1)$$$ 位的数字大于或等于 $$$5$$$,则第 $$$k$$$ 位的数字增加 $$$1$$$,否则第 $$$k$$$ 位的数字保持不变(使用数学舍入)。
- 如果在操作之前第 $$$k$$$ 位的数字是 $$$9$$$,并且应该增加 $$$1$$$,那么我们搜索最小位置 $$$k'$$$ ($$$k'>k$$$),其中第 $$$k'$$$ 位的数字小于 $$$9$$$ 并将 $$$1$$$ 添加到第 $$$k'$$$ 位的数字。然后我们分配$$$k=k'$$$。
- 之后,所有位置小于 $$$k$$$ 的数字都被替换为零。

如果您可以根据需要多次执行该操作,则您的任务是使 $$$x$$$ 尽可能大。

例如,如果 $$$x$$$ 等于 $$$3451$$$,那么如果连续选择:

- $$$k=1$$$,则运算后$$$x$$$将变为$$$3450$$$
- $$$k=2$$$,则运算后$$$x$$$将变为$$$3500$$$
- $$$k=3$$$,则运算后$$$x$$$将变为$$$4000$$$
- $$$k=4$$$,则运算后$$$x$$$将变为$$$0$$$

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例由正整数 $$$x$$$ 组成,长度最大为 $$$2 \cdot 10^5$$$。确保整数中没有前导零。

保证所有测试用例中所有整数 $$$x$$$ 的长度总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每组输入数据,运算后输出$$$x$$$的最大可能值。该数字在其表示形式中不应有前导零。

示例

输入 #1

10
1
5
99
913
1980
20444
20445
60947
419860
40862016542130810467

输出 #1

1
10
100
1000
2000
20444
21000
100000
420000
41000000000000000000

注意

在第一个示例中,最好不要执行任何操作。

在第二个示例中,您可以执行一次操作并获得$$$10$$$。

在第三个示例中,您可以选择 $$$k=1$$$ 或 $$$k=2$$$。在这两种情况下,答案都是 $$$100$$$。