Statistics

Problem Statement for "BearEmptyCoin"

Problem Statement

Bear Limak has a fair coin. (Whenever he tosses the coin, it will land on each side with probability 50%.) Initially, both sides of the coin are empty.


Limak is going to play a game. At the beginning of the game, Limak's score is 0. The game will consist of K turns. Each turn will look as follows:

  1. Limak tosses the coin.
  2. If the visible side of the coin is empty, Limak chooses an arbitrary (possibly negative or extremely big) integer and writes it on that side of his coin.
  3. Limak adds the integer written on the visible side of the coin to his score.

Limak will win the game if his final score (after all K turns) is exactly S. Limak is smart and always follows a strategy that maximizes the probability of winning the game.


You are given the ints K and S. Let P be the probability that Limak wins the game. It can be shown that P multiplied by 2^K is an integer. Compute and return that integer.

Definition

Class:
BearEmptyCoin
Method:
winProbability
Parameters:
int, int
Returns:
long
Method signature:
long winProbability(int K, int S)
(be sure your method is public)

Constraints

  • K will be between 1 and 60, inclusive.
  • S will be between -1,000,000,000 and 1,000,000,000, inclusive.

Examples

  1. 1

    17

    Returns: 2

    After tossing a coin, Limak should write 17 on the visible side. His final score will be 17. The probability of winning is 1. You should return 1 * 2K = 2.

  2. 2

    -50

    Returns: 4

    An optimal strategy looks as follows: Toss the coin for the first time. Write -25 on the visible side. Add the number -25 to your score. Your score is now -25. Toss the coin for the second time. There are now two possibilities: either the visible side is empty, or it contains the -25 we wrote on the coin in the first round. If the visible side is empty, write -25 on that side as well. In either case, add -25 to your score. Your score is now -50. When following this strategy you are guaranteed to win the game. Again, you should return 1 * 2K.

  3. 2

    -49

    Returns: 2

    In this case you cannot guarantee to win the game. The best strategy will give you a 50% probability of winning. The return value should be 0.5 * 2K = 2. One optimal strategy looks as follows: After the first coin toss, write 80,000,000,000 (i.e. 8 * 1010) on the visible side. Then, there are two possibilities for the second coin toss. If you see 80,000,000,000 again, your final score is 160,000,000,000 and you lose. If you see the other (still empty) side of the coin, you can write -80,000,000,049 and win the game beucase your final score is -49. Obviously, there are other optimal strategies as well: you can write any integer x after the first coin toss, and then hope to see the other side on the coin and write (-49-x) there.

  4. 4

    42

    Returns: 8

  5. 4

    -123456789

    Returns: 6

  6. 18

    123456

    Returns: 49870

  7. 60

    0

    Returns: 1152921504606846976

  8. 20

    -2845018

    Returns: 187942

  9. 40

    1

    Returns: 138834194756

  10. 45

    7

    Returns: 4245049529812

  11. 46

    -4

    Returns: 8300338116572

  12. 48

    1

    Returns: 32333691386100

  13. 48

    2

    Returns: 32467381649194

  14. 48

    3

    Returns: 32444728845612

  15. 48

    4

    Returns: 32484044416434

  16. 48

    536870912

    Returns: 32484083199532

  17. 48

    -12

    Returns: 32497456808804

  18. 50

    0

    Returns: 1125899906842624

  19. 55

    1331

    Returns: 3941269902101972

  20. 55

    -10240

    Returns: 3943804317714000

  21. 56

    1

    Returns: 7688091247051004

  22. 56

    14

    Returns: 7697975326484038

  23. 57

    584141

    Returns: 15448986573412072

  24. 57

    29317

    Returns: 15448988483966872

  25. 57

    3

    Returns: 15486421747060896

  26. 57

    -9

    Returns: 15486421747060896

  27. 57

    57

    Returns: 144115188075855872

  28. 58

    2149567

    Returns: 30634274042643224

  29. 58

    -1974706

    Returns: 30256308000358456

  30. 58

    -13805936

    Returns: 30256308000358456

  31. 58

    438190

    Returns: 288230376151711744

  32. 59

    990182101

    Returns: 60851070403400216

  33. 60

    950123071

    Returns: 118346099267169764

  34. 60

    25279

    Returns: 118346099267169764

  35. 60

    36902

    Returns: 118660374228977932

  36. 60

    2700003

    Returns: 118809561469934696

  37. 60

    680246

    Returns: 118660374228977932

  38. 60

    -122400444

    Returns: 118978535620999900

  39. 60

    73264952

    Returns: 118938508471432060

  40. 60

    -13451264

    Returns: 118938508471432060

  41. 60

    892020

    Returns: 1152921504606846976

  42. 60

    32271040

    Returns: 118943684750808136

  43. 1

    0

    Returns: 2

  44. 1

    -1

    Returns: 2

  45. 1

    1000000000

    Returns: 2

  46. 1

    36419354

    Returns: 2

  47. 1

    -15694274

    Returns: 2

  48. 58

    0

    Returns: 288230376151711744

  49. 58

    1

    Returns: 28102293705839768

  50. 58

    -1000000000

    Returns: 30256308000358456

  51. 58

    67002942

    Returns: 30256308000358456

  52. 58

    -647250060

    Returns: 30256308000358456

  53. 59

    0

    Returns: 576460752303423488

  54. 59

    -1

    Returns: 60851070403400216

  55. 59

    1000000000

    Returns: 60851070403400216

  56. 59

    934128330

    Returns: 60851070403400216

  57. 59

    -778734568

    Returns: 60851070403400216

  58. 60

    0

    Returns: 1152921504606846976

  59. 60

    1

    Returns: 118346099267169764

  60. 60

    -1000000000

    Returns: 118943684750808136

  61. 60

    718731665

    Returns: 118516609160695776

  62. 60

    -134586090

    Returns: 120845846627388478

  63. 60

    545465338

    Returns: 118660374228977932

  64. 60

    -44536346

    Returns: 118660374228977932

  65. 60

    1

    Returns: 118346099267169764

  66. 60

    2

    Returns: 118660374228977932

  67. 60

    3

    Returns: 118809561469934696

  68. 60

    17

    Returns: 118346099267169764

  69. 60

    15

    Returns: 118831589107963608

  70. 60

    -1

    Returns: 118346099267169764

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: