『ディビジョン・ナイン』
こちらの問題に挑戦しましたが、解き方が分からずに放置されたコードがこちらです。
codeiq.jp
#include <stdio.h> int get9(int min, int max) { static int k[]={0,9,18,27,36,45,54,63,72,81}; static int i = 0; static int smin, smax; int get9 = 0; if(i == 0){ smin = min; smax = max; while(k[i] < smin){ i++; } } if(k[i] <= smax){ get9 = k[i++]; }else{ get9 = 0; } return get9; } int div9(int n, int m, int k) { int p, i; if(k == 0){ return 1; } if(n < m || k < 0){ return 0; } p = 0; for(i = 1; i <= 4; i++){ if(n-m <= k-i){ p += div9(n, m+1, k-i); }else{ break; } } return p; } int main(int argc, const char * argv[]) { int n; scanf("%d", &n); int i; while(0 < (i = get9(n, 4*n))){ printf("%d,%d\n", i, div9(n, 1, i)); } printf("\n"); return 0; }
たしか入力されたnから、各桁(1〜4)のn桁がとりうる9の倍数のカウントをしていたような。
たとえば入力がnが3なら、111〜444で、各桁の合計は3〜12で、その内9の倍数は9のみ。
そこから総当たりで調べていたような。
get9が各桁の合計範囲から次の9の倍数を取得する。
div9は各桁の値が(1〜4)のn桁で9の倍数になる組み合わせを取得する。
この考えだと、入力nが5なら、11111〜44444で、各桁の合計は5〜20。
その内9の倍数は、9と18です。
9になる組み合わせと18になる組み合わせを合計すると答えるがでるかも。
入力nが20なら、11111111...111〜4444444...444で、各桁の合計は20〜80。
その内9の倍数は9、18、24、36、45、54、63、72です。
ただ9と18は、各桁の合計の下限が20以下なので、組み合わせは0通り。
残りの24〜72の9の倍数になる各組み合わせの数の総和が答えになるかもしれない。
でも、結局のところ総当たりで求めているので時間内に終わらないけど。
また暇があったら別の問題も解いてみます!