oj.uz

Submission #31914

# Submission time Handle Problem Language Result Execution time Memory
31914 2017-09-14T10:30:49 Z chonka Palindrome-Free Numbers (BOI13_numbers) C++
100 / 100
 0 ms 2064 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;

long long st , en ;

long long dp[ 22 ][ 12 ][ 12 ][ 2 ] ;

vector < int > get ( long long x ) {
    vector < int > aux ;
    while ( x != 0 ) {
        aux.push_back ( ( x % 10 ) ) ;
        x /= 10 ;
    }
    vector < int > ret ;
    int i ;
    int sz = aux.size ( ) ;
    for ( i = sz - 1 ; i >= 0 ; i -- ) {
        ret.push_back ( aux[ i ] ) ;
    }
    return ret ;
}

long long f ( long long x ) {
    if ( x < 0 ) { return 0 ; }
    vector < int > v = get ( x ) ;
    int i , j , t , z , p ;
    int n = v.size ( ) ;
    for ( i = 0 ; i <= n ; i ++ ) {
        for ( j = 0 ; j <= 10 ; j ++ ) {
            for ( t = 0 ; t <= 10 ; t ++ ) {
                for ( z = 0 ; z < 2 ; z ++ ) {
                    dp[ i ][ j ][ t ][ z ] = 0 ;
                }
            }
        }
    }
    dp[ 0 ][ 10 ][ 10 ][ 1 ] = 1 ;
    for ( i = 0 ; i < n ; i ++ ) {
        for ( j = 0 ; j <= 10 ; j ++ ) {
            for ( t = 0 ; t <= 10 ; t ++ ) {
                for ( z = 0 ; z < 2 ; z ++ ) {
                    if ( dp[ i ][ j ][ t ][ z ] == 0 ) { continue ; }
                    if ( j == 10 && t == 10 ) {
                        dp[ i + 1 ][ j ][ t ][ 0 ] += dp[ i ][ j ][ t ][ z ] ;
                    }
                    if ( z == 0 ) {
                        for ( p = 0 ; p <= 9 ; p ++ ) {
                            if ( p == j || p == t ) { continue ; }
                            if ( t == 10 && p == 0 ) { continue ; }
                            dp[ i + 1 ][ t ][ p ][ 0 ] += dp[ i ][ j ][ t ][ z ] ;
                        }
                    }
                    else {
                        for ( p = 0 ; p <= v[ i ] ; p ++ ) {
                            if ( p == j || p == t ) { continue ; }
                            if ( t == 10 && p == 0 ) { continue ; }
                            int id = 0 ;
                            if ( p == v[ i ] ) { id = 1 ; }
                            dp[ i + 1 ][ t ][ p ][ id ] += dp[ i ][ j ][ t ][ z ] ;
                        }
                    }
                }
            }
        }
    }
    long long ret = 0 ;
    for ( j = 0 ; j <= 10 ; j ++ ) {
        for ( t = 0 ; t <= 10 ; t ++ ) {
            for ( z = 0 ; z < 2 ; z ++ ) {
                ret += dp[ n ][ t ][ j ][ z ] ;
            }
        }
    }
    return ret ;
}

void input ( ) {
    cin >> st >> en ;
}

void solve ( ) {
    printf ( "%lld\n" , f ( en ) - f ( st - 1 ) ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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