2346:Lucky tickets

keyword

BruteForce　C++

概要

n(in {2,4,6,8,10})が与えられる。n桁の数字(先頭が0でも良い)のうち、前半と後半のdigit sumが一致するものがいくつあるか求める問題。
流石に10桁をBruteForceは無理だけど、前半部 or 後半部の和はたかだか9*5まで数えれば良いので和がnになる数(5桁以下)を数えておけば良い。後は2乗和をとるだけ。

int getDigitSum(int x){
    int ret = 0;
    int d = 1;
    while(x/d){
        ret += (x/d)%10;
        d *= 10;
    }
    return ret;
}

int main(){
    int div[50][6];
    int ans[11];
    int i, j;
    REP(i,50)REP(j,6) div[i][j] = 0;

    REP(i,10) div[getDigitSum(i)][1]++;
    REP(i,100) div[getDigitSum(i)][2]++;
    REP(i,1000) div[getDigitSum(i)][3]++;
    REP(i,10000) div[getDigitSum(i)][4]++;
    REP(i,100000) div[getDigitSum(i)][5]++;

    REP(i,11) ans[i] = 0;
    REPONE(i,5)REP(j,50){
        ans[2*i] += div[j][i]*div[j][i];
    }

    int n;
    scanf("%d",&n);
    printf("%d\n",ans[n]);
    return 0;
}