레이팅 미적용소 베시(Bessie)가 학교로 돌아왔다! 베시는 양의 정수를 \(10\)의 거듭제곱으로 반올림하는 수학 숙제를 하기 시작했다.
양의 정수 \(a\)를 가장 가까운 \(10^b\)으로 반올림하기 위해(\(b\)는 양의 정수), 베시는 먼저 오른쪽에서 \(b\)번째 자리의 숫자를 찾는다. 이 숫자를 \(x\)라 하자.
\(x \geq 5\)이면, 베시는 \(a\)에 \(10^b\)을 더한다.
그 다음, 베시는 오른쪽에서 \(b\)번째 자리와 그 오른쪽의 모든 자릿수를 \(0\)으로 만든다.
예를 들어, 베시가 \(456\)을 가장 가까운 \(10^2\)(백의 자리)으로 반올림하려면, 먼저 오른쪽에서 \(2\)번째 자리의 숫자인 \(5\)를 찾는다. 즉 \(x = 5\)이다. \(x \geq 5\)이므로 베시는 \(a\)에 \(100\)을 더한다. 마지막으로 베시는 \(a\)에서 오른쪽에서 \(2\)번째 자리와 그 오른쪽의 모든 자릿수를 \(0\)으로 만들어 \(500\)을 얻는다.
반면 베시가 \(446\)을 가장 가까운 \(10^2\)으로 반올림하면 \(400\)이 된다.
베시의 숙제를 본 엘시(Elsie)는 자신이 새로운 반올림 방식을 발명했다고 생각한다. 바로 연쇄 반올림이다. 가장 가까운 \(10^b\)으로 연쇄 반올림을 하기 위해, 엘시는 먼저 가장 가까운 \(10^1\)로 반올림하고, 그 다음 가장 가까운 \(10^2\)으로, 이런 식으로 가장 가까운 \(10^b\)까지 반올림한다.
베시는 엘시가 틀렸다고 생각하지만, 수학 숙제로 너무 바빠서 자신의 의심을 확인할 수 없다. 베시는 \(2\) 이상 \(N\) (\(1 \leq N \leq 10^{9}\)) 이하의 정수 \(x\) 중에서, \(x\)를 가장 가까운 \(10^P\)으로 반올림한 결과와 가장 가까운 \(10^P\)으로 연쇄 반올림한 결과가 다른 것의 개수를 세는 일을 당신에게 맡겼다. 여기서 \(P\)는 \(10^P \geq x\)를 만족하는 가장 작은 정수이다.
문제 제공: Weiming Zhou
배점
- 입력 2-4: \(N\le 10^3\)
- 입력 5-7: \(N\le 10^6\)
- 입력 8-13: 추가 제약이 없다.
문제 제공: Weiming Zhou
여러 개의 테스트 케이스에 답해야 한다.
입력의 첫째 줄에는 테스트 케이스의 수를 나타내는 정수 \(T\) (\(1 \leq T \leq 10^5\))가 주어진다. 이어서 \(T\)개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫째 줄이자 유일한 줄에는 정수 \(N\)이 주어진다. 같은 입력 파일 안의 모든 \(N\)은 서로 다름이 보장된다.
\(T\)개의 줄을 출력하며, \(i\)번째 줄에는 \(i\)번째 테스트 케이스의 답을 출력한다. 각 줄은 두 반올림 방식의 결과가 서로 다른, \(2\) 이상 \(N\) 이하의 정수의 개수를 나타내는 정수여야 한다.
4
1
100
4567
33660
5
183
60Consider 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\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Bronze