Recover the Dice Count
National Olympiad — Municipal round (2019 season)
Submission name: zar.cpp
Problem summary
Each throw of K standard dice produces a top sum A and bottom sum 7K−A. In the recorded bottom sum, every decimal digit except exactly one was changed, without changing the digit count or introducing a leading zero. Find every possible K consistent with all throws.
Input
N, followed by N pairs A[i], B[i], where B is the altered bottom sum.
Output
The number of possible dice counts, then the counts in increasing order.
Constraints
1 ≤ N ≤ 100; 1 ≤ A[i],B[i] ≤ 10,000; the input has at least one valid explanation.
Worked example
An independently prepared example for this explanation.
Input
4 23 192 50 92 111 24 62 68
Output
1 20
Solution analysis
- For K dice every top sum is between K and 6K. Thus it is sufficient to enumerate K from 1 to the smallest A[i], which is at most 10,000. For each row the true bottom sum is forced to be 7K−A[i].
- Check K≤A[i]≤6K, equal decimal lengths for the true and recorded bottom sums, and exactly one equal digit in corresponding positions. All other positions must differ; this is stronger than saying at least one digit survived.
- For the example K=20 gives true bottom sums 117,90,29,78. Against 192,92,24,68 each retains exactly one position. The remaining candidates fail at least one throw.
Why it works
The dice bound excludes exactly impossible top sums: all integers K…6K can be obtained by distributing an increment 0…5K across K dice. Opposite faces force the bottom sum to 7K−A. Equal length and exactly one matching digit are precisely the allowed corruption. Therefore a candidate passes every row exactly when it could have produced the entire record.
Watch out. Exactly one digit is unchanged, including in one-digit sums. Leading zeroes cannot be used to pad a shorter true number.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
// Algorithm: For K dice every top sum is between K and 6K.
using namespace std;
int main(){
int n;
cin>>n;
vector<int>top(n),altered(n);
int limit=10000;
for(int i=0;i<n;i++){
cin>>top[i]>>altered[i];
limit=min(limit,top[i]);
}
vector<int>answer;
for(int dice=1;dice<=limit;dice++){
bool possible=true;
for(int i=0;i<n&&possible;i++){
if(top[i]<dice||top[i]>6*dice){
possible=false;
break;
}
string original=to_string(7*dice-top[i]);
string recorded=to_string(altered[i]);
if(original.size()!=recorded.size()){
possible=false;
break;
}
int equal=0;
for(int j=0;j<static_cast<int>(original.size());j++){
equal+=original[j]==recorded[j];
}
possible=equal==1;
}
if(possible){
answer.push_back(dice);
}
}
cout<<answer.size()<<'\n';
for(int i=0;i<static_cast<int>(answer.size());i++){
cout<<(i?" ":"")<<answer[i];
}
cout<<'\n';
}