In finance, Internal Rate of Return (IRR) is the discount rate of an investment when NPV equals zero. Formally, given TCFCF, ..., CF, then IRR is the solution to the following equation:

NPV = CF + UVA 11881 Internal Rate of Return(数学+二分)-LMLPHP + UVA 11881 Internal Rate of Return(数学+二分)-LMLPHP + K + UVA 11881 Internal Rate of Return(数学+二分)-LMLPHP = 0

Your task is to find all valid IRRs. In this problem, the initial cash-flow CF < 0, while other cash-flows are all positive (CF > 0 for all i = 1, 2,...).

Important: IRR can be negative, but it must be satisfied that IRR > - 1.

Input

There will be at most 25 test cases. Each test case contains two lines. The first line contains a single integer T ( 1UVA 11881 Internal Rate of Return(数学+二分)-LMLPHPTUVA 11881 Internal Rate of Return(数学+二分)-LMLPHP10), the number of positive cash-flows. The second line contains T + 1 integers: CFCF,CF, ..., CF, where CF < 0, 0 < CF < 10000 ( i = 1, 2,..., T). The input terminates by T = 0.

Output

For each test case, print a single line, containing the value of IRR, rounded to two decimal points. If noIRR exists, print ``No" (without quotes); if there are multiple IRRs, print ``Too many"(without quotes).

题目大意:给出CF[0]<0,CF[i]>0,i>0,求IRR(IRR>-1)令NPV = 0.

思路:设f(IRR) = NPV,这就变成了一个函数,稍微观察一下,可以发现当IRR∈(-1, +∞)的时候是单调递减的(好像是吧做完忘了),这样我们就可以二分答案0点了。当IRR无限接近-1的时候,f(IRR)→+∞(好像是吧),当IRR→+∞时,f(IRR)→CF[0]<0,令left = -1、right = 1e5(我也不知道该取什么我随便取的然后AC了),随便二分一下就好。

PS:恩?说完了?那什么时候输出No和Too many啊?关于这个坑爹的问题,看完前面的分析,笔者完全不知道什么时候会出现这两个答案,于是妥妥地没将这两个东西写进代码然后AC了。这里还有一个小技巧,题目的样例完全没有出现No和Too many这两种答案,很可能说明这两种答案都是不存在的。比如很多的题目说如果什么什么得不到答案就输出-1那样,它的样例大多都会有一个是输出-1的,当然这不是绝对的……

代码(15MS):

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std; const int MAXN = ;
const double EPS = 1e-; inline int sgn(double x) {
if(fabs(x) < EPS) return ;
return x > ? : -;
} int CF[MAXN];
int T; double f(double IRR) {
double ret = CF[], tmp = + IRR;
for(int i = ; i <= T; ++i) {
ret += CF[i] / tmp;
tmp = tmp * ( + IRR);
}
return ret;
} double solve() {
double ans = -;
double L = -, R = 1e5;
while(R - L > EPS) {
double mid = (R + L) / ;
if(sgn(f(mid)) == ) L = mid;
else R = mid;
}
return ans = L;
} int main() {
while(scanf("%d", &T) != EOF) {
if(T == ) break;
for(int i = ; i <= T; ++i) scanf("%d", &CF[i]);
//double t; while(cin>>t) cout<<f(t)<<endl;
printf("%.2f\n", solve());
}
}
05-11 13:17