USACO 2024 December Contest, Bronze
Problem 1. Roundabout Rounding
Contest has ended.
Log in to allow submissions in analysis mode
Bessie the cow is back in school! She has started doing her math homework in which she is tasked to round positive integers to powers of $10$.
To round a positive integer $a$ to the nearest $10^b$, where $b$ is a positive integer, Bessie first locates the $b$'th digit from the right. Let $x$ denote this digit.
If $x \geq 5$, Bessie adds $10^b$ to $a$.
Then, Bessie sets all the digits including and to the right of the $b$'th digit from the right to be $0$.
For instance, if Bessie wanted to round $456$ to the nearest $10^2$ (hundred), Bessie would first locate the $2$nd digit from the right which is $5$. This means $x = 5$. Then since $x \geq 5$, Bessie adds $100$ to $a$. Finally, Bessie sets all the digits in $a$ to the right of and including the $2$nd digit from the right to be $0$, resulting in $500$.
However, if Bessie were to round $446$ to the nearest $10^2$, she would end up with $400$.
After looking at Bessie's homework, Elsie thinks she has invented a new type of rounding: chain rounding. To chain round to the nearest $10^b$, Elsie will first round to the nearest $10^1$, then the nearest $10^2$, and so on until the nearest $10^b$.
Bessie thinks Elsie is wrong, but is too busy with math homework to confirm her suspicions. She tasks you to count how many integers $x$ at least $2$ and at most $N$ ($1 \leq N \leq 10^{9}$) exist such that rounding $x$ to the nearest $10^P$ is different than chain rounding to the nearest $10^P$, where $P$ is the smallest integer such that $10^P \geq x$.
INPUT FORMAT (input arrives from the terminal / stdin):
You have to answer multiple test cases.
The first line of input contains a single integer $T$ ($1 \leq T \leq 10^5$) denoting the number of test cases. $T$ test cases follow.
The first and only line of input in every test case contains a single integer $N$. All $N$ within the same input file are guaranteed to be distinct.
OUTPUT FORMAT (print output to the terminal / stdout):
Output $T$ lines, the $i$'th line containing the answer to the $i$'th test case. Each line should be an integer denoting how many integers at least $2$ and at most $N$ exist that are different when using the two rounding methods.
SAMPLE INPUT:
4 1 100 4567 3366
SAMPLE OUTPUT:
0 5 183 60
Consider the second test case in the sample. $48$ should be counted because $48$ chain rounded to the nearest $10^2$ is $100$ ($48\to 50\to 100$), but $48$ rounded to the nearest $10^2$ is $0$.
In the third test case, two integers counted are $48$ and $480$. $48$ chain rounds to $100$ instead of to $0$ and $480$ chain rounds to $1000$ instead of $0$. However, $67$ is not counted since it chain rounds to $100$ which is $67$ rounded to the nearest $10^2$.
SCORING:
- Inputs 2-4: $N\le 10^3$
- Inputs 5-7: $N\le 10^6$
- Inputs 8-13: No additional constraints.
Problem credits: Weiming Zhou