bodipy 581/591,gym red

主题Problem E. Bet的链接

input file : output file : time limit : standardinputstandardouptut1second the 2016 ACM-icpcasiachina-final contest

The Codejamon game is on fire！ fansacrosstheworldarepredictingandbettingonwhichteamwillwinthegame。

agamblingcompanyisprovidingbettingoddsforallteams； theoddsfortheithteamisai : bi。

For each team，youcanbetanypositiveamountofmoney，and you do not have to bet the same

amountoneachteam.iftheithteamwins，you get your bet on that team back，plus Bi times

your bet on that team .喜欢的豌豆pAi

For example，suppose that there are two teams，withoddsof 5:3 and 233607 and you bet $ 20 on the

firstteamand $ 10 onthesecondteam.ifthefirstteamwins，you will lose your $10 bet on the

第二个team，butyouwillreceiveyour $ 20 bet back，plus 3 20=12，so you will have a total5

of $ 32at the end.ifthesecondteamwins，youwillloseyour $ 20 betonthefirstteam，butyouwillreceiveyour $ 10bet back，plus710

way，youwillhavemoremoneythanyoubet ($ 20 $ 10=$ 30 )。

As a greedy fan，youwanttobetonasmanyteamsaspossibletomakesurethataslongasoneofthemwins，youwillalwaysendupwithmoremoneythanythanyous

输入输出

theinputstartswithonelinecontainingexactlyoneintegert，which is the number of test cases。

eachtestcasestartswithonelinecontaininganintegern : thenumberofteamsinthegame.then， nmorelinesfollow.eachlineisapairofnumbersintheformai : bi (thatis，a numberAi，followed by a colon，then a number Bi，withno

输出

For each test case，outputonelinecontaining“case # x : y”，wherexisthetestcasenumber (starting from1) andyisthemaximumumber

利米茨

1t100。

1n100。

•

0<Ai,Bi <100.
• Both Ai and Bi have at most 3 digits after the decimal point.

Page 6 of 21

The 2016 ACM-ICPC Asia China-Final Contest

Sample input and output

Note

In sample case #1, one optimal strategy is to bet 1.5 dollars on the first team and 1.5 dollars onthe third team. If the first team wins, you will get 1.5 + 1.5 × (1.1/1) = 3.15 dollars back, and ifthe third team wins, you will get 1.5 + (1.7/1.5) × 1.5 = 3.2 dollars back. Both of these are higherthan the total money that you bet (1.5 + 1.5 = 3 dollars).

However, there is no way to bet on all three teams and be guaranteed a profit.

参考题解题意：有一个赌博游戏，给出n个队的赔率A:B，问你最多能下注多少个队，才能使得不论你下注的这些队中哪一个队赢了你都可以赚，也就是最后所得金额大于下注的总额。对于一个队，假设下注x，如果输了，那么你将失去x，如果赢了，你将额外得到（B／A）*x，也就是最后有x+（B／A）*x。题解：先用数学翻译一下此题，其实很简单就可以推出一个不等式：用Pi代表我下注的总额中第i个队占的金额占比，应有： Pi(1+Bi/Ai)>1 即： Pi > Ai/(Ai+Bi) 要使得尽可能下注多的队，就将所有队的Ai/(Ai+Bi)从小到大排序，挨着取，直到总和>=1 上面的博客说这一题需要高精度，然后手写了一个高精度除法，后来我在gym上点开一个AC代码发现用long double存也能过。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>#include<cmath>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int maxn=100+10;long double p[maxn];int main(){ int cas; scanf("%d",&cas); for(int k=1;k<=cas;k++) { int n; scanf("%d",&n); double x,y; rep(i,1,n+1) { scanf("%lf:%lf",&x,&y); int x1=floor(x*1000),y1=floor(y*1000); p[i]=1.0*x1/(x1+y1); } long double sum=0; sort(p+1,p+n+1); int cnt=0; rep(i,1,n+1) { sum+=p[i]; if(sum>=1) break; cnt++; } printf("Case #%d: %dn",k,cnt); } return 0;}