ACM/ICPC Indonesia National Contest 2007
Problem E
The Adventure in Panda Land Part I: Panda Number
Time Limit: 1sIn Panda Land, pandas have their own numeral system to represent a number. Surprisingly, this numeral system is similar to the famous Roman Numerals in our ancient civilization. Although pandas are aware about numeral system, they can not write (imagine how can a panda write!). Instead, they cut and arrange bamboos to form a number.
|
These are the production rules of Panda Number:
|
The aforementioned rules imply that there is exactly one representation in Panda Number for each number in decimal system.
Unlike those Roman Numerals, pandas do recognize zero and negative number (which prove pandas are more advanced than our ancient Romans). To represent a negative number, they add one bamboo as a negative sign in front of the letters. Zero is a special number which doesn't fall into any rules above. To form a zero, pandas need five bamboos.
The number of bamboos needed to form a number is the sum of required bamboos for each letter that appears in that number. For Example:
4108 = 4000+100+8 = (5000-1000)+100+5+1+1+1 = MECVIII (16 bamboos).
4109 = 4000+100+9 = (5000-1000)+100+(10-1) = MECIX (14 bamboos).
-205 = [-], 200+5 = 100+100+ 5 = -CCV (9 bamboos)
Given two numbers A and B, find out how many bamboos needed by panda to form (remember, they can't write) all number between A and B inclusively.
Input
The input begins with a single positive integer T in a line indicating the number of test cases. Each case contains two numbers A and B (-25,000,000 <= A <= B <= 25,000,000) in a line.Output
For each case, print in a single line the number of needed bamboos to form all numbers between A and B (inclusive).Sample Input
7 -1 1 4018 4019 -25000000 25000000 -100 -57 -100 0 0 100 43 100
Sample Output
8 28 2121000021 399 778 678 434
Problem Setter: Evan Leonardi
Pembahasan Problem E - Panda Number
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.
Contoh: 3 = 3 * 10^0 -> III 30 = 3 * 10^1 -> XXX 300 = 3 * 10^2 -> CCC 3000 = 3 * 10^3 -> MMM 30000 = 3 * 10^4 -> WWW ... 4 = 4 * 10^0 -> IV 40 = 4 * 10^1 -> XL 400 = 4 * 10^2 -> CN 4000 = 4 * 10^3 -> ME 40000 = 4 * 10^4 -> WF ... 8 = 8 * 10^0 -> VIII 80 = 8 * 10^1 -> LXXX 800 = 8 * 10^2 -> NCCC 8000 = 8 * 10^3 -> EMMM 80000 = 8 * 10^4 -> FWWW ... dan yang lain dan seterusnyaDari contoh diatas, terlihat pattern:
Sebenarnya I,X,L,C,M,W,Y,H,A itu semua sama saja, yang membedakannya adalah pangkat 10 nya, begitu pula dengan V,L,N,E,F,K,T.Jadi, format angka 80 itu sama saja dengan angka 80000, hanya saja L diganti F, dan X diganti W. Otomatis kita tinggal membuat tabel:
Untuk pangkat 10 tertentu, apakah simbol yang bersangkutan? atauUntuk soal ini, kita tidak perlu tahu simbolnya, tapi hanya jumlah bambunya saja. Anda bisa lihat function bamboo(d,p) dibawah untuk menghitung berapa bamboo yang diperlukan untuk digit d dimana digit tersebut ada di posisi 10^p. Contoh:
Untuk pangkat 10 tertentu, berapa bambu yang dibutuhkan?
Untuk menghitung banyak bambu untuk angka 80000 = 8 * 10^4, tinggal panggil bamboo(8,4).
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
}
}
}
}
No comments:
Post a Comment