oj.uz

Submission #217311

# Submission time Handle Problem Language Result Execution time Memory
217311 2020-03-29T11:51:17 Z KoalaMuch Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 6 ms 384 KB 
#include<bits/stdc++.h>
using namespace std;
long long dp[21][10][10];
long long s[21];
long long cal(long long num,long long ret = 0)
{
    if(num<=9)  return num+1;
    memset(dp,0,sizeof dp);
    long long n = ((long long)log10(num))+1;
    for(long long i=n;i>=1;i--,num/=10)   s[i] = num%10;
    long long st = 1e9;
    for(long long i=2;i<=n;i++)
    {
        if(s[i]==s[i-1])    st = min(st,i);
        if(i>2&&s[i]==s[i-2])   st = min(st,i);
    }
    for(long long i=1;i<s[1];i++)   for(long long j=0;j<=9;j++) dp[2][i][j] = i!=j;
    for(long long i=0;i<=s[2];i++)  dp[2][s[1]][i] = s[1]!=i;
    for(long long i=2;i<=n-1;i++)
    {
        for(long long j=0;j<=9;j++)
        {
            for(long long k=0;k<=9;k++)
            {
                for(long long l=0;l<=9;l++)
                {
                    if(j==l||k==l)  continue;
                    dp[i+1][k][l]+=dp[i][j][k];
                    if(i<st&&j==s[i-1]&&k==s[i]&&l>s[i+1]) --dp[i+1][k][l];
                }
            }
        }
    }
    for(long long i=0;i<=9;i++)   for(long long j=0;j<=9;j++)   ret+=dp[n][i][j];
    return ret;
}
long long split(long long n,long long ret = 0)
{
    for(long long st=9,i=0;i<=17;++i,st = st*10+9)
    {
        if(n<=st)   return ret+cal(n);
        ret+=cal(st);
    }
    return ret+cal(n);
}
int main()
{
    long long l,r;
    scanf("%lld %lld",&l,&r);
    long long ans = split(r);
    if(l)   ans-=split(l-1);
    printf("%lld\n",ans);
    return 0;
}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&l,&r);
     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 256 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 380 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 5 ms 384 KB Output is correct
38 Correct 5 ms 384 KB Output is correct
39 Correct 5 ms 384 KB Output is correct
40 Correct 5 ms 384 KB Output is correct
41 Correct 5 ms 384 KB Output is correct
42 Correct 5 ms 384 KB Output is correct
43 Correct 5 ms 384 KB Output is correct
44 Correct 5 ms 384 KB Output is correct
45 Correct 5 ms 384 KB Output is correct