Numbers and Digits
National Olympiad — Municipal round (2013 season)
Submission name: num012.cpp
Problem summary
For each of three positive integers N>1, decide whether every decomposition N=A+B into positive integers has a digit 0,1,or 2 in at least one summand. Output 1 when this universal condition holds, and 0 when a decomposition using only digits 3..9 exists.
Input
Three lines, each containing one N.
Output
Three lines, one binary answer per input number.
Constraints
Each N has at most 18 decimal digits.
Worked example
Official statement sample.
Input
5 19 18
Output
1 1 0
Solution analysis
- Search for the opposite condition: two positive integers containing only digits 3..9 that add to N. Add from the units digit upward using a small DP over the carry and two flags indicating whether each summand has already ended.
- At the units position both summands must select a digit 3..9, guaranteeing positivity. At every later position an unfinished summand may choose another such digit or end by contributing zero. Once ended, it contributes zero forever. Keep transitions whose sum digit matches the corresponding digit of N.
- After all digits, a reachable state with carry zero is a valid forbidden-digit-free decomposition. For 18, choosing 9+9 reaches that state and the output is 0. Neither 5 nor 19 has such a decomposition, so each produces 1.
Why it works
The flags allow exactly ordinary finite positive decimal numbers over digits 3..9, with zero padding only above their most significant digit. The carry recurrence is exact decimal addition. Thus a final zero-carry state exists exactly when the desired counterexample to the universal condition exists.
Watch out. Do not treat leading zero padding as a forbidden digit inside a summand. Output is inverted: existence of an allowed pair means 0.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main(){
for(int test=0;test<3;++test){
string s;
cin>>s;
// State: carry, whether summand A ended, whether summand B ended.
bool dp[2][2][2]={};
dp[0][0][0]=true;
for(int pos=0;pos<static_cast<int>(s.size());++pos){
bool next[2][2][2]={};
int target=s[s.size()-1-pos]-'0';
for(int carry=0;carry<2;++carry){
for(int endedA=0;endedA<2;++endedA){
for(int endedB=0;endedB<2;++endedB){
if(!dp[carry][endedA][endedB]){
continue;
}
for(int a=0;a<=9;++a){
if((endedA&&a!=0)||(!endedA&&(a==1||a==2))||
(pos==0&&a==0)){
continue;
}
for(int b=0;b<=9;++b){
if((endedB&&b!=0)||(!endedB&&(b==1||b==2))||
(pos==0&&b==0)){
continue;
}
int sum=a+b+carry;
if(sum%10==target){
next[sum/10][endedA||a==0][endedB||b==0]=true;
}
}
}
}
}
}
memcpy(dp,next,sizeof(dp));
}
bool exists=false;
for(int a=0;a<2;++a){
for(int b=0;b<2;++b){
exists=exists||dp[0][a][b];
}
}
cout<<(exists?0:1)<<'\n';
}
}