#include<iostream>
#include<string>
#include<sstream>
using namespace std;
#define ll unsigned long long int
ll dp[19][10][10];
ll dp2[19];
ll dp1[19][10];
ll dp3[19][10];
ll dpz[19];
/*bool c(string a)
{
if (a.length()==1) return true;
if (a.length()==2) return true;
int N=a.length();
int i;
for (i=0;i<N-3;i++)
{
if (a[i] == a[i+1] || a[i] == a[i+2]) return false;
}
return true;
}*/
int num(char p)
{
switch(p)
{
case '0' : return 0;
case '1' : return 1;
case '2' : return 2;
case '3' : return 3;
case '4' : return 4;
case '5' : return 5;
case '6' : return 6;
case '7' : return 7;
case '8' : return 8;
case '9' : return 9;
}
}
ll f(int k, int i , int j)
{
if (dp[k][i][j] != -1) return dp[k][i][j];
ll p,q,val = 0;
if (j==0)
{
for (p=0;p<10;p++)
{
for (q=1;q<10;q++)
if ((q!=i)&&(q!=0)&&(p!=0))
val += f(k-2,q,p);
}
}
else
{
for (p=0;p<10;p++)
if (p!=j && p!=i)
val += f(k-1,j,p);
}
dp[k][i][j] = val;
return dp[k][i][j];
}
ll count(string a)
{
int i,N = a.length(),j,k,p;
if (N==1) return num(a[0]) - 1 ;
ll val = 0;//dp2[N-1]
if (N==2)
{
val = 9;
k = num(a[0])*10 + num(a[1]);
for (i=1;i<10;i++)
{
if (i>num(a[0])) break;
for (j=0;j<10;j++)
{
if (i==num(a[0]) && j==num(a[1])) break;
if (i!=j)
{
val++;
}
}
}
return val;
}
for (i=1;i<N;i++) val += dp2[i];
for (i=1;i<num(a[0]);i++) // doing the first digit upto a;
val += dp1[N][i];
for (i=0;i<num(a[1]);i++)
{
val += dp[N][num(a[0])][i];
}
//cout<<"Value calculated till now is "<<val<<endl;
for (k=N-2;k>0;k--)
{
//cout<<"looking from digit "<<N-k<<endl;
if ((a[N-k-2] == a[N-k-1])||(k<N-2&&a[N-k-1] == a[N-k-3])) return val;
else if (a[N-k-1] != '0')
for (i=0;i<num(a[N-k]);i++)
{
//cout<<"entered\n";
if (i != num(a[N-k-2]))
val += dp[k+1][num(a[N-k-1])][i];
}
else
for (i=1;i<num(a[N-k]);i++)
{
if (i != num(a[N-k-2]))
val += dp1[k][i] - dp[k][i][0];
}
//cout<<"Value calculated till now is "<<val<<endl;
/*else
{
p=num(a[N-k-2]);
val += dp2[k] - dp1[k][p] - dp3[k][0] + dp[k][p][0];
}*/
//cout<<"final value is "<<k<<" "<<dpz[k]<<endl;// - dp1[k][num(a[N-k-1])] - dp1[k][num(a[N-k-2])] - dp3[k][num(a[N-k-1])] + dp[k][num(a[N-k-2])][num(a[N-k-1])]<<endl<<endl;
}
if (a[N-2] != a[N-3])
for (i=0;i<num(a[N-1]);i++)
if (i!=num(a[N-2])&&i!=num(a[N-3]));// val++;
return val;
}
int main()
{
int i,j,k;
ll p;
for (j=0;j<10;j++)
for (i=1;i<10;i++)
{
dp[2][i][j] = (i==j) ? 0 : 1;
dp[3][i][j] = (i==j) ? 0 : 8;
}
for (k=4;k<19;k++)
for (j=0;j<10;j++)
for (i=1;i<10;i++)
dp[k][i][j]= (i==j) ? 0 : -1;
for (k=2;k<19;k++)
{
dp2[k] = 0;
}
dp2[1] = 9;
for (k=2;k<19;k++)
for (j=0;j<10;j++)
for (i=1;i<10;i++)
{
dp3[k][j] += f(k,i,j);
dp1[k][i] += f(k,i,j);
dp2[k] += f(k,i,j);
}
dp1[1][0] = 1;
dp1[2][0] = 9;
dpz[2] = 90;
dpz[1] = 10;
for (k=3;k<19;k++)
{
dp1[k][0] = dp2[k-1] - dp3[k-1][0];
dpz[k] = dp2[k] + dp1[k][0];
}
for (i=1;i<10;i++) dp1[1][i] = 1;
ostringstream st[2];
string a[2];
/*while (true){
cin>>a[0];
cout<<count (a[0])<<endl; }*/
//cout<<dp2[4]<<endl<<dp2[3];
cin>>a[0]>>p;
st[1]<<p+1;
a[1] = st[1].str();
cout<<count(a[1]) - count(a[0]);
return 0;
}
Compilation message
numbers.cpp: In function 'long long unsigned int f(int, int, int)':
numbers.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (dp[k][i][j] != -1) return dp[k][i][j];
~~~~~~~~~~~~^~~~~
numbers.cpp:48:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if ((q!=i)&&(q!=0)&&(p!=0))
~^~~
numbers.cpp:55:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (p!=j && p!=i)
~^~~
numbers.cpp:55:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (p!=j && p!=i)
~^~~
numbers.cpp: In function 'long long unsigned int count(std::__cxx11::string)':
numbers.cpp:64:27: warning: unused variable 'p' [-Wunused-variable]
int i,N = a.length(),j,k,p;
^
numbers.cpp: In function 'int num(char)':
numbers.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
0 ms |
384 KB |
Output is correct |
18 |
Correct |
0 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
384 KB |
Output is correct |
22 |
Correct |
1 ms |
384 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
1 ms |
384 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
1 ms |
384 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
0 ms |
384 KB |
Output is correct |
33 |
Correct |
0 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
1 ms |
384 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
38 |
Correct |
1 ms |
384 KB |
Output is correct |
39 |
Correct |
0 ms |
384 KB |
Output is correct |
40 |
Correct |
1 ms |
384 KB |
Output is correct |
41 |
Correct |
1 ms |
384 KB |
Output is correct |
42 |
Correct |
1 ms |
384 KB |
Output is correct |
43 |
Correct |
1 ms |
384 KB |
Output is correct |
44 |
Correct |
1 ms |
384 KB |
Output is correct |
45 |
Correct |
1 ms |
384 KB |
Output is correct |