1972.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1972 on 2006-07-01 at 11:21:00 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1024;
const double INF = 1e20;

int main()
{
	int n, i, j;
	double l, r, pn[N];

	while(scanf("%d", &n) != EOF && n != 0) {
		scanf("%lf %lf", &l, &r);
		if(l < r) swap(l, r);
		pn[0] = 0;
		for(i = 1; i <= n; i++) {
			pn[i] = INF;
			for(j = i/2; j >= 0; j--) {
				int k = i-1-j;
				pn[i] = min(pn[i], (1+pn[j]*l+pn[k]*r)/(1-l-r)+pn[j]+pn[k]);
			}
		}
		printf("%.2lf\n", pn[n]);
	}
	
	return 0;
}