#include <bits/stdc++.h>
#define ll long long
using namespace std;
string x;
ll dp[10][10][20][2];
ll a, b;
ll recursion(int first, int second, int position, bool f) {
if(position >= x.length()) {
return 1;
}
else {
if(dp[first][second][position][f] == -1) {
ll sum = 0;
if(f) {
for(int i=0;i<=9;i++) {
if(i!=first && i!=second)
sum += recursion(second, i, position+1, f);
}
}
else {
int temp = x[position] - '0';
for(int i=0;i<temp;i++) {
if(i!=first && i!=second) {
sum += recursion(second,i,position+1, true);
}
}
if(temp!=first && temp!=second) {
sum += recursion(second,temp,position+1,false);
}
}
dp[first][second][position][f] = sum;
}
return dp[first][second][position][f];
}
}
ll solve(ll y) {
stringstream ss; ss << y; x = ss.str();
memset(dp,-1,sizeof(dp));
ll result = 1;
int temp = x[0]-'0';
for(int i=1;i<=temp;i++) {
result += recursion(i,i,1,i!=temp);
}
for(int i=2;i<=x.length();i++) {
for(int j=1;j<10;j++) {
result += recursion(j,j, i, true);
}
}
return result;
}
int main() {
cin>>a>>b;
cout<<solve(b)-solve(a-1)<<"\n";
return 0;
}
Compilation message
numbers.cpp: In function 'long long int recursion(int, int, int, bool)':
numbers.cpp:9:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(position >= x.length()) {
^
numbers.cpp: In function 'long long int solve(long long int)':
numbers.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=2;i<=x.length();i++) {
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
612 KB |
Output is correct |
| 3 |
Correct |
2 ms |
612 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
612 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
612 KB |
Output is correct |
| 6 |
Correct |
1 ms |
612 KB |
Output is correct |
| 7 |
Correct |
1 ms |
612 KB |
Output is correct |
| 8 |
Correct |
1 ms |
612 KB |
Output is correct |
| 9 |
Correct |
1 ms |
696 KB |
Output is correct |
| 10 |
Correct |
1 ms |
696 KB |
Output is correct |
| 11 |
Correct |
1 ms |
720 KB |
Output is correct |
| 12 |
Correct |
1 ms |
720 KB |
Output is correct |
| 13 |
Correct |
2 ms |
724 KB |
Output is correct |
| 14 |
Incorrect |
1 ms |
760 KB |
Output isn't correct |
| 15 |
Correct |
1 ms |
776 KB |
Output is correct |
| 16 |
Correct |
1 ms |
780 KB |
Output is correct |
| 17 |
Correct |
1 ms |
784 KB |
Output is correct |
| 18 |
Incorrect |
1 ms |
792 KB |
Output isn't correct |
| 19 |
Correct |
2 ms |
792 KB |
Output is correct |
| 20 |
Correct |
1 ms |
796 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
800 KB |
Output is correct |
| 2 |
Correct |
2 ms |
804 KB |
Output is correct |
| 3 |
Correct |
2 ms |
916 KB |
Output is correct |
| 4 |
Correct |
2 ms |
916 KB |
Output is correct |
| 5 |
Correct |
1 ms |
916 KB |
Output is correct |
| 6 |
Correct |
1 ms |
916 KB |
Output is correct |
| 7 |
Correct |
2 ms |
916 KB |
Output is correct |
| 8 |
Correct |
1 ms |
916 KB |
Output is correct |
| 9 |
Correct |
1 ms |
916 KB |
Output is correct |
| 10 |
Correct |
1 ms |
916 KB |
Output is correct |
| 11 |
Correct |
2 ms |
916 KB |
Output is correct |
| 12 |
Correct |
1 ms |
916 KB |
Output is correct |
| 13 |
Correct |
1 ms |
916 KB |
Output is correct |
| 14 |
Correct |
2 ms |
916 KB |
Output is correct |
| 15 |
Correct |
1 ms |
916 KB |
Output is correct |
| 16 |
Correct |
2 ms |
916 KB |
Output is correct |
| 17 |
Correct |
2 ms |
916 KB |
Output is correct |
| 18 |
Correct |
2 ms |
916 KB |
Output is correct |
| 19 |
Correct |
2 ms |
916 KB |
Output is correct |
| 20 |
Correct |
2 ms |
916 KB |
Output is correct |
| 21 |
Correct |
2 ms |
916 KB |
Output is correct |
| 22 |
Correct |
2 ms |
916 KB |
Output is correct |
| 23 |
Correct |
2 ms |
916 KB |
Output is correct |
| 24 |
Correct |
2 ms |
916 KB |
Output is correct |
| 25 |
Correct |
2 ms |
916 KB |
Output is correct |
| 26 |
Correct |
2 ms |
916 KB |
Output is correct |
| 27 |
Correct |
2 ms |
916 KB |
Output is correct |
| 28 |
Correct |
2 ms |
916 KB |
Output is correct |
| 29 |
Correct |
2 ms |
916 KB |
Output is correct |
| 30 |
Correct |
2 ms |
924 KB |
Output is correct |
| 31 |
Correct |
2 ms |
928 KB |
Output is correct |
| 32 |
Correct |
2 ms |
928 KB |
Output is correct |
| 33 |
Correct |
2 ms |
932 KB |
Output is correct |
| 34 |
Correct |
2 ms |
936 KB |
Output is correct |
| 35 |
Correct |
2 ms |
940 KB |
Output is correct |
| 36 |
Correct |
2 ms |
944 KB |
Output is correct |
| 37 |
Correct |
2 ms |
944 KB |
Output is correct |
| 38 |
Correct |
2 ms |
952 KB |
Output is correct |
| 39 |
Correct |
2 ms |
956 KB |
Output is correct |
| 40 |
Correct |
2 ms |
992 KB |
Output is correct |
| 41 |
Correct |
2 ms |
996 KB |
Output is correct |
| 42 |
Correct |
2 ms |
1000 KB |
Output is correct |
| 43 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 44 |
Correct |
2 ms |
1008 KB |
Output is correct |
| 45 |
Correct |
2 ms |
1008 KB |
Output is correct |
