Connection Status:
Competition Arena > ScrabbleBet

ScrabbleBet

SRM 293 · 2006-03-17 · by supernova

SRM 293 · 2006-03-17 · by supernova · Brute Force, Math
Class Name: ScrabbleBet
Return Type: double
Method Name: estimate
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

One Saturday evening you are playing a game of online Scrabble. Your opponent is a very good player, but this time you managed to win. After a brief conversation, you are told: "I am clearly better than you, but one game is simply not enough to prove it." Your opponent then makess the following bet: "If we play 10 games, you will win less than 5 ... and this will happen every time, even if we try this 10 times in a row!".

You will solve a more general problem using the following parameters:
- an int trials denoting the number of meetings in which a set of games is played.
- an int games denoting the number of games that are to be played in each meeting.
- an int winsNeeded denoting the number of victories you need in one of the meetings to win the bet.
- an int winChance denoting the probability in percent of winning one particular game.

Return a double between 0 and 1, denoting the probability you have to win the bet.

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • trials will be between 1 and 50, inclusive.
  • games will be between 1 and 20, inclusive.
  • winsNeeded will be between 1 and games, inclusive.
  • winChance will be between 0 and 100, inclusive.
Examples
0)
2
2
1
50
Returns: 0.9375

There are 4 possible ways a meeting could evolve: - you lose both games. - you lose game 1 and you win game 2. - you win game 1 and you lose game 2. - you win both games. Your opponent has a 1/4 chance of not losing the bet after the first meeting. Since there are two meetings, your opponent's chances to win the bet are 1/4 * 1/4 = 1/16. Thus, you have a 15/16 chance to win the bet.

1)
2
2
2
50
Returns: 0.4375

This time your opponent has a 3/4 chance of not losing the bet after one meeting and a 9/16 chance of not losing the bet after the two meetings. Your chances are now 1 - 9/16 = 7/16.

2)
10
10
5
25
Returns: 0.5566860567603682
3)
2
20
5
10
Returns: 0.08448495352665641
4)
50
15
1
0
Returns: 0.0

Submissions are judged against all 108 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ScrabbleBet with a public method double estimate(int trials, int games, int winsNeeded, int winChance) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous