Intergalactic Mortgage

Interview

Time limit1sMemory limit128 MB

Summary
Simulate monthly compound interest at r/12 percent on a debt, subtract a fixed payment, and report whether the balance reaches zero within N years.
Level

Medium4 of 10

Topics
Simulation, Math, Implementation, Binary search
Solved
No attempts yet

Problem

Many people on Earth want to solve their housing needs. When they don't have enough money to buy a house or a flat, they take a mortgage from a bank and then pay fixed monthly payments until the mortgage is fully repaid.

You may think that paying a mortgage for 30 years is a long time, but it is quite short compared to galactic mortgages. Aliens don't buy houses — they buy whole planets. Since planets are "a little" more expensive, the mortgage periods are much longer.

Mortgages work the same way for aliens as for us earthlings. If an alien wants to buy a planet, he goes to the GCB (Galactic Central Bank) to borrow an amount XX. The bank offers a mortgage with an annual interest rate of r%r\% (per year). Interest is computed at the end of each month (one alien year has 12 months). At the end of every month, the current debt grows by (r/12)%(r/12)\%, and then the alien pays the bank a fixed amount YY, which is subtracted from the debt.

Because of the intergalactic financial crisis, the bank's rules are strict. Every mortgage must start on the first day of a year. If, within the first NN years, the alien does not pay enough to cover the principal and interest, the bank confiscates his planet.

On the other hand, galactic employment is quite stable. Once you have a job, you keep it forever, so the alien can pay the same amount YY at the end of every month for the entire mortgage period.

Decide whether the alien is able to pay off his mortgage.

Input

The input contains several test cases. Each test case is given on one line containing the numbers XX, YY, NN, rr separated by spaces. XX is the principal (the initial amount borrowed), YY is the monthly payment (paid at the end of each month), NN is the number of years within which the alien must repay the mortgage, and rr is the annual interest rate in percent.

XX and YY are integers (1≤X,Y≤1 000 000 0001 \le X, Y \le 1\,000\,000\,000). NN is an integer (1≤N≤10 0001 \le N \le 10\,000). rr is a real number with two digits of precision (0≤r≤1000 \le r \le 100). For each test case, the values XX, YY, NN, rr are chosen so that even if the alien paid nothing for the whole time, the resulting debt after NN years would be at most 102510^{25}. The precision of a double is also sufficient for most computations (a difference in the rate of less than 10−8%10^{-8}\% will not affect the result).

The last test case is followed by a line containing four zeros.

Output

For each test case, output "YES" if the alien can repay the mortgage within NN years, and "NO" if his salary is too small to repay the mortgage in time.

Examples1

  1. Example 1

    Input
    10000 500 2 5.00
    10000 400 2 5.00
    10000 245 100 30.00
    321321321 2895492 11 3.23
    0 0 0 0
    
    Expected output
    YES
    NO
    NO
    NO