Problem Statement
This problem has a non-standard time limit: 4 seconds.
This problem is about a specific way of rolling the dice in one franchise of tabletop RPG games.
Whenever the player attempts a non-trivial action, the action is evaluated as follows:
- The game master sets the target value T based on the player's skill.
- The game master gives the player some 6-sided dice to roll. Each die is either positive or negative.
- The player rolls all the dice.
- As long as there is a positive and a negative die with the same value, a pair of such dice is removed from the roll.
- At this point, if there is a positive die with value less than or equal to the target, the roll is a success, otherwise it is a failure.
- Each negative die that was not removed counts as a point of stress for the player. In this problem the points of stress do not matter and can be ignored.
For example, suppose the player had the target T = 5 and rolled P = 4 positive and N = 6 negative dice, getting the values {3, 6, 3, 6} on the positive dice and the values {2, 3, 1, 6, 3, 3} on the negative dice. To evaluate this roll, we first remove several pairs of a positive and a negative die with the same value (value 3 twice and value 6 once). Once we do that, we now see {6} on the only remaining positive die and {2, 1, 3} on the three remaining negative dice. Thus, the roll is a failure and the player receives three points of stress.
You are given the target T, the number P of positive dice and the number N of negative dice. Calculate p: the probability that the roll will be a success. Return (p * 6P+N) modulo 1,000,000,007.
Definition
- Class:
- ZombieRPGDice
- Method:
- expectation
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int expectation(int T, int P, int N)
- (be sure your method is public)
Notes
- It should be obvious that the value (p * 6P+N) is always a non-negative integer, and thus the return value is well-defined.
Constraints
- T will be between 1 and 6, inclusive.
- P will be between 0 and 250, inclusive.
- N will be between 0 and 250, inclusive.
Examples
5
1
0
Returns: 5
There is one positive die and no negative dice, the target is 5. The roll will be a success if we roll anything other than a six. The probability of success is p = 5/6, and thus the correct return value is p*6 = 5.
3
0
7
Returns: 0
With only negative dice there can be no success.
4
1
1
Returns: 20
In order to be successful, we need to roll 1, 2, 3, or 4 on the positive die, and we need the negative die to differ from the positive die. The probability that both things happen is p = (4/6) * (5/6) = 20/36.
6
15
0
Returns: 184981286
Remember to use modular arithmetic. The return value shown here is 6^15 modulo (10^9 + 7).
5
4
6
Returns: 50489560
3
0
0
Returns: 0
No dice at all = no success.
6
0
0
Returns: 0
5
250
250
Returns: 491881721
4
2
2
Returns: 948
3
0
3
Returns: 0
3
162
221
Returns: 499207927
4
233
232
Returns: 66756861
6
0
0
Returns: 0
1
144
125
Returns: 416777524
1
230
243
Returns: 60011691
6
0
2
Returns: 0
1
150
25
Returns: 979279195
5
231
242
Returns: 189915290
6
176
235
Returns: 514708494
1
249
243
Returns: 635864704
2
0
1
Returns: 0
1
2
0
Returns: 11
4
240
231
Returns: 915644597
3
142
13
Returns: 857826015
5
219
146
Returns: 362702228
2
243
240
Returns: 942765671
5
3
2
Returns: 7440
3
10
197
Returns: 192831477
5
0
0
Returns: 0
5
38
140
Returns: 104428302
3
138
123
Returns: 779317467
2
182
15
Returns: 887711823
4
230
242
Returns: 48244098
3
242
240
Returns: 354949843
1
0
3
Returns: 0
4
243
237
Returns: 633730082
3
3
1
Returns: 1053
2
3
0
Returns: 152
5
216
194
Returns: 973115335
4
3
0
Returns: 208
3
3
3
Returns: 31308
4
244
250
Returns: 270793273
5
248
246
Returns: 96937661
5
1
1
Returns: 25
6
2
2
Returns: 1230
6
1
0
Returns: 6
4
243
247
Returns: 349386185
5
78
61
Returns: 164676146
6
151
153
Returns: 240615830
1
111
207
Returns: 115512375
1
225
133
Returns: 933875682
1
249
235
Returns: 420548791
2
2
3
Returns: 2772
3
240
247
Returns: 320096383
1
246
143
Returns: 291685005
3
233
246
Returns: 7169017
4
2
1
Returns: 176
1
1
2
Returns: 25
4
246
244
Returns: 274521847
5
241
233
Returns: 692632782
1
200
202
Returns: 120592065
3
0
2
Returns: 0
4
128
29
Returns: 826480375
6
0
1
Returns: 0
2
235
139
Returns: 87450873
6
201
116
Returns: 468479916
6
117
240
Returns: 691994676
3
42
118
Returns: 784666214
1
77
13
Returns: 546480898
6
242
231
Returns: 981271743
4
239
244
Returns: 330601200
1
239
233
Returns: 811796350
1
231
118
Returns: 727057849
3
232
77
Returns: 492411483
1
249
242
Returns: 177092881
3
231
241
Returns: 489624414
4
247
241
Returns: 676638886
2
0
2
Returns: 0
1
2
3
Returns: 1450
5
232
245
Returns: 822776580
5
0
3
Returns: 0
5
3
1
Returns: 1275
5
133
195
Returns: 875804878
2
248
245
Returns: 851364663
5
238
239
Returns: 872361750
6
238
238
Returns: 228541640
1
105
106
Returns: 881419851
4
235
249
Returns: 780370392
3
200
180
Returns: 435014743
6
3
2
Returns: 7776
6
139
175
Returns: 397724472
5
239
243
Returns: 138781127
6
245
245
Returns: 848567055
4
153
35
Returns: 151463058
2
249
235
Returns: 170737774
6
18
44
Returns: 92313642
1
248
130
Returns: 598745258
4
230
249
Returns: 136626190
4
231
237
Returns: 406178718
2
210
173
Returns: 423120385
2
3
1
Returns: 816
4
0
1
Returns: 0
5
248
249
Returns: 78278933
3
3
2
Returns: 5778
5
229
187
Returns: 772173647
6
2
3
Returns: 6780
6
1
3
Returns: 750
1
224
159
Returns: 676842199
1
233
246
Returns: 613002070
2
90
203
Returns: 338528239
6
236
250
Returns: 814026446
5
247
235
Returns: 187188108
4
250
70
Returns: 616802367
2
239
236
Returns: 929491965
1
1
1
Returns: 5
6
249
244
Returns: 908930434
2
232
247
Returns: 974609994
2
2
2
Returns: 538
4
17
184
Returns: 890803942
4
31
5
Returns: 836890315
3
0
1
Returns: 0
5
195
69
Returns: 197652347
6
250
250
Returns: 404915918