A16127. Maximum Rounding
编程题
普及/提高-
知识点
题目描述
Given a natural number $x$ . You can perform the following operation:
- choose a positive integer $k$ and round $x$ to the $k$ -th digit
Note that the positions are numbered from right to left, starting from zero. If the number has $k$ digits, it is considered that the digit at the $k$ -th position is equal to $0$ .
The rounding is done as follows:
- if the digit at the $(k-1)$ -th position is greater than or equal to $5$ , then the digit at the $k$ -th position is increased by $1$ , otherwise the digit at the $k$ -th position remains unchanged (mathematical rounding is used).
- if before the operations the digit at the $k$ -th position was $9$ , and it should be increased by $1$ , then we search for the least position $k'$ ( $k'>k$ ), where the digit at the $k'$ -th position is less than $9$ and add $1$ to the digit at the $k'$ -th position. Then we assign $k=k'$ .
- after that, all digits which positions are less than $k$ are replaced with zeros.
Your task is to make $x$ as large as possible, if you can perform the operation as many times as you want.
For example, if $x$ is equal to $3451$ , then if you choose consecutively:
- $k=1$ , then after the operation $x$ will become $3450$
- $k=2$ , then after the operation $x$ will become $3500$
- $k=3$ , then after the operation $x$ will become $4000$
- $k=4$ , then after the operation $x$ will become $0$
To maximize the answer, you need to choose $k=2$ first, and then $k=3$ , then the number will become $4000$ .
- choose a positive integer $k$ and round $x$ to the $k$ -th digit
Note that the positions are numbered from right to left, starting from zero. If the number has $k$ digits, it is considered that the digit at the $k$ -th position is equal to $0$ .
The rounding is done as follows:
- if the digit at the $(k-1)$ -th position is greater than or equal to $5$ , then the digit at the $k$ -th position is increased by $1$ , otherwise the digit at the $k$ -th position remains unchanged (mathematical rounding is used).
- if before the operations the digit at the $k$ -th position was $9$ , and it should be increased by $1$ , then we search for the least position $k'$ ( $k'>k$ ), where the digit at the $k'$ -th position is less than $9$ and add $1$ to the digit at the $k'$ -th position. Then we assign $k=k'$ .
- after that, all digits which positions are less than $k$ are replaced with zeros.
Your task is to make $x$ as large as possible, if you can perform the operation as many times as you want.
For example, if $x$ is equal to $3451$ , then if you choose consecutively:
- $k=1$ , then after the operation $x$ will become $3450$
- $k=2$ , then after the operation $x$ will become $3500$
- $k=3$ , then after the operation $x$ will become $4000$
- $k=4$ , then after the operation $x$ will become $0$
To maximize the answer, you need to choose $k=2$ first, and then $k=3$ , then the number will become $4000$ .
输入格式
The first line contains a single integer $t$ ( $1\le t\le 10^4$ ) — the number of test cases.
Each test case consists of positive integer $x$ with a length of up to $2 \cdot 10^5$ . It is guaranteed that there are no leading zeros in the integer.
It is guaranteed that the sum of the lengths of all integers $x$ over all test cases does not exceed $2 \cdot 10^5$ .
Each test case consists of positive integer $x$ with a length of up to $2 \cdot 10^5$ . It is guaranteed that there are no leading zeros in the integer.
It is guaranteed that the sum of the lengths of all integers $x$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each set of input data, output the maximum possible value of $x$ after the operations. The number should not have leading zeros in its representation.
输入输出样例
输入 #1
10 1 5 99 913 1980 20444 20445 60947 419860 40862016542130810467
输出 #1
1 10 100 1000 2000 20444 21000 100000 420000 41000000000000000000
说明/提示
In the first sample, it is better not to perform any operations.
In the second sample, you can perform one operation and obtain $10$ .
In the third sample, you can choose $k=1$ or $k=2$ . In both cases the answer will be $100$ .
In the second sample, you can perform one operation and obtain $10$ .
In the third sample, you can choose $k=1$ or $k=2$ . In both cases the answer will be $100$ .