gym101194 china final Problem E. Bet(数学,高精度)-白红宇的个人博客

gym101194 china final Problem E. Bet(数学,高精度)

发布日期：2021-11-12 00:25:56 浏览次数：4 分类：技术文章

本文共 3612 字，大约阅读时间需要 12 分钟。

Problem E. Bet

Input file:Output file: Time limit:

Standard InputStandard Ouptut1 second

The 2016 ACM-ICPC Asia China-Final Contest

The Codejamon game is on fire! Fans across the world are predicting and betting on which teamwill win the game.

A gambling company is providing betting odds for all teams; the odds for the ith team is Ai:Bi.

For each team, you can bet any positive amount of money, and you do not have to bet the same

amount on each team. If the ith team wins, you get your bet on that team back, plus Bi times

your bet on that team.

For example, suppose that there are two teams, with odds of 5:3 and 2:7 and you bet $20 on the

first team and $10 on the second team. If the first team wins, you will lose your $10 bet on the

second team, but you will receive your $20 bet back, plus 3 × 20 = 12, so you will have a total5

of $32 at the end. If the second team wins, you will lose your $20 bet on the first team, but youwill receive your $10 bet back, plus 7 × 10 = 35, so you will have a total of $45 at the end. Either

way, you will have more money than you bet ($20+$10=$30).

As a greedy fan, you want to bet on as many teams as possible to make sure that as long as oneof them wins, you will always end up with more money than you bet. Can you figure out howmany teams you can bet on?

Input

The input starts with one line containing exactly one integer T , which is the number of test cases.

Each test case starts with one line containing an integer N: the number of teams in the game.Then, N more lines follow. Each line is a pair of numbers in the form Ai:Bi (that is, a numberAi, followed by a colon, then a number Bi, with no spaces in between), indicating the odds forthe ith team.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number(starting from 1) and y is the maximum number of teams that you can bet on, under the conditionsspecified in the problem statement.

Limits

• 1≤T ≤100.

• 1 ≤ N ≤ 100.

• 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
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define rep(i,a,n) for (int i=a;i
           
            =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
            
              VI;typedef long long ll;typedef pair
             
               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: %d\n",k,cnt); } return 0;}

转载地址：https://blog.csdn.net/fouzhe/article/details/56665763 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：gym101194 china final Problem D. Ice Cream Tower(二分)

下一篇：Codeforces Round #398 (Div. 2) E. Change-free(想法题,贪心,好题)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章