fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <map>
  5. #include <cstring>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. int a, b, n;
  11. vector<int> y;
  12. int dp[12][12][12][2];
  13.  
  14. void splitNumber(int x){
  15.   while(x != 0){
  16.     y.push_back(x % 10);
  17.     x /= 10;
  18.   }
  19.   reverse(y.begin(), y.end());
  20. }
  21.  
  22. int solve(int i, int qtd, int leftmost_lo, int leftmost_hi, int x, int numero){
  23.   int result = 0;
  24.   if(i == n){
  25.     if(leftmost_lo <= leftmost_hi){
  26.       return qtd;
  27.     }else{
  28.       return 0;//max(0, qtd - 1);
  29.     }
  30.   }
  31.  
  32.   /*int &ret = dp[i][leftmost_lo][leftmost_hi][numero != 0];
  33.  
  34.   if(ret != -1)
  35.     return ret;*/
  36.  
  37.   for(int d = 0; d <= 9; d++){
  38.     int lm_lo = leftmost_lo;
  39.     int lm_hi = leftmost_hi;
  40.  
  41.     if(d < y[i] && i < lm_lo){
  42.       lm_lo = i;
  43.     }
  44.     if(d > y[i] && i < lm_hi){
  45.       lm_hi = i;
  46.     }
  47.  
  48.     int novo_numero = numero*10 + d;
  49.  
  50.     if(d == 0 and !numero){
  51.       result += solve(i + 1, qtd, lm_lo, lm_hi, x, novo_numero);
  52.     }else
  53.       result += solve(i + 1, qtd + (x == d), lm_lo, lm_hi, x, novo_numero);
  54.   }
  55.  
  56.   return result; //ret = result;
  57. }
  58.  
  59.  
  60. int main(){
  61.   while(scanf("%d %d", &a, &b) && (a || b)){
  62.     y.clear();
  63.     int ans[10] = {0};
  64.     splitNumber(a - 1);
  65.     n = (int) y.size();
  66.  
  67.     for(int i = 0; i <= 9; i++){
  68.       memset(dp, -1, sizeof dp);
  69.       int ret = solve(0, 0, n, n, i, 0);
  70.       ans[i] = ret;
  71.       //printf("%d ", ans[i]);
  72.     }
  73.     //puts("");
  74.     y.clear();
  75.     splitNumber(b);
  76.     n = (int) y.size();
  77.     for(int i = 0; i <= 9; i++){
  78.       memset(dp, -1, sizeof dp);
  79.       int qtd = solve(0, 0, n, n, i, 0);
  80.       ans[i] = qtd - ans[i];
  81.       printf("%d ", ans[i]);
  82.     }
  83.     puts("");
  84.   }
  85.   return 0;
  86. }
  87.  
Time limit exceeded #stdin #stdout 5s 15240KB
comments (?)
stdin
copy 
1 9
12 321
5987 6123
12345678 12345679
0 0
stdout
copy 
Standard output is empty
https://ideone.com/AOwBpQ
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!