NextFloor

すきな物やモノに囲まれて生きていく!

『ディビジョン・ナイン』

こちらの問題に挑戦しましたが、解き方が分からずに放置されたコードがこちらです。
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の倍数になる各組み合わせの数の総和が答えになるかもしれない。

でも、結局のところ総当たりで求めているので時間内に終わらないけど。
また暇があったら別の問題も解いてみます!