fork download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <deque>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <ctime>
  20. #include <cstring>
  21.  
  22. using namespace std;
  23.  
  24. #define fori(i, n) for (int i=0; i<n; ++i)
  25. #define forr(i, a, n) for (int i=a; i<=n; ++i)
  26.  
  27. #define tipo unsigned long long
  28.  
  29. typedef vector<int> vi;
  30. typedef vector<vi> vtrio;
  31. typedef pair<int, int> par;
  32.  
  33. tipo dp[11][11], fim[11], sub[11], counted[2][11];
  34. tipo res;
  35.  
  36.  
  37. int num(char c){
  38.     return ((c - '0') % 48);
  39. }
  40.  
  41. tipo count(char numero[], int comeco){
  42.    int t = strlen(numero);
  43.    if (comeco >= t) return 0;
  44.    int d = t - comeco;
  45.    int p = num(numero[comeco]);
  46.  
  47.    for (int i = 1; i<p; i++)
  48.      fim[i] += pow (10, d-1);
  49.  
  50.    tipo qt_zeros = dp[0][d]/9 - dp[0][d-1];
  51.    //printf("|%llu|\n", qt_zeros);
  52.    fim[0] += qt_zeros*(p-1);
  53.  
  54.    for (int i = 1; i < 10; i++) fim[i] += (p-1)*counted[1][d];
  55.  
  56.    if (d>1){
  57.      char resto[d-1];
  58.      int start = comeco+1;
  59.  
  60.      if (numero[start]!='0'){
  61.        fim[0] += p*pow(10,d-2);
  62.        int k =0;
  63.        for (int i = start; i<t; i++) resto[k++] = numero[i];	
  64.        resto[k] = 0;
  65.        fim[p] += atoi(resto)+1;
  66.      }else{
  67.      	int n_zeros = 0;
  68.      	while(numero[start]=='0'){ n_zeros++; start++;}
  69.      	int k =0;
  70.         for (int i = start; i<t; i++) resto[k++] = numero[i];	
  71.         resto[k] = 0;
  72.      	fim[0] += n_zeros* atoi(resto) +n_zeros;
  73.      	fim[p] += atoi(resto)+1;
  74.      }
  75.      return count(numero, start);
  76.    }else
  77.     fim[p]++;
  78.  
  79.    return 0;
  80. }
  81.  
  82. void memo(){
  83.  
  84.  for (int d = 2; d < 10; d++){
  85.   for (int i = 1; i < d; i++)
  86.    dp[0][d] += pow(10, d-(i+1)) * pow(9, i-1);
  87.   dp[0][d] *= 9;
  88.   dp[0][d] += dp[0][d-1];
  89.  }
  90.  
  91.  for (int d = 2; d <= 9; d++){
  92.  	tipo below = 0;
  93.  	for (int i = 1; i < d; i++)
  94.       below += pow(10, d-i-1) * pow(9, i-1);
  95.     counted[1][d] = below;
  96.  	for (int i = 1; i<10; i++)
  97.  		dp[i][d] += 9*below + pow(10,d-1) + dp[i][d-1];
  98.  }
  99.  
  100. }
  101.  
  102. int main(){
  103.  memset(dp, 0, sizeof dp);
  104.  memset(counted, 0, sizeof counted);
  105.  for (int n = 1; n<10; n++)
  106.   dp[n][1] = 1;
  107.  
  108.  memo();
  109.  while(1){
  110.   char a[20], b[20];
  111.   scanf("%s %s", a, b);
  112.  
  113.   if (a[0]=='0') break;
  114.   else{
  115.    count(b,0);
  116.    for (int i =0; i < strlen(a); i++) fim[num(a[i])]++;
  117.    for (int i = 0; i < 10; i++){
  118.     sub[i] = fim[i] + dp[i][strlen(b)-1];
  119.     fim[i]=0;
  120.    }
  121.  
  122.    count(a,0);
  123.  
  124.    for (int i=0; i<10;i++){
  125.     sub[i] -= (fim[i] + dp[i][strlen(a)-1]);
  126.     fim[i] = 0;
  127.     if (i==0)
  128.      printf("%llu",sub[0]);
  129.     else
  130.      printf(" %llu",sub[i]); 
  131.    }
  132.    printf("\n");
  133.   }
  134.  }
  135.  return 0;
  136. }
Success #stdin #stdout 0s 3352KB
comments (?)
stdin
copy 
1 9
12 321
5987 6123
12345678 12345679
0 0
stdout
copy 
0 1 1 1 1 1 1 1 1 1
63 166 160 80 58 58 58 58 58 58
31 37 7 3 2 15 126 3 6 26
0 2 2 2 2 2 2 2 1 1
https://ideone.com/AwXeZh
language:
C++ (gcc 8.3)
created:
9 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!