POJ 2199 - Rate of Return

http://poj.org/problem?id=2199

概要

\(m_j\) 月の最初に \(x_j\) ドル投資をした結果、\(M\) 月の最後には \(X\) になっていた、という情報が与えられる。 このとき、一月あたりの金利 \(i\) を答える。

たとえば金利が \(i\) のとき、1月の最初に100ドル、3月の最初にもう100ドル投資したとすると、 4月の最後には \(100 \cdot (1+i) ^ 4 + 100 \cdot (1+i) ^ 2\) ドルになっている。

制約

解法

方程式を解くだけ。 最終的な金額を表す式は \(i\) に関して単調増加であるため、二分探索すればいい。

 1 #include <cstdio>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   for (int Ti = 1; scanf("%d", &N) != EOF && N != -1; Ti++) {
 9     double c[16];
10     for (int i = 0; i <16; i++) {
11       c[i] = 0.0;
12     }
13     for (int i = 0; i < N; i++) {
14       int mon;
15       double x;
16       scanf("%d %lf", &mon, &x);
17       c[mon] = x;
18     }
19     int lastmon;
20     double amount;
21     scanf("%d %lf", &lastmon, &amount);
22     double lo = 0.0, hi = 1.0;
23     for (int i = 0; i < 100; i++) {
24       const double mid = (lo + hi)/2.0;
25       double x = 0.0;
26       for (int j = 1; j <= lastmon; j++) {
27         x += c[j] * pow(mid+1, double(lastmon-j+1));
28       }
29       if (x < amount) {
30         lo = mid;
31       } else {
32         hi = mid;
33       }
34     }
35     printf("Case %d: %.5f\n\n", Ti, (lo+hi)/2.0);
36   }
37   return 0;
38 }
poj/2199.cc