TopCoder problem "ReasonableOdds" used in SRM 405 (Division I Level Three)



Problem Statement

    

When it's impossible to determine a winner after normal soccer play between two teams, a penalty shoot-out is used. During a penalty shoot-out, each of the teams takes k shots (each of those can either result in scoring a goal or not), and the team who scores the most goals is declared the winner. If both teams score an equal number of goals, we will assume in this problem that the game ends in a draw.

We will also assume that for each team there exists a number between 0 and 1, inclusive, denoting the skill level of that team, such that each penalty shot taken by that team results in a goal with probability equal to that number. You can assume that all shots are independent.

Your friend, an eager sports better, tells you that he knows that team 1 will win with probability p1%, team 2 will win with probability p2%, and the probability of a draw is pDraw%. You need to check if such a probability distribution is possible. In other words, can there exist two teams with valid skill levels such that those three outcomes would happen with the given probabilities?

Given ints p1, pDraw, p2 and k, return "YES" if such a distribution is possible, and "NO" otherwise (quotes for clarity only).

 

Definition

    
Class:ReasonableOdds
Method:check
Parameters:int, int, int, int
Returns:String
Method signature:String check(int p1, int pDraw, int p2, int k)
(be sure your method is public)
    
 

Constraints

-p1, pDraw and p2 will be between 0 and 100, inclusive.
-p1, pDraw and p2 will sum up to 100.
-k will be between 1 and 5, inclusive.
 

Examples

0)
    
0
100
0
1
Returns: "YES"
When both teams have a skill level of 0, a draw is unavoidable.
1)
    
50
0
50
1
Returns: "NO"
When both teams can win, a draw is also a possibility.
2)
    
30
0
70
5
Returns: "NO"
3)
    
30
10
60
2
Returns: "NO"
Moreover, a draw is a significant possibility.
4)
    
30
40
30
2
Returns: "YES"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9744

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12177&pm=9744

Writer:

Petr

Testers:

PabloGilberto , Olexiy , Jan_Kuipers , ivan_metelsky

Problem categories:

Math, Simulation