Numbering the Sheep
National Olympiad — Regional round (2018 season)
Submission name: sheep.cpp
Problem summary
A shepherd numbers N sheep using increasing positive integers, skipping every number that contains a missing digit stamp. Given the missing digits, find the number assigned to the last sheep.
Input
N, then L, then the L missing digits.
Output
The N-th positive integer containing none of the missing digits.
Constraints
1 ≤ N ≤ 1000000; 1 ≤ L ≤ 3; missing digits are decimal digits.
Worked example
An independently prepared example for this explanation.
Input
10 1 1
Output
22
Solution analysis
- All valid numbers of a shorter length come before every valid number of a longer length. Let b be the number of available digits and f the number of available nonzero digits. There are f·b^(length−1) valid numbers of a given length.
- Subtract whole length blocks until N identifies a number within the remaining block. Change to a zero-based rank. At each digit position, each allowed digit starts an equally sized block of suffixes, so divide by that block size to choose the digit and use the remainder as the suffix rank.
- With digit 1 missing, the one-digit valid numbers are 2 through 9: eight choices. The tenth number is therefore the second two-digit choice. Those choices begin 20,22,23,…, so the answer is 22.
Why it works
The length counts enumerate exactly all valid numbers, excluding leading zero. Within a fixed length, numeric order equals lexicographic digit order. Dividing a rank into equal suffix blocks therefore chooses precisely the digit containing that rank; induction over the positions yields the required N-th number.
Watch out. Zero may be an available suffix digit but cannot be the first digit. Convert to a zero-based rank only after subtracting the shorter-length blocks.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
long long rank;
int lost;
cin >> rank >> lost;
array<bool, 10> missing{};
for (int i = 0; i < lost; ++i) {
int digit;
cin >> digit;
missing[digit] = true;
}
vector<int> digits;
vector<int> firstDigits;
for (int digit = 0; digit <= 9; ++digit) {
if (!missing[digit]) {
digits.push_back(digit);
if (digit != 0) {
firstDigits.push_back(digit);
}
}
}
long long suffixCount = 1;
int length = 1;
// Remove complete blocks of shorter valid numbers.
while (rank > static_cast<long long>(firstDigits.size()) * suffixCount) {
rank -= static_cast<long long>(firstDigits.size()) * suffixCount;
suffixCount *= static_cast<long long>(digits.size());
++length;
}
--rank;
cout << firstDigits[static_cast<size_t>(rank / suffixCount)];
rank %= suffixCount;
for (int position = 1; position < length; ++position) {
suffixCount /= static_cast<long long>(digits.size());
cout << digits[static_cast<size_t>(rank / suffixCount)];
rank %= suffixCount;
}
cout << '\n';
}