답안 #99524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99524 2019-03-04T17:11:00 Z MohamedAhmed0 Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
5 ms 512 KB
#include <bits/stdc++.h>

using namespace std;

long long dp[19][2][2][11][11] ;
vector<int>v ;

long long cnt(int idx , bool f , bool f2 , int prv , int prv2)
{
    if(idx == v.size())
        return 1 ;
    long long &ret = dp[idx][f][f2][prv][prv2] ;
    if(ret != -1)
        return ret ;
    int LMT ;
    if(f)
        LMT = 9 ;
    else
        LMT = v[idx] ;
    ret = 0ll ;
    for(int i = 0 ; i <= LMT ; ++i)
    {
        int nf = f ;
        int nf2 = f2 ;
        if(i < LMT)
            nf = 1 ;
        if(i == prv || i == prv2)
            continue;
        if(i != 0)
            nf2 = 1 ;
        if(nf2 == 0)
            ret += cnt(idx+1 , nf , nf2 , 10 , 10) ;
        else
            ret += cnt(idx+1 , nf , nf2 , i , prv) ;
    }
    return ret ;
}
long long solve(long long x)
{
    if(x < 0)
        return 0 ;
    v.clear();
    memset(dp , -1 , sizeof(dp)) ;
    while(x > 0)
    {
        v.push_back(x % 10) ;
        x /= 10 ;
    }
    reverse(v.begin() , v.end()) ;
    long long ans = cnt(0 , 0 , 0 , 10 , 10) ;
    return ans ;
}

int main()
{
    long long a , b ;
    cin>>a>>b ;
    return cout<<solve(b) - solve(a-1)<<"\n" , 0 ;
}

Compilation message

numbers.cpp: In function 'long long int cnt(int, bool, bool, int, int)':
numbers.cpp:10:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(idx == v.size())
        ~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 380 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 3 ms 384 KB Output is correct
37 Correct 3 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 3 ms 384 KB Output is correct
40 Correct 3 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 3 ms 384 KB Output is correct
43 Correct 3 ms 384 KB Output is correct
44 Correct 3 ms 384 KB Output is correct
45 Correct 2 ms 428 KB Output is correct