Submission #31913

#	Time	Username	Problem	Language	Result	Execution time	Memory
31913		chonka	Palindrome-Free Numbers (BOI13_numbers)	C++98	96.25 / 100	0 ms	2064 KiB

numbers

#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 ) {
    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: 21.25 / 25
• Subtask 2: 75 / 75