Boring Apartment Calls
National Olympiad — Regional round (2025 season)
Submission name: boring.cpp
Problem summary
An apartment number is boring if all its digits are equal. Among apartments 1…N, a child calls all boring numbers made of digit 1 in increasing order, then digit 2, and so on through digit 9. He stops immediately after calling K, which is guaranteed boring. Count calls including K.
Input
N and K on separate lines.
Output
The number of apartments called.
Constraints
1 ≤ N ≤ 10^9; 1 ≤ K ≤ N; K has equal digits.
Worked example
An independently prepared example for this explanation.
Input
100 22
Output
4
Solution analysis
- Only nine choices of repeated digit and at most ten lengths are relevant. Generate each digit’s numbers by value=10·value+digit, starting from the digit itself.
- Enumerate digits from 1 through 9, and for each digit enumerate its boring numbers while they do not exceed N. Increment the call count and stop when the generated value equals K.
- For N=100,K=22, the calls are 1,11,2,22. The number 111 is skipped because it exceeds N, so K is the fourth call.
Why it works
For each digit, repeated appending generates exactly its equal-digit apartment numbers in increasing order. The nested loops follow the prescribed digit order and exclude numbers above N. Stopping after K therefore counts exactly the calls made.
Watch out. The call order is not global numerical order. Include the final apartment K and use long long when appending another digit.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long n, k;
cin >> n >> k;
int calls = 0;
for (int digit = 1; digit <= 9; digit++) {
// Appending the same digit generates this digit group in calling order.
for (long long value = digit; value <= n; value = value * 10 + digit) {
calls++;
if (value == k) {
cout << calls << '\n';
return 0;
}
}
}
}