oj.uz

Submission #624858

# Submission time Handle Problem Language Result Execution time Memory
624858 2022-08-08T21:40:04 Z chonka Palindrome-Free Numbers (BOI13_numbers) C++
100 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

vector < int > v ;

ll dp[ 22 ][ 123 ][ 2 ] ;

ll f ( ll up ) {
    if ( up < 0 ) { return 0 ; }
    v.clear ( ) ;
    while ( up > 0 ) {
        v.push_back ( up % 10 ) ;
        up /= 10 ;
    }
    reverse ( v.begin ( ) , v.end ( ) ) ;
    int n = v.size ( ) ;
    for ( int i = 0 ; i <= n ; ++ i ) {
        for ( int j = 0 ; j <= 121 ; ++ j ) {
            for ( int t = 0 ; t < 2 ; ++ t ) {
                dp[ i ][ j ][ t ] = 0 ;
            }
        }
    }
    dp[ 0 ][ 120 ][ 1 ] = 1 ;
    for ( int i = 0 ; i < n ; ++ i ) {
        for ( int j = 0 ; j <= 120 ; ++ j ) {
            int x = ( j / 11 ) , y = ( j % 11 ) ;
            for ( int t = 0 ; t < 2 ; ++ t ) {
                if ( dp[ i ][ j ][ t ] == 0 ) { continue ; }
                for ( int z = 0 ; z <= 10 ; ++ z ) {
                    if ( z == 10 ) {
                        if ( y != 10 ) { continue ; }
                        dp[ i + 1 ][ j ][ 0 ] += dp[ i ][ j ][ t ] ;
                    }
                    else {
                        if ( z == 0 && y == 10 ) { continue ; }
                        if ( t == 1 && z > v[ i ] ) { continue ; }
                        int nwt = t ;
                        if ( z < v[ i ] ) { nwt = 0 ; }

                        if ( z == x || z == y ) { continue ; }
                        int nwj = z + 11 * y ;
                        dp[ i + 1 ][ nwj ][ nwt ] += dp[ i ][ j ][ t ] ;
                    }
                }
            }
        }
    }
    ll ret = 0 ;
    for ( int i = 0 ; i <= 120 ; ++ i ) {
        ret += dp[ n ][ i ][ 0 ] + dp[ n ][ i ][ 1 ] ;
    }
    return ret ;
}

void solve ( ) {
    ll l , r ;
    cin >> l >> r ;
    cout << f ( r ) - f ( l - 1 ) << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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