Saturday, June 16, 2007

Final Indonesia National Contest 2007 :: Problem H - Tree Median

ACM/ICPC Indonesia National Contest 2007

Problem H

Tree Median

Time Limit: 3s


A tree is a connected graph containing no cycles. A vertex is called a median vertex if the total cost to reach all vertices is minimal. There could be more than one median vertex in a tree, that's why we define median as the set of all median vertices. To find median in a tree with small number of vertices is fairly easy task as you can solve this by a simple brute force program.

In the left figure, we can see a weighted tree with 5 vertices. The tree median is {B} because the total cost from vertex B to all other vertices is minimal.

B-A = 2    B-D = 7
B-C = 1    B-E = 7 + 5 = 12

TOTAL = 2 + 1 + 7 + 12 = 22

What if the number of vertices is quite large? This might be a problem since brute force program cost too much time. Given a weighted tree with N vertices, output the total cost to reach all vertices from its median.

Input

Input consists of several cases. Each case begins with an integer n (1<= n <= 10,000) denoting the number of vertices in a tree. Each vertex is numbered from 0...n-1. Each of the next n-1 lines contains three integers: a, b, and w (1<= w <= 100), which means a and b is connected by an edge with weight w.

Input is terminated when n is equal to 0. This input should not be processed.

Output

For each case, output a line containing the sum of cost of path to all other vertices from the tree median.

Sample Input

5
0 1 2
1 2 1
1 3 7
3 4 5
6
0 1 1
1 2 4
2 3 1
3 4 4
4 5 1
0

Sample Output

22
21


Problem Setter: Suhendry Effendy



Pembahasan Problem H - Tree Median

Diberikan suatu graph berbentuk tree. Graph ini memiliki N (1 <= N <= 10000) nodes dan N-1 edges yang mempunyai weight W (1 <= W <= 100). Carilah satu dari N node untuk dijadikan "root" sehingga total distance dari root ke semua nodes adalah minimum. Untuk contoh jelasnya (dipandu dengan gambar) silahkan lihat problem statement diatas.

Salah satu cara menyelesaikannya adalah dengan bruteforce, yaitu dengan mencoba satu-persatu node untuk dijadikan "root" dan menghitung total distance dari root tersebut ke semua nodes. Kendalanya adalah bagaimana cara menghitung total distance dari root ke semua node dalam O(1)? Berikut adalah cara yang saya ketahui, yaitu dengan menggeser root yang sekarang ke node tetangganya dan meng-update total distance ke semua nodes. Dibawah adalah langkah-langkah untuk melakukannya:

Pilih salah satu node untuk dijadikan "root", misalkan node 0. Lalu pre-calculate semua distance weight dan count nodes dari root ke semua nodes. Definisi distance weight adalah berapa total distance untuk node tersebut beserta sub-tree dari node tersebut. Definisi count nodes adalah berapa banyak node anak yang dimiliki node tersebut (termasuk node itu sendiri). Pre-calculate ini bisa dilakukan dengan DFS (rekursi). Note: untuk input yang besar, misalkan N = 10000, maka kedalaman rekursi dari DFS ini akan menyebabkan stack-overflow kecuali anda sudah mengubah setting compiler untuk stack size menjadi lebih besar (32 MB cukup).

Setelah pre-calculate distance weight dan count nodes dari node 0, otomatis anda bisa mengetahui total distance dari root ini ke semua nodes dalam O(edges dari node 0). Lalu anda bisa melakukan DFS (rekursi) ke dua yang bertugas untuk menggerakan "root" (yang sekarang di node 0) ke semua node lainnya sembari mengupdate tabel distance weight dan count nodes supaya anda bisa tetap menghitung total distance dari root yang baru ke semua nodes juga dalam O(edges dari root tersebut).

Jadi, total complexity dari algoritma ini adalah O(N) untuk pre-calculate distance dan count. O(N) untuk menggeser "root" ke N-1 nodes yang lain sambil mengcalculate distance nya dalam O(edges dari root node baru tersebut). Dengan amortized analysis, complexity dari calculate total distance untuk suatu root adalah O(1), karena ada N-1 edges total dan N nodes.
Code untuk problem ini saya pecah menjadi dua: tree-rec.cpp dan tree-stack.cpp. Keduanya mengimplement code diatas. Tetapi yang menggunakan rekursi (tree-rec.cpp) hanya bisa untuk N yang kecil (karena terbatas stack size di compiler, kecuali anda naikkan stack size compiler anda). Untuk code yang menggunakan stack buatan (tree-stack.cpp) bisa menghandle input lebih besar tanpa mengubah settingan compiler karena data dialokasikan di heap memory.

Kedua code menggunakan STL map, set, vector. Kalau tidak, maka codingnya akan jauh lebih panjanggggg..... Anda bisa menggunakan problem ini untuk belajar STL maupun rekursi dengan stack buatan.

Untuk Andrian Kurniady: sharing donk algo "DP problem I" nya gimana? pake rekursi topdown? apa bottom up?

#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

vector<map<int,int> > con;
vector<long long> dist;
vector<int> cnt;
long long res;
int n;

void calcCnt(int i, int p){
    cnt[i]++;
    dist[i] = 0;
    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p){
            calcCnt(j,i);
            cnt[i] += cnt[j];
            dist[i] += cnt[j] * w + dist[j];
        }
    }
}

void rec(int i, int p, int c, long long v){
    long long sum = (p==-1)? 0 : (v + c * con[p][i]);
    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p) sum += cnt[j] * w + dist[j];
    }
    res = min(res, sum);

    FOREACH(it,con[i]){
        int j = it->first;
        int w = it->second;
        if (j!=p) rec(j, i, n-cnt[j], sum-(dist[j] + cnt[j]*w));
    }
}

int main(){
    while (scanf("%d",&n)!=EOF && n){
        con = vector<map<int,int> >(n);
        for (int i=1,a,b,w; i<n; i++){
            scanf("%d %d %d",&a,&b,&w);
            con[a][b] = w;
            con[b][a] = w;
        }

        cnt = vector<int>(n);
        dist = vector<long long>(n);
        calcCnt(0,-1);

        res = 1000000000000LL;
        rec(0,-1,0,0);
        printf("%lld\n",res);
    }
}
#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

vector<map<int,int> > con;
vector<long long> dist;
vector<int> cnt;
long long res;
int n;

void calcCnt(int i, int p){
    vector<pair<int,int> > stk;
    vector<bool> vis;
    stk.push_back(make_pair(i,p));
    vis.push_back(false);
    while (stk.size()>0){
        i = stk.back().first;
        p = stk.back().second;

        if (!vis.back()){
            vis.back() = true;
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    stk.push_back(make_pair(j,i));
                    vis.push_back(false);
                }
            }
        } else {
            cnt[i] = 1;
            dist[i] = 0;
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    cnt[i] += cnt[j];
                    dist[i] += cnt[j] * w + dist[j];
                }
            }
            stk.pop_back();
            vis.pop_back();
        }
    }
}

struct ipcv {
    long long i,p,c,v;
};

void rec(int i, int p, int c, long long v){
    vector<ipcv> stk;
    vector<bool> vis;
    stk.push_back((ipcv){i,p,c,v});
    vis.push_back(false);
    while (stk.size()>0){
        ipcv t = stk.back();
        i = t.i;
        p = t.p;
        c = t.c;
        v = t.v;

        if (!vis.back()){
            vis.back() = true;

            long long sum = (p==-1)? 0 : (v + c * con[p][i]);
            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p) sum += cnt[j] * w + dist[j];
            }
            res = min(res, sum);

            FOREACH(it,con[i]){
                int j = it->first;
                int w = it->second;
                if (j!=p){
                    stk.push_back((ipcv){j, i, n-cnt[j], sum-(dist[j] + cnt[j]*w)});
                    vis.push_back(false);
                }
            }
        } else {
            stk.pop_back();
            vis.pop_back();
        }
    }
}

int main(){
    while (scanf("%d",&n)!=EOF && n){
        con = vector<map<int,int> >(n);
        for (int i=1,a,b,w; i<n; i++){
            scanf("%d %d %d",&a,&b,&w);
            con[a][b] = w;
            con[b][a] = w;
        }

        cnt = vector<int>(n);
        dist = vector<long long>(n);
        calcCnt(0,-1);

        res = 1000000000000LL;
        rec(0,-1,0,0);
        printf("%lld\n",res);
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem G - Sultan's Land

ACM/ICPC Indonesia National Contest 2007

Problem G

Sultan's Land

Time Limit: 1s


Sultan Al-Bandar, the ruler of Old West Sumatra Sultanate, has decided to give his land to his only son. Although the Sultan believes that his son will not misuse the land for some bad purposes, he still has some doubts on his son's capability to rule the land. Therefore, he decided to give his son a test, a puzzle test.

The Sultan drew N x N grids (virtually of course) on his land where any two adjacent grid intersections would have the same length. Then he placed some pillars on the land where each pillar was placed at one intersection. Then he summoned his son to come to the land.

"Well, my dear son, if you are to choose four pillars to form an area where each pillar serves as a corner of that area, how many possible selections are there?" asked the Sultan. His son replied him with a big smile. Just at the time the Sultan remembered that his son works for the Sultanate's Advance Combinatorial Ministry, so this problem might be too easy. Then he quickly added, "Oh! Each side of the area should be parallel to the grid I have drawn before."


To tell the truth, the Sultan himself actually had not prepared any answers since he spontaneously asked his after the big smile. Help this Sultan by writing a program to count how many possible selections can be made by applying the rules above.

Input

The input contains several test cases. Each case begins with two integers, N (2 <= N <= 100) the grid-size, and P (2 <= P <= N2) the number of pillars. Each grid will be numbered from 1 to N. The next P following lines each will contains two integers: r and c (1 <= r, c <= N) the row and column where the pillar is placed.

Input is terminated by a line containing two zeroes. This input should not be processed.

Output

For each case, output a line containing the number of possible selections can be made to form an area whose sides are parallel to the grid.

Sample Input

7 10
1 3
1 6
2 2
2 5
4 2
4 5
5 1
5 6
6 3
6 6
3 6
2 1
2 2
2 3
3 1
3 2
3 3
0 0

Sample Output

2
3


Problem Setter: Suhendry Effendy


Pembahasan Problem G - Sultan's Land

Diberikan banyak pilar-pilar berupa titik (1<=x<=100, 1<=x<=100) dalam suatu kartesian sistem. Suatu persegi bisa dibentuk oleh 4 pillar yang terletak di 4 sudut persegi tersebut. Berapa banyak persegi yang mungkin dibentuk?

Cara yang paling gampang adalah bruteforce 4 titik: untuk setiap 4 titik, dicek apakah membentuk persegi? kalau iya, maka tambahkan ke hasil. Tapi sayangnya jumlah titik bisa mencapai 100 x 100 dimana nCk(10000, 4) = 416416712497500 itu sangat besar. Sudah pasti kena time limit exceeded.

Cara kedua adalah juga bruteforce, tetapi sedikit lebih pintar: untuk setiap kombinasi 2 baris, carilah berapa banyak persegi yang bisa dibentuk? Banyaknya kombinasi baris yang mungkin adalah nCk(100,2) = 4950 kemungkinan. Untuk setiap kombinasi 2 baris, anda dapat menghitung kemungkinan persegi yang bisa dibuat dengan cara menghitung banyak nCk(titik yang bersekutu di kolom, 2). Dengan demikian, complexity dari bruteforce ini adalah O(N^3). Untuk implementasinya silahkan lihat kode rect.c dibawah.

Anda bisa mempercepat perhitungan jumlah titik yang bersekutu di kolom untuk baris i dan baris j dengan menggunakan 2 long long variable dan menghitung jumlah persekutuan kolomnya dengan melakukan bitwise operation AND untuk baris i dan j. Lalu untuk menghitung berapa bit yang ON bisa dilakukan dengan O(1) meskipun kodenya sangatlah criptic, anda bisa lihat di bithack article ini. Sehingga complexity dari bruteforce turun menjadi O(N^2). Bagaimanapun, algo brutforce O(N^3) diatas sudah cukup cepat untuk problem ini.

#include <stdio.h>
#include <string.h>

int N,P,pillar[100][100];

int main(){
    int i,j,k,r,c,res;
    while (scanf("%d %d",&N,&P)!=EOF && (N||P)){
        memset(pillar,0,sizeof(pillar));
        for (i=0; i<P; i++){
            scanf("%d %d",&r,&c);
            pillar[r-1][c-1] = 1;
        }

        res = 0;
        for (i=0; i<N; i++)
            for (j=i+1; j<N; j++){
                int c = 0;
                for (k=0; k<N; k++)
                    if (pillar[i][k] && pillar[j][k])
                        c++;

                res += c*(c-1)/2; // nCk(c,2) = c diambil 2 = c*(c-1)/2
            }
        printf("%d\n",res);
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem F - Jakarta Traffic Jam

ACM/ICPC Indonesia National Contest 2007

Problem F

Jakarta Traffic Jam

Time Limit: 1s


The traffic in Jakarta is terrible. Streets in Jakarta may get congested with traffic jam during rush hour. This means it will take longer time to pass through those streets since you can only drive half your speed during rush hours. Therefore, you need to plan your trip carefully if you don't want to be late for your activities.

For example, consider a street from P to Q which will need 20 minutes to drive in a normal time. The street is congested with traffic at 15:00 until 16:00. Now, let's consider some sample conditions that might happen related to rush hours:
  1. If you start your trip 15 minutes before the rush hour (start from P at 14:45), then when the traffic starts to get congested, you can only drive half of your normal speed, thus, you will need 10 (2x5) more minutes to reach Q. Thus, the total time you need to go from P to Q is 15 + 10 = 25 minutes.

  2. If you start your journey at the last 5 minutes of the rush hour (start from P at 15:55), the distance you have reached in the first 5 minutes is equal to the distance you can reach in 2.5 minutes during normal hours. You will need 17.5 more minutes to get to Q. Thus, the total time you need to go from P to Q is 5 + 17.5 = 22.5 minutes.

  3. Other combinations of (a) and (b).
Given a map which has at most N intersections and M streets, find out how many minute(s) you need to go from s to d. You want to reach d as soon as possible without wasting any seconds or microseconds, or even nanoseconds.

Input

The input contains several test cases. Each case begins with two integers N (1<= N <=20) and M. Each intersection will be numbered from 0 to N-1.

The first three integers P, Q, and T (1<= T <=50) in each of the following M line means there is a street connecting intersection P to intersection Q which need T minutes driving in normal time. These integers will be followed by either character 'N' or 'R'. 'N' will not be followed by any characters and it means the street has no rush hours. 'R' will be followed by the starting and ending time of the rush hour in the format of hh:mm (00:00 to 23:59). No rush hours will rollover past midnight.

The last line of each case contains s - your starting point, d - your destination and w - current time.

Input is terminated by a line containing two zeroes. This line should not be processed.

Output

For each case, output a line containing the minimum time you need to go from s to d in minutes. Your output should always contain two digits after the decimal point.

Sample Input

2 1
0 1 20 R 15:00 16:00
0 1 14:45
3 3
0 1 20 R 15:00 16:00
1 3 10 N
2 1 35 R 16:30 17:00
0 2 15:55
0 0

Sample Output

25.00
72.50


Problem Setter: Danny Gunawan


Pembahasan Problem F - Jakarta Traffic Jam

Soal ini secara algoritma lebih mudah daripada soal Taxi di babak penyisihan, tetapi bobotnya dipindahkan ke matematika!

Ada N persimpangan dan M jalan. Setiap jalan mempunyai jam kemacetan dimana kalau anda melalui jalan tersebut saat macet maka kecepatan anda akan menurun setengah kecepatan awal. Pertanyaannya, berapakah waktu tercepat dari s ke d?

Anda tidak perlu A* seperti soal Taxi di penyisihan, algoritma umum Dijkstra bisa diterapkan untuk memecahkan soal ini karena anda hanya perlu meminimalisasi waktu dari source ke destination. Tepat seperti apa yang Dijkstra lakukan. Bagaimanapun juga, A* adalah versi superior dan kode nya pun tidak jauh beda dengan Dijkstra dan mungkin lebih gampang di implementasi. Untuk belajar A*, anda bisa buka pembahasan soal penyisihan Taxi. Untuk belajar Dijkstra anda bisa lihat pembahasan soal ini.

Saya akan coba menjelaskan Dijkstra secara kasarnya saja. Untuk cara formalnya, anda bisa baca dari buku Introduction to Algorithms atau cari sendiri lewat Google :)

Cara Dijkstra bekerja adalah dengan selalu memprocess node yang memiliki waktu tercepat dan berhenti saat semua node sudah diprocess. Dalam memprocess suatu node, node tersebut akan meng-update waktu yang dibutuhkan untuk tiba di node lain dari node tersebut. Saat suatu node diprocess, maka waktu tercepat untuk sampai ke node tersebut sudah diketahui dengan pasti. Silahkan lihat dibawah untuk implementasinya.

#include <stdio.h>

// ini adalah function mematikan dari soal ini, membutuhkan sedikit if dan else + rekursi :)
double calculate(double waktuSekarang, double lamaPerjalanan, int rushStart, int rushEnd){
    double waktuTiba = waktuSekarang + lamaPerjalanan;

    if (rushStart <= waktuSekarang && waktuSekarang <= rushEnd){
        // waktu mulainya kena rush hour, case yang B

        // berapa lama lagi sampai rush hournya berhenti
        double lamanyaRushHour = rushEnd - waktuSekarang;

        if (lamanyaRushHour > lamaPerjalanan * 2){
            // sepanjang anda berjalan, macet melulu
            return lamaPerjalanan * 2;      
        } else {
            // ditengah-tengah perjalanan anda berhasil lolos dari rush hour
            double jarakTersisa = lamaPerjalanan - lamanyaRushHour/2;
            return lamanyaRushHour + jarakTersisa;
        }
    } else if (waktuSekarang <= rushStart && rushStart <= waktuTiba){
        // ditengah perjalanan anda terkena rush hour, case yang A
        
        // anda bisa jalan dengan kecepatan normal saat belum terkena rush hour
        double jalanNormal = rushStart - waktuSekarang;    
        
        // disinilah anda mulai terkena rush hour dan kalau dilihat, anda mirip Case B diatas
        // yaitu anda memulai dengan terkena rush hour! maka tinggal panggil aja calculate() sekali lagi ;)
        return jalanNormal + calculate(
            waktuSekarang + jalanNormal,    // waktu sekarang sudah bertambah sebanyak perjalanan yang ditempuh
            lamaPerjalanan - jalanNormal,   // lama perjalanan berkurang sebanyak yang ditempuh
            rushStart, rushEnd);            // waktu rush hour start dan end masih tetap sama
    } else {
        return lamaPerjalanan;              // anda mujur sekali tidak terkena rush hour
    }
}

int getTime(){
    int hh,mm;
    scanf("%d:%d",&hh,&mm);
    return hh*60 + mm;
}

int main(){
    int travel_time[20][20];     // travel_time[i][j] waktu normal berjalan dari i ke j
    int rush_start[20][20];      // rush_start[i][j] waktu mulai rush hour untuk jalan i ke j
    int rush_end[20][20];        // rush_end[i][j] waktu selesai rush hour untuk jalan i ke j
    double waktu[20];            // waktu[x] adalah waktu tercepat untuk sampai di node x
    int N,M,i,j,k,P,Q,T,s,d,pq[20],pqSize;
    char NR[2];

    while (scanf("%d %d",&N,&M)!=EOF && (N||M)){
        memset(travel_time,-1,sizeof(travel_time));
        memset(rush_start,-1,sizeof(rush_start));
        memset(rush_end,-1,sizeof(rush_end));

        for (i=0; i<M; i++){
            scanf("%d %d %d %s",&P,&Q,&T,NR);
            travel_time[P][Q] = travel_time[Q][P] = T;
            if (NR[0]=='R'){
                rush_start[P][Q] = rush_start[Q][P] = getTime();
                rush_end[P][Q] = rush_end[Q][P] = getTime();
            }
        }
        scanf("%d %d",&s,&d);

        for (i=0; i<N; i++){
            pq[i] = i;           // masukkan semua node ke Priority Queue
            waktu[i] = 1e10;     // waktu di semua node adalah tak terhingga
        }
        waktu[s] = getTime();    // set waktu dari starting intersection s
        
        // Dijkstra, process berdasarkan waktu yang paling pagi
        for (pqSize=N; pqSize>0; pqSize--){

            // cari node terpagi yang belum diprocess
            k = 0;
            for (i=1; i<pqSize; i++)
                if (waktu[pq[i]] < waktu[pq[k]])
                    k = i; // update k kalau ketemu node yang lebih pagi

            i = pq[k];               // pq[k] adalah node dengan waktu terpagi, simpan di i
            pq[k] = pq[pqSize-1];    // buang node k dari priority queue

            // process node i (node yang terpagi saat ini)
            for (j=0; j<N; j++){
                if (travel_time[i][j]!=-1){
                    double duration = travel_time[i][j];
                    
                    if (rush_start[i][j]!=-1){
                        duration = calculate(    // hitung durasi waktu yang diperlukan dari intersection i ke j
                            waktu[i],            // waktu saat ini
                            travel_time[i][j],   // waktu perjalanan normal dari i ke j
                            rush_start[i][j],    // jam mulai rush hour untuk jalan i ke j
                            rush_end[i][j]);     // jam selesai rush hour untuk jalan i ke j
                    }

                    // jika kita bisa travel ke j dari i lebih cepat, maka update waktu j
                    if (waktu[i] + duration < waktu[j]){
                        waktu[j] = waktu[i] + duration;
                    }
                }
            }
        }

        // waktu tercepat sampai di destination d adalah waktu di d dikurang dengan waktu di s
        printf("%.2lf\n", waktu[d] - waktu[s]);
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem E - Panda Number

ACM/ICPC Indonesia National Contest 2007

Problem E

The Adventure in Panda Land Part I: Panda Number

Time Limit: 1s


In 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.

Decimal Panda Number Required Bamboo
1I1
5V2
10X2
50L2
100C3
500N3
1,000M4
5,000E4
10,000W4
50,000F3
100,000Y3
500,000K3
1,000,000H3
5,000,000T2
10,000,000A3
  These are the production rules of Panda Number:
  • Letters which represent powers-of-ten (I, X, C, M, W, Y, H, A) can be repeated at most three times. The others (V, L, N, E, F, K, T) can not be repeated.
  • If one or more letters are placed after another letter of greater value, add that amount. The letters should be written in descending order from the largest to the least value. For example:
    FXVIII = 50000 + 10 + 5 + 1 + 1 + 1 = 50018
  • If a letter is placed before another letter of greater value, subtract that amount. Only subtract one letter from another. For example:
    XIV = 10 + (5 - 1) = 14
    CIX = 100 + (10 - 1) = 109
    MECIX = (5000 - 1000) + 100 + (10 - 1) = 4109
  • Only powers-of-ten can be used to subtract a value (that is, you can subtract I from V, or X from L, but not V from X (V is not powers-of-ten.)
  • Do not subtract a letter from one that is more than 10 times greater (that is, you can subtract I from X, but not I from L -- there is no such number as IL.)

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 seterusnya

Dari 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? atau
Untuk pangkat 10 tertentu, berapa bambu yang dibutuhkan?
Untuk 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 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
            }
        }
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem D - Email from The Professor

ACM/ICPC Indonesia National Contest 2007

Problem D

Email from The Professor

Time Limit: 1s


Being a judge in a programming contest like ACM/ICPC INC sometimes means trouble. They have to prepare challenging and interesting problems, and most importantly, they should keep the problems secret before the contest day. Usually, the judges use email as a main device to communicate and discuss on problems. As you might think, this is not a secure way to communicate confidentially since emails can be unintentionally sent to unexpected recipients, e.g. his/her student or worst, the contestant.

Considering those issues, Prof. Nash V. Ruhdney, one of the judges, has proposed a method to communicate confidentially amongst judges. Supposed there is a message of length n, write the message in a rectangle of width k, row by row, and read it column by column in a permuted order. The order of columns will then be the encryption key for the message. For example,
Message     : I am Prof. Nash V. Ruhdney
Key         : 3 7 4 1 2 6 5
Plain Text  : I   a m   P r
              o f .   N a s
              h   V .   R u
              h d n e y * *     note: '*' means blank and is not part of the message.
Column      : 11112222333344445556667777
Cipher Text : m .e N yIohha.VnrsuPaR f d
Prof. Nash then send this encrypted message (cipher text) through email, while the encryption key is sent through other means, such as phone or SMS. This way he can reduce the risk of erroneously sent email.

Of course there is no way that the professor would use paper & pencil to encrypt those messages. So, would you be kind to help him while he is preparing a nice problem for you?

Input

Input consists of several test cases. The first line of each test case contains a message of length n (1 <= n <= 1,000) in a line (the message consists of ASCII characters). The next line contains k, (1 <= k <= 1,000) the width of rectangle, followed by k integer(s) separated by a single space, the permutation of 1 to k which represents the encryption key.

Output

For each message, output the encrypted message in a single line.

Sample Input

I am Prof. Nash V. Ruhdney
7 3 7 4 1 2 6 5
give no easy problem this year.
5 1 4 3 2 5

Sample Output

m .e N yIohha.VnrsuPaR f d
gnso  .eepeiav  lheioybty armsr


Problem Setter: Suhendry Effendy


Pembahasan Problem D - Email from the Professor

Diberikan string plaintext, dan sebuah key untuk meng-enkripsi-nya. Cara meng-enkripsi plaintext tersebut adalah dengan me-wrap around plaintext dengan width K (sehingga tercipta K columns of characters dan R baris). Lalu pengkodeannya adalah dengan membaca column (a1,a2,a3..aK) dari baris paling atas ke paling bawah dimana a1..aK adalah permutasi dari 0..K-1.

Soal ini hanya men-simulasikan apa yang ada di soal, jadi pintar-pintarnya kalian membuat program tanpa bug. Algoritmanya simple, anda cukup melakukan inverse dari key yang diberikan, lalu tinggal anda print per kolom dari baris pertama sampai terakhir, tetapi hati-hati dengan baris terakhir, bisa jadi sudah melebihi panjang string inputnya. Untuk lebih jelasnya lihat source code dibawah.

#include <stdio.h>
#include <string.h>

int idx[1000], inv[1000];
char s[1001];

int main(){
    while (gets(s)){
        int i,j,k,row,len=strlen(s);

        scanf("%d",&k);
        for (i=0; i<k; i++)
            scanf("%d",&idx[i]);
        scanf("\n");                             // baca ending new line

        for (i=0; i<k; i++)
            inv[idx[i]-1] = i;                   // inverse idx, tampung di inv

        row = (len+k-1)/k;                       // berapa baris yang tercipta, dibulatkan keatas

        for (i=0; i<k; i++)                      // looping pertama, untuk setiap kolum dari 0..k-1
            for (j=0; j<row; j++){               // looping kedua, print dari baris atas sampai bawah
                if (inv[i]<len)                  // hati hati, cek apakah index sekarang melebihi input?
                    printf("%c",s[inv[i]]);
                inv[i] += k;                     // lanjutkan ke baris berikutnya
            }
        
        puts("");
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem C - Playing With Domino

ACM/ICPC Indonesia National Contest 2007

Problem C

Playing With Domino

Time Limit: 1s


A domino is a 2x1 rectangular tile with a line dividing its face into two squares, each with a certain number of dots from zero spots to six spots. As you might know, there are many different games which can be played using dominoes. In most games, dominoes are played by arranging them into a single chain where adjacent dominoes must have matching numbers (see example illustration below).


There are 28 possible faces in a complete set of domino: 0-0, 0-1, 0-2, 0-3, 0-4, 0-5, 0-6, 1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-2, 2-3, 2-4, 2-5, 2-6, 3-3, 3-4, 3-5, 3-6, 4-4, 4-5, 4-6, 5-5, 5-6, 6-6. Of course you can play each domino in either direction. For example, you can play 1-6 as 1/6 or 6/1 depending on your need.

Write a program to find the longest chain that can be made from a given set of dominoes. There may be more than one domino with the same face.

Input

Input contains several cases. Each case begins with an integer N (1 <= N <= 1,000) denoting the number of available domino. Each of the following N lines contains a pair of number (0 to 6) which represents the domino. The first number in each pair is always smaller or equal to the second number.

Output

For each case, print in a single line the number of domino used in the longest domino chain.

Sample Input

6
2 5
0 1
1 6
2 3
1 2
4 5
2
0 1
3 5

Sample Output

4
1


Problem Setter: Ang Ing Ing


Pembahasan Problem C - Playing With Domino

Diberikan N (N <= 1000) kartu domino yang memiliki angka dari 0 sampai 6. Anda harus menyusun kartu domino tersebut sambung menyambung sepanjang mungkin. Berapakah panjang dari rangkaian domino terpanjang? Untuk penjelasan lebih lengkapnya silahkan lihat di problem statement diatas.

Ini adalah soal tersulit di babak final. Bukan saja sulit dalam hal algoritma apa yang harus dipakai, tetapi juga sulit dalam hal implementasinya. Yang saya maksud sulit dalam hal implementasi bukanlah jumlah baris kodenya, tetapi alur dari kode tersebut. Implementasi saya (setelah melihat solusi juri -> Suhendry) adalah dengan menggunakan 2 fungsi rekursif yang saling memanggil satu sama lain. Selain itu anda juga harus bisa memaintain state global/lokal yang dipakai berulang-ulang dalam pemanggilan rekursi tersebut.

Untuk menyelesaikan soal ini, dibutuhkan pengetahuan tentang Euler Path:

Dalam suatu connected graph, untuk bisa membentuk suatu path menggunakan semua edges yang ada di dalam graph tersebut, graph tersebut haruslah memiliki <= 2 node/vertices yang ber-degree ganjil. Definisi degree suatu node adalah total semua incoming dan outgoing edges untuk node tersebut.

Soal domino ini, bisa diubah menjadi soal Euler Path diatas. Caranya adalah dengan membuat graph (possibly disconnected) yang nodes nya terdiri dari angka 0 sampai 6. Dan edges yang menghubungkan kedua node i dan j diberi weight sebanyak kartu domino (i,j) yang ada di input. Definisi dari disconnected graph adalah jika suatu graph tersebut ada 2 node yang tidak terhubung oleh suatu path.

Dari pengetahuan diatas dan pemahaman soal domino, kita bisa simpulkan hal-hal berikut:

  1. Graph input domino mungkin disconnected. Kita harus memprocess satu-persatu connected graph.
  2. Untuk masing-masing connected graph kita perlu menghitung berapa jumlah node yang ber-degree ganjil?
    • Kalau node dengan degree ganjil berjumlah <= 2, maka semua edges di connected graph ini bisa terpakai untuk membuat satu path yang tanpa putus! (Euler Path)
    • Kalau node dengan degree ganjil berjumlah > 2, maka kita harus membuang beberapa edges (sesedikit mungkin) sehingga degree ganjilnya turun menjadi <= 2.
  3. Diantara semua connected graphs yang mungkin terbentuk, kita harus memilih satu connected graph yang bisa menghasilkan satu path terpanjang. Inilah jawabannya.

Coba anda berhenti sejenak, dan lihat ke-3 kesimpulan diatas. Kira-kira seberapa sulit untuk membuat codenya? Berikut saya bahas implementation issue (cara mengimplementasi-nya):

  1. Untuk mencari satu connected graph, bisa dilakukan dengan cara memilih salah satu node X, dan men-traverse graphnya dan menandai node mana saja yang reach-able dari node X (secara langsung maupun tidak langsung). Graph traversal dapat dilakukan dengan cara BFS (Breadth First Search) atau DFS (Depth First Search). Untuk hal ini, DFS saya rasa jauh lebih mudah.
  2. Untuk menghitung jumlah degree (in-degree + out-degree) dari suatu node X, anda tinggal menghitung berapa banyak edges yang keluar dan masuk node X.
    • Misalkan anda mengetahui bahwa suatu connected graph jumlah node ber-degree ganjil adalah <= 2. Maka semua edges di dalam connected graph ini bisa membentuk satu path panjang yang lurus tanpa putus. Nah bagaimana cara anda menghitung berapa banyak kartu domino dalam path ini? Jawabannya adalah total degree graph tersebut dibagi dengan 2 (karena satu kartu domino sebenarnya adalah satu edge di dalam graph dan jumlah edge dalam suatu graph itu adalah sama dengan dua kali jumlah degree dari graph tersebut).
    • Bagian yang tersulit untuk di-implementasi adalah jika jumlah node ber-degree ganjil > 2. Untuk kasus ini anda harus membuang satu atau beberapa edges sehingga jumlah degree ganjil dari connected graph tersebut menjadi <= 2 sehingga anda bisa menghitung path terpanjang (atau jumlah kartu domino) nya sesuai cara diatas lagi. Berikut adalah caranya:
      Cari node yang ber-degree ganjil dan traverse dengan DFS dari node tersebut sambil membuang edge yang dilalui. Kalau ternyata setelah membuang edge tersebut node tujuan menjadi genap, maka anda berhasil membuang sebuah pasangan node ganjil. Dari sini anda bisa kembali ke nomor 1 diatas, dan mengeceknya lagi. Tetapi kali ini anda yakin bahwa jumlah node yang ber-degree ganjil sudah berkurang, dengan begini anda tidak perlu takut dengan endless loop.
  3. Ini bagian termudah, untuk setiap connected graph catatlah dan update jumlah path terpanjang yang bisa dibentuk.

Bagi beberapa orang, mungkin dengan melihat code akan lebih mengerti daripada melihat penjelasan. Silahkan lihat code dibawah. Dua rekursif function yang saling memanggil satu sama lain adalah removeOddPair() dengan longestPath().

#include <stdio.h>
#include <string.h>

int used[7]; // used[i] == 1 artinya rangkaian domino yang mengandung angka i sudah terpakai
int c[7][7]; // c[i][j] menunjukkan berapa banyak domino i-j
int n; // jumlah domino

// gabungan out-degree dan in-degree dari node x
int degree(int x){
    return c[x][x] + c[x][0] + c[x][1] + c[x][2] +
           c[x][3] + c[x][4] + c[x][5] + c[x][6];
}

int oddDegree(int x){
    return degree(x) % 2 == 1;
}

// menghilangkan odd-pair dari suatu graph dengan cara
// mencari semua kemungkinan dari 2 end-point node ganjil
// dan memilih yang menyisakan rangkaian domino terpanjang
int removeOddPair(int i, int vis[7]){
    int longestPath(int);
    int j,ret=0,temp;

    if (!oddDegree(i)) return longestPath(i);
    if (vis[i]) return 0; else vis[i] = 1;

    for (j=0; j<7; j++)
        if (c[i][j]>0 && i!=j && !vis[j]){
            c[i][j]--; c[j][i]--;
            temp = removeOddPair(j,vis);
            c[i][j]++; c[j][i]++;
            if (temp>ret) ret = temp;
        }
    return ret;
}

// menandai node mana saja yang reachable dari node i
void dfs(int i, int vis[7]){
    int j;
    vis[i] = 1;
    for (j=0; j<7; j++)
        if (c[i][j]>0 && !vis[j])
            dfs(j,vis);
}

// mencoba menghitung rangkaian domino yang memiliki node/angka i
// dengan status domino yang sekarang (global variable c)
int longestPath(int i){
    int oddCount = 0;
    int totDegrees = 0;
    int vis[7] = { 0 };
    int j;

    dfs(i,vis);

    for (j=0; j<7; j++)
        if (vis[j]){
            used[j] = 1; // node j sudah terpakai di salah satu rangkaian
            if (oddDegree(j)) oddCount++;
            totDegrees += degree(j);
        }

    if (oddCount<=2){
        // jika node ganjil kurang dari 2, artinya semua domino 
        // bisa dipakai untuk menjalin suatu rangkaian lurus.
        // total dominoes == total all degrees / 2
        return totDegrees / 2; 
    } else {
        // jika node ganjil > 2, kita coba membuang pair node ganjil
        // dan memilih yang bisa membentuk rangkaian lurus terpanjang
        int res = 0;
        for (j=0; j<7; j++)
            if (oddDegree(j)){
                memset(vis,0,sizeof(vis));
                int temp = removeOddPair(j,vis);
                if (temp > res) res = temp;
            }
        return res;
    }
}

int main(){
    while (scanf("%d",&n)!=EOF){
        int i,a,b,res=0;

        // membuat graph untuk domino
        memset(c,0,sizeof(c));
        for (i=0; i<n; i++){
            scanf("%d %d",&a,&b);
            c[a][b]++;
            if (a!=b) c[b][a]++;
        }

        memset(used,0,sizeof(used));
        for (i=0; i<7; i++) if (!used[i]){ 
            // rangkaian dengan angka i belum digunakan/dicari
            // berapakah rangkaian lurus terpanjang menggunakan node/angka i?
            int length = longestPath(i); 
            if (length > res) res = length;
        }

        printf("%d\n",res);
    }
}

Kembali ke halaman utama

Final Indonesia National Contest 2007 :: Problem B - GCD!

ACM/ICPC Indonesia National Contest 2007

Problem B

GCD!

Time Limit: 1s


The greatest common divisor of two numbers is defined as the largest integer that divides both numbers without leaving any reminder. For example, the greatest common divisor of 8 and 12, written as GCD(8,12) is 4, as 4 is the largest integer that divides both 8 and 12 (the common divisors of 8 and 12 are 1, 2, and 4).

Meanwhile, the factorial of a natural number is the product of all positive integers less than or equal to that number. For example, the factorial of 5, written as 5! is 1*2*3*4*5, which equals to 120. By convention, 0! is 1.

Given two integers, n and k, you should find the greatest common divisor of n! and k. For example, if n = 3 and k = 10, then GCD(n!,k) = GCD(3!,10) = GCD(1*2*3,10) = GCD(6,10) = 2. Write a program to find this number!

Input

Each line contains two integers, n (0 <= n <= 1,000,000,000) and k (1 <= k <= 1,000,000,000) respectively.

Output

For each line of input, output one line containing the GCD of n! and k.

Sample Input

3 10
10 240
12 364
100 2351
629 163547

Sample Output

2
240
28
1
67


Problem Setter: Suhendry Effendy


Pembahasan Problem B - GCD!

Hitunglah GCD(n!,k)

GCD (Greatest Common Divisor) dalam bahasa Indonesia adalah FPB (Faktor Persekutuan Terbesar). Untuk mencari GCD(A,B) anda bisa memfaktorisasi A dan B dalam bentuk faktor-faktor prima mereka, dan kemudian memilih faktor berpangkat paling kecil dan mengalikannya kembali.

Contoh:

A = 543312
B = 24570
GCD(A,B) = ?

Kita bisa faktorisasi A dan B menjadi faktor prima mereka:

A = 543312 =  2^4 * 3^2       * 7^3 * 11
B = 24570  =  2^1 * 3^3 * 5^1 * 7^1      * 13

Berikutnya, untuk setiap faktor prima yang bersekutu (common) antara A dan B,
ambil yang berpangkat lebih kecil, kalikan semuanya, itulah hasil GCD(A,B):

GCD(A,B) = 2^1 * 3^2 * 7^1 = 126

Ok, itu gampang... tapi pertanyaannya bukan GCD(N,K) tetapi GCD(N!,K). Bagaimana sekarang?

Untuk ini, anda perlu jurus baru:

Cara menghitung banyaknya faktor X di dalam N faktorial.
Ada cara cepat menghitung hal tersebut, anda bisa lihat artikelnya disini. (blum sempet nyari, internet bapuk)
Setelah anda tahu jurus ini, sisanya sama seperti cara diatas:
Untuk setiap faktor prima P dari K, anda cari ada berapa faktor prima P dalam N!
Lalu ambil yang berpangkat terkecil, kalikan ke dalam hasil akhir.
Silahkan lihat code dibawah untuk lebih jelasnya.

Ada satu trik lagi untuk menghindari time limit dalam pencarian faktor prima P dari K:

Carilah hanya sampai square-root dari K
Karena lebih dari itu, K sudah pasti bilangan prima.

#include <stdio.h>

// ini adalah jurus baru yang dimaksud diatas:
// menghitung jumlah faktor x dalam n!
int factorialPower(int n, int x){
    int res = 0;
    while (n>0){
        res += n/x;
        n /= x;
    }
    return res;
}

int main(){
    int n, k, i, p;

    while (scanf("%d %d",&n,&k)!=EOF){
        int result = 1; // GCD dari 2 bilangan positive apapun minimal adalah 1

        // kita hanya perlu looping p dari 2 .. sqrt(k)
        // untuk mencari faktor-faktor prima p dari k.
        for (p=2; p*p <= k; p++){
            int pPower = 0;
            while (k % p == 0){
                k /= p;   // p disini adalah bilangan prima di penjelasan diatas
                pPower++; // mencari berapa banyak faktor p dalam k
            }
            
            // memilih faktor yang berpangkat lebih kecil antara faktor-faktor dari k
            // dengan faktor-faktor dari n!, tampung pangkat terkecilnya di pPower
            if (pPower > factorialPower(n,p))
                pPower = factorialPower(n,p);

            // kalikan p ke hasil sebanyak pangkat terkecil yang bersekutu (pPower)
            for (i=0; i<pPower; i++) result *= p;
        }

        // sisa k disini adalah bilangan prima (berpangkat 1) dan kalau k lebih kecil
        // atau sama dengan n, maka k termasuk bagian dari GCD
        if (k <= n) result *= k;
        printf("%d\n",result);
    }
}

Kembali ke halaman utama