I NEED A OFFER!

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5280 Accepted Submission(s): 1799

Problem Description

Speakless很早就想出国，现在他已经考完了所有须要的测验，预备了所有要预备的资料，于是，便须要去申请黉舍了。要申请外洋的任何大学，你都要缴纳必定的申请费用，这可是很惊人的。Speakless没有多少钱，统共只攒了n万美元。他将在m个黉舍中选择多少的（当然要在他的经济承受范围内）。每个黉舍都有不同的申请费用a（万美元），并且Speakless估计了他失掉这个黉舍offer的可能性b。不同黉舍之间是否失掉offer不会互相影响。“I NEED A OFFER”，他大呼一声。帮帮这个可怜的人吧，帮助他盘算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个黉舍，失掉恣意一个黉舍的offer都可以）。

Input

输入有多少组数据，每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=1000)

后面的m行，每行都有两个数据ai(整型),bi(实型)分别表示第i个黉舍的申请费用和可能拿到offer的概率。

输入的最后有两个0。

Output

每组数据都对应一个输出，表示Speakless可能失掉至少一份offer的最大概率。用百分数表示，准确到小数点后一位。

Sample Input

      10 3 4 0.1 4 0.2 5 0.3 0 0 

Sample Output

每日一道理

只有启程，才会到达理想和目的地，只有拼搏，才会获得辉煌的成功，只有播种，才会有收获。只有追求，才会品味堂堂正正的人。

      44.0% 
Hint
 You should use printf("%%") to print a '%'. 
       简单0、1背包 
       反过来求不可能的概率。让 bi=1.0-bi , 最后结果就 1.0 - f[n]。 
       转移方程：f[j] = max{f[j-a[i]]*b[i]}; ｛也可以不要让bi=1.0-bi。那转移方程为 f[j] = min{1-(1-b[i])*(1-f[j-a[i])｝ 
       code: 

文章结束给大家分享下程序员的一些笑话语录：程序员的愿望

　　有一天一个程序员见到了上帝.上帝: 小伙子,我可以满足你一个愿望.程序员: 我希望中国国家队能再次打进世界杯.

　　上帝: 这个啊!这个不好办啊,你还说下一个吧!

　　程序员: 那好!我的下一个愿望是每天都能休息6个小时以上.

　　上帝: 还是让中国国家打进世界杯.

--------------------------------- 原创文章 By

概率和数据

---------------------------------

转载于:https://www.cnblogs.com/jiangu66/archive/2013/05/24/3097619.html

你可能感兴趣的文章