Problem B - Avoiding Financial Nightmare

Berapakah biaya bulanan yang harus anda bayar sehingga hutang nya lunas tepat 0 di bulan terakhir atau negative sedikit (jika tidak bisa 0). Cara pembayaran per bulan bisa dilihat rumusnya pada soal, silahkan click problem statement soal diatas. Jika anda sudah mengerti perhitungan di tabel soal, maka yang perlu anda cari adalah berapa total biaya perbulan yang harus dibayar?

Jebakan untuk soal ini ada 2. Yang pertama adalah Interest Payment harus dibulatkan keatas. Yang kedua, anda akan kena overflow kalau tidak menggunakan tipe data long long di C/C++ atau long di Java. Jika anda mengetahui kedua jebakan ini, anda tetap tidak akan bisa memecahkan soal ini jika tidak tahu algoritma Binary Search. Mungkin saja soal ini bisa diselesaikan hanya dalam 1 rumus, tetapi karena pembulatan saya kira ini akan sangat susah.

Algoritma binary search analoginya adalah seperti anda mencari suatu kata dalam kamus yang terurut. Dalam kasus problem ini, yang harus anda binary-search adalah "biaya yang harus anda bayar per-bulan". Untuk lebih jelasnya, anda bisa lihat code dibawah. Singkat, padat, jelas :) (saya rasa tidak perlu membuat versi Java atau C++ nya, cuma sedikit sih).

#include <stdio.h>

int N, M, R;

// pakailah long long untuk menghindari overflow
long long balance(long long monthly){
    long long P = N, i;
    for (i=0; i<M; i++){
        // ingat, Interest Payment dibulatkan keatas
        long long I = (R * P + 99) / 100;
        P -= monthly - I;
    }
    return P;
}

int main(){
    while (scanf("%d %d %d",&N,&M,&R)!=EOF){
        int lo = 0, hi = 3*N, res; // jawaban tidak mungkin lebih besar dari 3*N
        // ini algoritma binary search
        while (lo<=hi){
            int med = (lo+hi)/2;
            if (balance(med) <= 0){
                res = med; // jawaban ditemukan saat nilai balance == 0 atau negative sedikit
                hi = med-1;
            } else {
                lo = med+1;
            }
        }
        printf("%d\n",res);
    }
}

Lihat problem lain:

1. The Chosen Sub Matrix
2. Avoiding Financial Nightmare
3. No Pause Telegraph
4. Burger, French Fries, Soft Drink
5. Taxi!