Statistics

Problem Statement for "PBG"

Problem Statement

PBG is a shooter game for bears. The next round of this game will involve P polar bears (including Limak), B brown bears and G grizzly bears. We will use N to denote the total number of bears, that is, N = P + B + G.

The PBG game is played in rounds. In each round, a pair of bears is chosen uniformly at random. The two chosen bears fight each other. The loser of the fight is eliminated from the game, the winner remains.

The three bear species can be ordered by strength. Grizzly bears are the strongest, polar bears are in the middle, and brown bears are the weakest. A bear from a stronger species will always beat a bear of a weaker species in a fight. Whenever two bears of the same species fight, each of them has a 50 percent chance to win the fight.

The game ends when there is only one bear left. After the game, each bear is assigned a place: the winner's place is 1 and the other bears are on places 2 to N in reversed elimination order. (That is, the bear that lost the very last fight is in place 2, and the bear that got eliminated first is in place N.)

Limak is one of the polar bears in the game. Find the expected value of his place in the game. Express this value as a reduced fraction X/Y. Return the value X*Y^(-1) modulo 1000000007.

Definition

Class:
PBG
Method:
findEV
Parameters:
int, int, int
Returns:
int
Method signature:
int findEV(int P, int B, int G)
(be sure your method is public)

Notes

  • Given the constraints used in this problem, if Limak's expected place is a reduced fraction is X/Y, the number Y will never be divisible by (10^9 + 7) = 1,000,000,007.
  • The notation Y^(-1) represents the inverse element to Y modulo 10^9 + 7. The previous note implies that this value always exists.

Constraints

  • P will be between 1 and 2000, inclusive.
  • B will be between 0 and 2000, inclusive.
  • G will be between 0 and 2000, inclusive.

Examples

  1. 5

    0

    0

    Returns: 3

    There are five polar bears and each of them is equally likely to take any place from 1 to 5. The expected value of Limak's place is (1+2+3+4+5)/5 = 3.

  2. 1

    1

    1

    Returns: 333333338

    There is one bear of each species. There are three possibilities: In the first round Limak (a polar bear) meets a brown bear. Since polar bears are a stronger species, Limak wins. In the second round he will then lose to the grizzly bear. Limak's place: 2. In the first round Limak meets the grizzly bear and loses. Limak's place: 3. In the first round the other two bears fight. The grizzly wins. In the second round the grizzly defeats Limak as well. Limak's place: 2. Each of the three scenarios is equally likely, so the answer is (2 + 3 + 2) / 3 = 7 / 3. The correct return value is therefore (7 * 3^(-1)) mod (10^9 + 7) = (7 * 333,333,336) mod (10^9 + 7) = 333,333,338.

  3. 1

    3

    0

    Returns: 1

    There is one polar bear (Limak) and three brown bears. Limak is the strongest of the four bears, so he will always get first place.

  4. 2

    3

    4

    Returns: 672193888

  5. 1

    0

    3

    Returns: 333333339

  6. 1

    0

    0

    Returns: 1

  7. 2000

    2000

    2000

    Returns: 246923693

  8. 1

    0

    0

    Returns: 1

  9. 1

    0

    1

    Returns: 2

  10. 1

    1

    0

    Returns: 1

  11. 1

    1

    1

    Returns: 333333338

  12. 2

    0

    0

    Returns: 500000005

  13. 2

    0

    1

    Returns: 500000006

  14. 2

    1

    0

    Returns: 666666673

  15. 2

    1

    1

    Returns: 833333342

  16. 2

    3

    1

    Returns: 945000010

  17. 2

    2

    5

    Returns: 568452391

  18. 3

    0

    5

    Returns: 971428584

  19. 4

    3

    0

    Returns: 260000005

  20. 9

    6

    2

    Returns: 391916956

  21. 8

    2

    3

    Returns: 902631442

  22. 8

    10

    6

    Returns: 592476738

  23. 5

    5

    0

    Returns: 906651560

  24. 5

    1

    7

    Returns: 816136378

  25. 11

    1

    1

    Returns: 333333343

  26. 1

    17

    19

    Returns: 221220387

  27. 56

    20

    32

    Returns: 323654840

  28. 28

    7

    2

    Returns: 854100311

  29. 39

    94

    35

    Returns: 263758373

  30. 179

    416

    199

    Returns: 65041808

  31. 68

    321

    261

    Returns: 33090732

  32. 440

    7

    433

    Returns: 303920351

  33. 1449

    1026

    753

    Returns: 630620618

  34. 1355

    896

    1085

    Returns: 810771595

  35. 580

    1980

    1631

    Returns: 567693850

  36. 1

    2000

    0

    Returns: 1

  37. 1

    0

    2000

    Returns: 666668006

  38. 1

    2000

    2000

    Returns: 577100435

  39. 2000

    0

    0

    Returns: 500001004

  40. 2000

    2000

    0

    Returns: 763051726

  41. 2000

    0

    2000

    Returns: 236952282

  42. 2000

    2000

    2000

    Returns: 246923693

  43. 1970

    1974

    1970

    Returns: 86044590

  44. 1977

    1958

    1979

    Returns: 714064297

  45. 1982

    1987

    1978

    Returns: 710469079

  46. 1996

    1984

    1979

    Returns: 271920889

  47. 1951

    1992

    1983

    Returns: 882397518

  48. 1877

    2000

    1412

    Returns: 101740193

  49. 17

    1977

    1761

    Returns: 140597095

  50. 2000

    39

    1999

    Returns: 674942010

  51. 1999

    1998

    3

    Returns: 763322305

  52. 1998

    2000

    1999

    Returns: 18742738

  53. 2000

    2000

    1999

    Returns: 345358891

  54. 1999

    2000

    1998

    Returns: 456420402

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: