Jill has been investing in a mutual fund for a while. Since her income has varied, the amount of money she has added to the investment has varied, and she hasn’t always added to the investment at regular intervals. Nevertheless, she does have a complete record of the amounts she has invested, and the dates of those investments.

Periodically Jill gets a report that indicates the total value of her investment. She wonders if she would have done better by investing her money in a savings account that pays a fixed interest rate. But to determine the answer to this question, she needs to know what the equivalent interest rate would have been paid on the mutual fund, had it paid a fixed rate. You are going to help her.

For simplicity we will assume that Jill added money to her mutual fund only at the beginning of a month, and that all months have the same length. We will further assume that the interest she would have been paid had she invested in a savings account would have been paid at the end of the month, and would have been compounded monthly.

Let’s consider a simple example. Suppose Jill invested $100 at the beginning of January and another $100 in March. At the end of April she finds that the value of her mutual fund is $210. If the equivalent fixed monthly interest rate was i, then we know that at the end of January the value would have been 100 × (1 + i). At the end of February the value would have been 100 × (1 + i) × (1 + i), or 100 × (1 + i)². At the end of March, the value would have been 100 × (1 + i)³ + 100 × (1 + i), and at the end of April, the value would have been 100 × (1 + i)⁴ + 100 × (1 + i)². So the question to be answered in this case is this: what is the value of i such that 100 × (1 + i)⁴ + 100 × (1 + i)² = 210? The answer for this case is close to 0.016351795234.

2   1   100.00    3100.00    4   210.0031 100.002 50.005 200.007 358.41  -1

Case 1: 0.01635Case 2: 0.00520

这题用二分法求解就很简单，但是有一点要注意，就是它的输入是升序的，但不是单调增的，因为我的代码在直接用month做下标的时候是错的，然后改用数组储存月份就过了，说明它的月份是有重复的，也就是一个人在同一个月储存了几次。

#include <iostream>#include <cstdio>#include <cmath>#include <cstring>using namespace std;const double eps = 1e-6;int dcmp(double x){    return (x > -eps && x < eps) ? 0 : 1;}int main(int argc, char const *argv[]){    int N, month[14];    double moneyIn[14], lastMoney, lastMonth;    int testNum = 0;    while (cin >> N && N != -1) {        memset(moneyIn, 0.0, sizeof(moneyIn));        for (int i = 0; i < N; ++i) {            cin >> month[i];            cin >> moneyIn[i];        }        cin >> lastMonth >> lastMoney;        double lastMoneyT = 0.0, rateE = 2.0, rateB = 1.0, rate = 1.5;        lastMoneyT = 0.0;        for (int i = 0; i < N; ++i)            lastMoneyT += moneyIn[i] * pow(rate, lastMonth - month[i] + 1);        while (dcmp(lastMoneyT - lastMoney) != 0 && rateE - rateB >= 1e-6) {            if (lastMoneyT > lastMoney)                rateE = rate;            else                rateB = rate;                        rate = (rateE + rateB) / 2;            lastMoneyT = 0.0;            for (int i = 0; i < N; ++i)                lastMoneyT += moneyIn[i] * pow(rate, lastMonth - month[i] + 1);        }        if (++testNum > 1)            cout << endl;        printf("Case %d: %.5lf\n", testNum, rate - 1);    }    return 0;}