Felix Halim .NET :: Pembahasan final INC 2007 Problem E

Anda diberikan sistem angka untuk Panda yang mirip sistem angka pada Roman. Diperlukan jumlah bambu tertentu untuk membentuk suatu angka. Untuk range A..B (-25 juta <= A < B < 25 juta), anda diminta untuk menghitung berapakah jumlah bambu yang diperlukan untuk membentuk semua angka dari A sampai B? Untuk lebih jelasnya silahkan lihat problem statement diatas.

Menurut pemahaman saya, setiap angka di decimal number system bisa diubah menjadi roman/panda system secara terpisah berdasarkan letak dari significant digit masing-masing angka tersebut.

Karena range A, B begitu besar, maka anda perlu mem-precalculate hasil untuk semua range. Ini bisa dilakukan dengan menggunakan dynamic programming (membuat tabel dp) yang meng-akumulasi jumlah bamboo dari 1 sampai n. Untuk menghitung jumlah bambu dari range A sampai B, anda tinggal menghitung dp[B] - dp[A-1] dimana A dan B harus positive. Kalau A atau B adalah negative atau nol, maka diperlukan sedikit if-else. Lihat dibawah untuk semua kemungkinan A dan B beserta perhitungannya.

Ada cara untuk menghitung akumulasi bambu dari 1..n on-the-fly hanya dalam O(banyak nya digit di input ^ 2). Saya diberi tahu cara ini oleh Stephen Kohar dari tim NoMoreAC. Caranya adalah (nanti saya jelaskan), kalian coba liat source code nya dulu dech dibawah (dengan nama panda-on-the-fly.c). Function bamboo dan main function tidak berubah sama sekali, yang berubah adalah dp[i] tidak lagi di-precalculate, tapi dihitung on-the-fly dp(i).

#include <stdio.h>
#include <math.h>

#define MAXN 25000000

int need[8][2] = { {1,2}, {2,2}, {3,3}, {4,4}, {4,3}, {3,3}, {3,2}, {3,0} };

// berapa bamboo yang diperlukan untuk digit d dimana digit tersebut ada di 10^p
int bamboo(int d, int p){
    switch (d){
        case 0: return 0; // special case
        case 1: return 1 * need[p][0] + 0 * need[p][1]; // I
        case 2: return 2 * need[p][0] + 0 * need[p][1]; // II
        case 3: return 3 * need[p][0] + 0 * need[p][1]; // III
        case 4: return 1 * need[p][0] + 1 * need[p][1]; // IV
        case 5: return 0 * need[p][0] + 1 * need[p][1]; // V
        case 6: return 1 * need[p][0] + 1 * need[p][1]; // VI
        case 7: return 2 * need[p][0] + 1 * need[p][1]; // VII
        case 8: return 3 * need[p][0] + 1 * need[p][1]; // VIII
        case 9: return 1 * need[p][0] + 0 * need[p][1] + 
                       1 * need[p+1][0] + 0 * need[p+1][1]; // IX
    }
}

int dp[MAXN+1]; // dp[i] adalah jumlah bamboo untuk membentuk angka angka dari 1 sampai i

void precalculate(){
    int i,j,k,p,base,need;

    // precalculate table dp untuk menghindari time limit
    // perhitungan DP ini memang agak sulit dijelaskan maupun dimengerti
    // tetapi dengan pengalaman dan latihan, anda akan bisa memahaminya :D
    dp[0] = 0;
    for (p=0,i=1; p<9; p++,i*=10){
        for (j=0; j<10; j++){
            if (i*j > MAXN) break;
            base = i*j;
            need = bamboo(j,p);
            for (k=0; k<i; k++){
                if (base+k > MAXN) break;
                dp[base+k] = need + dp[k];
            }
        }
    }

    for (i=1; i<=MAXN; i++) dp[i] += dp[i-1];               // akumulasi
}

int main(){
    int T,A,B;

    precalculate();

    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&A,&B);
        if (A<0){
            A = abs(A);
            if (B<0){
                B = abs(B);
                printf("%d\n", dp[A] - dp[B-1] + (A-B+1));  // A <= B < 0
            } else {
                printf("%d\n", A + dp[A] + 5 + dp[B]);      // A < 0 <= B
            }
        } else { // 0 <= A <= B
            if (A==0){
                printf("%d\n", dp[B] + 5);                  // 0 == A <= B
            } else {
                printf("%d\n", dp[B] - dp[A-1]);            // 0 < A <= B
            }
        }
    }
}

#include <stdio.h>
#include <math.h>

#define MAXN 25000000

int need[8][2] = { {1,2}, {2,2}, {3,3}, {4,4}, {4,3}, {3,3}, {3,2}, {3,0} };

// berapa bamboo yang diperlukan untuk digit d dimana digit tersebut ada di 10^p
int bamboo(int d, int p){
    switch (d){
        case 0: return 0; // special case
        case 1: return 1 * need[p][0] + 0 * need[p][1]; // I
        case 2: return 2 * need[p][0] + 0 * need[p][1]; // II
        case 3: return 3 * need[p][0] + 0 * need[p][1]; // III
        case 4: return 1 * need[p][0] + 1 * need[p][1]; // IV
        case 5: return 0 * need[p][0] + 1 * need[p][1]; // V
        case 6: return 1 * need[p][0] + 1 * need[p][1]; // VI
        case 7: return 2 * need[p][0] + 1 * need[p][1]; // VII
        case 8: return 3 * need[p][0] + 1 * need[p][1]; // VIII
        case 9: return 1 * need[p][0] + 0 * need[p][1] + 
                       1 * need[p+1][0] + 0 * need[p+1][1]; // IX
    }
}

int dp(int n){
    int p=0, digit=n, power=1, remaining=0, result=0, i;

    if (n<=0) return 0;
    while (digit>9) power *= 10, digit /= 10,  p++;
    remaining = n - digit*power;
    result = dp(remaining) + bamboo(digit,p) * (remaining+1) + dp(power-1) * digit;
    for (i=1; i<digit; i++) result += bamboo(i,p) * power;
    return result;
}

int main(){
    int T,A,B;

    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&A,&B);
        if (A<0){
            A = abs(A);
            if (B<0){
                B = abs(B);
                printf("%d\n", dp(A) - dp(B-1) + (A-B+1));  // A <= B < 0
            } else {
                printf("%d\n", A + dp(A) + 5 + dp(B));        // A < 0 <= B
            }
        } else { // 0 <= A <= B
            if (A==0){
                printf("%d\n", dp(B) + 5);                    // A==0, A <= B
            } else {
                printf("%d\n", dp(B) - dp(A-1));            // 0 < A <= B
            }
        }
    }
}

Problem E - Panda Number