FZU 2221—— RunningMan——————【线性规划】

 Problem 2221 RunningMan

Accept: 17    Submit: 52
Time Limit: 1000 mSec    Memory Limit : 32768 KB

FZU 2221—— RunningMan——————【线性规划】 Problem Description

ZB loves watching RunningMan! There's a game in RunningMan called 100 vs 100.

There are two teams, each of many people. There are 3 rounds of fighting, in each round the two teams send some people to fight. In each round, whichever team sends more people wins, and if the two teams send the same amount of people, RunningMan team wins. Each person can be sent out to only one round. The team wins 2 rounds win the whole game. Note, the arrangement of the fighter in three rounds must be decided before the whole game starts.

We know that there are N people on the RunningMan team, and that there are M people on the opposite team. Now zb wants to know whether there exists an arrangement of people for the RunningMan team so that they can always win, no matter how the opposite team arrange their people.

FZU 2221—— RunningMan——————【线性规划】 Input

The first line contains an integer T, meaning the number of the cases. 1 <= T <= 50.

For each test case, there's one line consists of two integers N and M. (1 <= N, M <= 10^9).

FZU 2221—— RunningMan——————【线性规划】 Output

For each test case, Output "Yes" if there exists an arrangement of people so that the RunningMan team can always win. "No" if there isn't such an arrangement. (Without the quotation marks.)

FZU 2221—— RunningMan——————【线性规划】 Sample Input

2
100 100
200 100

FZU 2221—— RunningMan——————【线性规划】 Sample Output

No
Yes

FZU 2221—— RunningMan——————【线性规划】 Hint

In the second example, the RunningMan team can arrange 60, 60, 80 people for the three rounds. No matter how the opposite team arrange their 100 people, they cannot win.

FZU 2221—— RunningMan——————【线性规划】 Source

第六届福建省大学生程序设计竞赛-重现赛(感谢承办方华侨大学)

 
题目大意:给你两个数,代表R,O两组的总人数n,m,现在玩三轮游戏,三局两胜,如果R组派出的人数大于等于本轮O组派出的人数,那么R组获胜,否则O组获胜,问你是否存在一种安排,不论O组怎么派队,R组都胜利。存在即输出Yes,否则输出No。
 
解题思路:现在将R组分为3队,人数为x,y,z。那么如果满足题意,则R组中每两个队伍都必须获胜,另外一队必输。
需同时满足: x+y >= m-1    表示:x,y两队胜,z队输。z队队员0个人跟O组除了跟x,y对战的另一队人数为1人对战,失败。
       x+z >= m-1
       y+z >= m-1 且 x+y+z = n
联立方程组,解得 n >= 3*(m-1)/2
 
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int main(){
int T,n,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
if(n >= 1.5*(m-1)){
puts("Yes");
}else{
puts("No");
}
}
return 0;
}

  

 
 
上一篇:[UOJ]#36. 【清华集训2014】玛里苟斯


下一篇:FZu Problem 2236 第十四个目标 (线段树 + dp)