Advertisement
Guest User

Untitled

a guest
May 27th, 2016
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None | 0 0
  1. #include <cstdio>
  2.  
  3. long long memo[19];
  4.  
  5. long long f(int K){
  6.     if(K <= 1){
  7.         return 0;
  8.     }
  9.    
  10.     if(memo[K] != -1){
  11.         return memo[K];
  12.     }
  13.    
  14.     long long ret = 0, aux = 1;
  15.     for(int i=0; i<K-2; i++) aux *= 10;
  16.    
  17.     for(int i=0; i<=9; i++){
  18.         ret += (9-i)*aux + f(K-2);
  19.     }
  20.    
  21.     return memo[K] = ret;
  22. }
  23.  
  24. int main(){
  25.     for(int i=0; i<=18; i++){
  26.         memo[i] = -1;
  27.     }
  28.    
  29.     int K;
  30.     while(scanf("%d", &K) > 0){
  31.         if(K <= 1){
  32.             printf("0\n");
  33.             continue;
  34.         }
  35.        
  36.         long long ans = 0, aux = 1;
  37.         for(int i=0; i<K-2; i++) aux *= 10;
  38.        
  39.         for(int i=1; i<=9; i++){
  40.             ans += (9-i)*aux + f(K-2);
  41.         }
  42.        
  43.         printf("%lld\n", ans);
  44.     }
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement