Favourite 13
National Olympiad — Municipal round
Submission name: Lubimec13.cpp
Problem summary
Count the input numbers from which deleting zero or more digits can leave 13. A 1 must precede a later 3; they need not be adjacent.
Input
N, followed by N decimal integers.
Output
The count, or exactly No when it is zero.
Constraints
1 < N < 100; 1 < each value < 100,000,000,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
4 130 31 10203 400
Output
2
Solution analysis
- Read numbers as strings.
- Remember whether a 1 has been seen; a later 3 makes the number qualify.
- Count qualifying numbers once each.
Why it works
The scan succeeds exactly when keeping one earlier 1 and one later 3 produces 13.
Complexity: O(total digits) time; O(maximum input length) space.
Watch out. Looking only for the substring 13 is too restrictive.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The scan succeeds exactly when keeping one earlier 1 and one later 3 produces 13.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
int n;
cin>>n;
int answer=0;
while(n--){
string s;
cin>>s;
bool one=false,ok=false;
for(char c:s){
if(c=='3'&&one){
ok=true;
}
if(c=='1'){
one=true;
}
}
answer+=ok;
}
if(answer){
cout<<answer<<'\n';
}
else{
cout<<"No\n";
}
}