ACM/ICPC Indonesia National Contest 2007 - Qualification

Problem B

Avoiding Financial Nightmare

Time Limit: 1s

Nowadays, getting a loan from a bank or financial company has become very popular, either it's for commercial or personal purposes. If you are a well-managed on your expenses, having a loan from a bank or using credit cards for your expenses could be a good help, otherwise it could be your worst financial nightmare. By considering the risks of paying bills, our professor has decided to get a loan to buy a new house on a pleasant city in Indonesia.

Our professor has considered 3 main variables that will affect his monthly bills:

Principal, the remaining amount of the loan

Period, the number of months to pay off the loan

Rate, the monthly interest rate

To help their customer, bank or financial company normally offers a fixed amount payment system. Every month the customer should pay a fixed amount of money which consists of two kinds of payment:

Interest Payment.
Interest Payment = Rate x Remaining Principal.
The amount of interest payment should be rounded up to the higher nearest integer.
Principal Payment.
Principal Payment = Total Payment - Interest Payment.
The previous Principal is to be subtracted with the current Principal Payment to get the current Principal.

The total monthly payment should be calculated in some way so that the total monthly payment to be paid spread evenly each month, and at the end of the period the remaining Principal is zero or a negative amount nearest to zero (if it's not possible to reach zero).

For example, let the professor get a loan in the amount of $42,000 with 5% interest rate per month that should be paid in 5 months.

Term	Payment			Principal
Term	Total	Interest Payment	Principal Payment	Principal
-	-	-	-	$42,000
1	$9,701	$2,100	$7,601	$34,399
2	$9,701	$1,720	$7,981	$26,418
3	$9,701	$1,321	$8,380	$18,038
4	$9,701	$902	$8,799	$9,239
5	$9,701	$462	$9,239	$0

1^st term: He should pay $9,701 ($2,100 for interest payment, and $7,601 for principal payment)
Interest Payment : 5% x $42,000 = $2,100
Principal Payment : $9,701 - $2,100 = $7,601
Current Principal : $42,000 - $7,601 = $34,399

2^nd term: He pays $9,701 ($1,702 for interest payment, and $7,981 for principal payment)
Interest Payment : 5% x $34,399 = $1,720
Principal Payment : $9,701 - $1,720 = $6,902
Current Principal : $34,399 - $6,902 = $26,418, and so on.

Unfortunately, the professor is terrible with financial stuffs. We don't want him to end up broke, do we? So, let us help him with the calculation on how much money he should spend to pay his monthly bills on the loan. In that way, the professor will be able to buy his new house and who knows that someday we might be invited to visit his house in return to our help.

Input Specification

The input contains multiple cases. Each case consists of three integers respectively, N (1<=N<=10,000,000) the initial principal, M (1<=M<=100) the period, and R (0<=R<=100) the percent rate.

Output Specification

For each case, you should output in a single line the total monthly payment should be made to satisfy the condition.

Sample Input

42000 5 5
100000 10 10

Sample Output

9701
16275

Problem Setter: Bong Win Ce

Pembahasan 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);
    }
}

Back to Home

Sunday, June 10, 2007

Penyisihan Indonesia National Contest 2007 :: Problem B - Avoiding Financial Nightmare