fork download 
  1. /*
  2.   プログラミングのお題スレ Part15
  3.   https://m...content-available-to-author-only...h.net/test/read.cgi/tech/1564310397/
  4.   
  5.   755デフォルトの名無しさん2019/10/12(土) 13:25:43.66ID:VvSWBOR5
  6.   >>748　言われた通りの改定問題
  7.  
  8.   X,Yが与えられる。
  9.   X以上Y以下の連続する整数で、数字和の頻度。
  10.   もっとも大きい頻度はいくつか。
  11.   制約 0 <= X < Y <= 5000億
  12.  
  13.   1) 0 9999 --> 670
  14.   　　合計18が、670ある。>>744の入力値
  15.   2) 1234567 9876543 --> 459034
  16.   3) 1 500000000000 --> 20406732610
  17.   4) 12345678909 498765432123 --> 20000965162
  18.  
  19.   ※Y-Xが MAX5000億なので愚直(力技)はきつい。
  20.   ※頻度表は"桁数*9"程度あるので、最高値出力のみに変更
  21. */
  22.  
  23. #include <stdio.h>
  24. #include <stdlib.h>
  25. #include <string.h>
  26.  
  27. #define MAXDIGIT 20
  28. #define MAXANUM ((MAXDIGIT*9) + 1)
  29. #define MAXXNUM ((MAXDIGIT+1)/2)
  30.  
  31. long long fact(int n){
  32.     long long p = 1;
  33.     while(n > 0){
  34.         p *= n;
  35.         n--;
  36.     }
  37.     return(p);
  38. }
  39. long long combi(int n, int k){
  40.     long long p = 1;
  41.     int i;
  42.     for(i = 0; i < k; i++){
  43.         p *= n--;
  44.     }
  45.     return(p / fact(k));
  46. }
  47.  
  48. void make_base(long long base[MAXDIGIT][MAXANUM]){
  49.     int i,j,k;
  50.     long long x[MAXXNUM];    
  51.     int curdigit, curanum, curhalfanum, curxnum;
  52.  
  53.     for(i = 0; i < MAXDIGIT; i++){
  54.         for(j = 0; j < MAXANUM; j++){
  55.             base[i][j] = 0;
  56.         }
  57.     }
  58.  
  59.     for(i = 0; i < MAXDIGIT; i++){
  60.         curdigit = i+1;
  61.         curanum = (curdigit*9)+1;
  62.         curhalfanum = (curdigit*9)/2+1;
  63.         curxnum = (curdigit+1)/2;
  64.  
  65.         for(j = 0; j < curxnum; j++){
  66.             if(j % 2 == 1){
  67.                 x[j] = -combi(curdigit-1,j);
  68.             }else{
  69.                 x[j] = combi(curdigit-1,j);
  70.             }
  71.         }
  72.         for(j = 0; j < curhalfanum; j++){
  73.             base[i][j] = x[j/10];
  74.         }    
  75.         for(j = 1; j < curdigit; j++){
  76.             for(k = 1; k < curhalfanum; k++){
  77.                 base[i][k] = base[i][k] + base[i][k-1];
  78.             }
  79.         }
  80.         if(curdigit % 2 == 1){
  81.             j = curhalfanum - 1;
  82.         }else{
  83.             j = curhalfanum - 2;
  84.         }
  85.         for(k = curhalfanum; k < curanum; k++){
  86.             base[i][k] = base[i][j];
  87.             j--;
  88.         }
  89.     } 
  90. }
  91.  
  92. void make_digitsum_zero_to(long long base[MAXDIGIT][MAXANUM], long long n, long long arr[MAXANUM]){
  93. 	long long tmp;
  94.     int darr[MAXDIGIT] = {};
  95.     int maxdigit, offset;
  96.     int i,j,k;
  97.  
  98.     for(i = 0; i < MAXANUM; i++){
  99.         arr[i] = 0;
  100.     }
  101.  
  102.     if(n <= 0){
  103.         arr[0]++;
  104.         return;
  105.     }
  106.  
  107.     i = 0;
  108.     for(tmp = n; tmp > 0; tmp /= 10){
  109.         darr[i] = tmp % 10;
  110.         i++;
  111.     }
  112.     maxdigit = i;
  113.  
  114.     for(i = 0; i < maxdigit; i++){
  115.         offset = 0;
  116.         for(j = i+1; j < maxdigit; j++){
  117.             offset += darr[j];
  118.         }
  119.  
  120.         if(i == 0){
  121.             for(j = 0; j < darr[i]; j++){
  122.                 arr[offset]++;
  123.                 offset++;
  124.             }
  125.         }else{   
  126.             for(j = 0; j < darr[i]; j++){
  127.                 for(k = 0; k < i*9+1; k++){
  128.                     arr[offset + k] += base[i-1][k];
  129.                 }
  130.                 offset++;
  131.             }
  132.         }
  133.     }
  134.  
  135.     offset = 0;
  136.     for(i = 0; i < maxdigit; i++){
  137.         offset += darr[i];
  138.     }
  139.     arr[offset]++;
  140. }
  141.  
  142. long long max_digit_sum_freq(long long base[MAXDIGIT][MAXANUM], long long X, long long Y){
  143.     long long xarr[MAXANUM], yarr[MAXANUM];
  144.     long long digit, tmp, anum, maxfreq;
  145.     int i;
  146.  
  147.     digit = 0;
  148.     for(tmp = Y; tmp > 0; tmp /= 10){
  149.         digit++;
  150.     }
  151.     anum = digit * 9 + 1;
  152.  
  153.     make_digitsum_zero_to(base, X - 1, xarr);
  154.     make_digitsum_zero_to(base, Y, yarr);
  155.  
  156.     for(i = 0; i < anum; i++){
  157.         yarr[i] -= xarr[i];
  158.     }
  159.  
  160.     maxfreq = yarr[0];
  161.     for(i = 1; i < anum; i++){
  162.         if(maxfreq < yarr[i]){
  163.             maxfreq = yarr[i];
  164.         }
  165.     }
  166.     return(maxfreq);
  167. }
  168.  
  169. #define BUFMAX 128
  170. int main(void){
  171.     long long base[MAXDIGIT][MAXANUM];
  172.     make_base(base);
  173.     long long X, Y;
  174.     char buf[BUFMAX], *eptr, *ptr;
  175.     while(1){
  176.         memset(buf, 0, BUFMAX);
  177.         if(fgets(buf, BUFMAX, stdin) == NULL){
  178.             break;
  179.         }
  180.         X = strtoll(buf, &eptr, 10);
  181.         ptr = eptr;
  182.         Y = strtoll(ptr, &eptr, 10);
  183.         if(X < 0 || Y <= 0 || X >= Y){
  184.             break;
  185.         }
  186.         printf("%lld %lld --> %lld\n", X, Y, max_digit_sum_freq(base,X,Y));       
  187.     }
  188.     return 0;
  189. }
Success #stdin #stdout 0s 4544KB
comments (?)
stdin 
0 9999
1234567 9876543
1 500000000000
12345678909 498765432123
0 9223372036854775807
-1
stdout 
0 9999 --> 670
1234567 9876543 --> 459034
1 500000000000 --> 20406732610
12345678909 498765432123 --> 20000965162
0 9223372036854775807 --> 293347961657308060
https://ideone.com/qdx79j
2つの0以上の整数間の数字和で最大頻度を求めるプログラム
language:
C (gcc 8.3)
created:
4 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!