oj.uz

답안 #719244

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719244 2023-04-05T16:48:33 Z nihaddhuseynli Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 2 ms 388 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
ll dp[10][10][20][2];
string str;

// all : all digits are allowed
ll Calc(int first, int second, int len, bool all){
    if(len>=str.length()){
        return 1;
    }else{
        if(dp[first][second][len][all]==-1){
            ll help= 0;
            
            if(all){
                for(int n=0;n<=9;n++){
                    if(n!=first && n!=second){
                        help+=Calc(second,n, len+1, true);
                    }
                }
            }else{
                int limit = str[len]-'0';
                for(int n=0;n<limit;n++){
                    if(n!=first && n!=second){
                        help+=Calc(second, n, len+1,true);
                    }
                }
                if(limit!=first && limit!=second){
                    help+=Calc(second, limit, len+1,false);
                }
            }
            dp[first][second][len][all]=help;
        }
        return dp[first][second][len][all];
    }
}

ll Get(ll num){
        if(num<0) return 0;
        
        stringstream ss; ss << num; str = ss.str();
        
        memset(dp,-1,sizeof(dp));
        
        int first = str[0]-'0';
        ll res =1;
            
        for(int n=1;n<=first;n++){
            res+=Calc(n,n,1,n!=first);
        }
        
        for(int k=2;k<=str.length();k++){
            for(int n=1;n<10;n++){
                res+=Calc(n,n,k,true);
            }
        }
        
        return res;
}
int main(){
    ll a,b;
    scanf("%lld %lld",&a,&b);
    ll counter = Get(b)-Get(a-1);
    printf("%lld\n",counter);
}

Compilation message

numbers.cpp: In function 'long long int Calc(int, int, int, bool)':
numbers.cpp:10:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if(len>=str.length()){
      |        ~~~^~~~~~~~~~~~~~
numbers.cpp: In function 'long long int Get(long long int)':
numbers.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int k=2;k<=str.length();k++){
      |                     ~^~~~~~~~~~~~~~
numbers.cpp: In function 'int main()':
numbers.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%lld %lld",&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 300 KB Output is correct
16 Correct 1 ms 240 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 388 KB Output is correct
15 Correct 1 ms 300 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 308 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 304 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 300 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 304 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 2 ms 300 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 1 ms 308 KB Output is correct
40 Correct 1 ms 308 KB Output is correct
41 Correct 1 ms 300 KB Output is correct
42 Correct 1 ms 304 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 1 ms 300 KB Output is correct
45 Correct 1 ms 212 KB Output is correct