Connection Status:
Competition Arena > FixedDiceGameDiv1

FixedDiceGameDiv1

SRM 626 · 2013-12-22 · by lg5293

SRM 626 · 2013-12-22 · by lg5293 · Advanced Math, Dynamic Programming
Class Name: FixedDiceGameDiv1
Return Type: double
Method Name: getExpectation
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

Alice and Bob are playing a game. Alice rolls a identical b-sided dice. Bob rolls c identical d-sided dice. The sides of an n-sided die have numbers 1 through n written on them.

A player's score is the sum of the numbers they rolled on their dice. The player with a strictly higher score wins. It is possible that neither player wins.

You are given the ints a, b, c, and d. The players already rolled their dice. If it's not possible for Alice to win, return -1. Otherwise, assume that you don't know what numbers Alice and Bob rolled, but that you know that Alice won the game. Return the expected value of Alice's score (given the above assumption).

Notes

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

Constraints

  • a, b, c, d will each be between 1 and 50, inclusive.
Examples
0)
1
2
1
5
Returns: 2.0

The only way Alice can win is if she rolls a 2. Thus, if we know Alice wins, we know she rolled a 2.

1)
3
1
1
3
Returns: 3.0

Alice will always roll a 3.

2)
1
5
1
1
Returns: 3.4999999999999996

Alice will not win if she rolls a 1. Thus, if we know she wins, her expected score is (2+3+4+5)/4=7/2.

3)
2
6
50
30
Returns: -1.0

No matter what Alice rolls, she will lose.

4)
50
11
50
50
Returns: 369.8865999182022
5)
50
50
50
50
Returns: 1332.7589106984374

max bounds

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

Coding Area

Language: C++17 · define a public class FixedDiceGameDiv1 with a public method double getExpectation(int a, int b, int c, int d) · 71 test cases · 2 s / 256 MB per case

Submitting as anonymous