oj.uz

Submission #63327

# Submission time Handle Problem Language Result Execution time Memory
63327 2018-08-01T12:31:52 Z Bodo171 Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 3 ms 892 KB 
#include <iostream>
#include <fstream>
using namespace std;
long long cif[20];
long long dp[20][11][11][2];
int i,j,c1,c2,newc,eq,len;
long long val,a,b;
long long calc(long long x)
{
    if(x<0) return 0;
    if(x==0) return 1;
    int nr=0;
    cif[0]=10;
    while(x!=0)
        cif[++nr]=x%10,x/=10;len=nr;
    for(i=1;i<=nr/2;i++)
        swap(cif[i],cif[nr-i+1]);
    for(i=1;i<cif[1];i++)
        dp[1][10][i][0]=1;
    dp[1][10][cif[1]][1]=1;
    for(i=2;i<=len;i++)
        for(j=1;j<10;j++)
           dp[i][10][j][0]=1;
    for(i=1;i<len;i++)
        for(c1=0;c1<=10;c1++)
          for(c2=0;c2<10;c2++)
            for(eq=0;eq<=1;eq++)
    {
        val=dp[i][c1][c2][eq];
        if(val)
        {
            if(eq)
         {
            for(newc=0;newc<cif[i+1];newc++)
                if(newc!=c1&&newc!=c2)
                    dp[i+1][c2][newc][0]+=val;
            if(cif[i+1]!=c1&&cif[i+1]!=c2)
               dp[i+1][c2][cif[i+1]][1]+=val;
         }
         else
         {
            for(newc=0;newc<10;newc++)
                if(newc!=c1&&newc!=c2)
                dp[i+1][c2][newc][0]+=val;
         }
        }
    }
    long long sum=0;
    for(i=0;i<=10;i++)
       for(j=0;j<10;j++)
          sum+=dp[len][i][j][0];
    sum+=dp[len][cif[len-1]][cif[len]][1];
    for(i=1;i<=len;i++)
        for(c1=0;c1<=10;c1++)
           for(c2=0;c2<=10;c2++)
             for(eq=0;eq<2;eq++)
                dp[i][c1][c2][eq]=0;
    return sum+1;//numaram si 0
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>a>>b;
    cout<<calc(b)-calc(a-1)<<'\n';
    return 0;
}

Compilation message

numbers.cpp: In function 'long long int calc(long long int)':
numbers.cpp:14:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     while(x!=0)
     ^~~~~
numbers.cpp:15:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
         cif[++nr]=x%10,x/=10;len=nr;
                              ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 2 ms 500 KB Output is correct
7 Correct 2 ms 552 KB Output is correct
8 Correct 2 ms 616 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 624 KB Output is correct
11 Correct 2 ms 628 KB Output is correct
12 Correct 2 ms 628 KB Output is correct
13 Correct 2 ms 636 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 652 KB Output is correct
18 Correct 2 ms 652 KB Output is correct
19 Correct 2 ms 668 KB Output is correct
20 Correct 2 ms 668 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 668 KB Output is correct
2 Correct 2 ms 672 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 688 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 2 ms 712 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 728 KB Output is correct
11 Correct 2 ms 736 KB Output is correct
12 Correct 2 ms 736 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 2 ms 752 KB Output is correct
15 Correct 2 ms 776 KB Output is correct
16 Correct 2 ms 776 KB Output is correct
17 Correct 2 ms 780 KB Output is correct
18 Correct 2 ms 784 KB Output is correct
19 Correct 3 ms 788 KB Output is correct
20 Correct 2 ms 792 KB Output is correct
21 Correct 3 ms 796 KB Output is correct
22 Correct 3 ms 800 KB Output is correct
23 Correct 2 ms 804 KB Output is correct
24 Correct 3 ms 808 KB Output is correct
25 Correct 2 ms 812 KB Output is correct
26 Correct 2 ms 816 KB Output is correct
27 Correct 2 ms 816 KB Output is correct
28 Correct 3 ms 828 KB Output is correct
29 Correct 2 ms 828 KB Output is correct
30 Correct 2 ms 832 KB Output is correct
31 Correct 2 ms 832 KB Output is correct
32 Correct 2 ms 832 KB Output is correct
33 Correct 3 ms 844 KB Output is correct
34 Correct 2 ms 848 KB Output is correct
35 Correct 2 ms 848 KB Output is correct
36 Correct 2 ms 860 KB Output is correct
37 Correct 2 ms 860 KB Output is correct
38 Correct 3 ms 864 KB Output is correct
39 Correct 2 ms 864 KB Output is correct
40 Correct 2 ms 872 KB Output is correct
41 Correct 3 ms 876 KB Output is correct
42 Correct 2 ms 880 KB Output is correct
43 Correct 2 ms 884 KB Output is correct
44 Correct 2 ms 884 KB Output is correct
45 Correct 2 ms 892 KB Output is correct