Statistics

Problem Statement for "VendingMachines"

Problem Statement

This problem has a non-standard time limit: 6 seconds. This problem also has a non-standard precision limit: 1e-4.

Yesterday, Cat Noku has spent a long day at the arcade. You are given the int tickets: the number of tickets he won by playing the games. This morning he is the first customer to enter the arcade. He now wants to exchange his tickets for prizes.

There are multiple vending machines at the arcade. All vending machines have just been reset into their initial state. The vending machines are probabilistic. Each vending machine has two parameters: its luck factor L and its value V. A vending machine with luck factor L and value V operates as follows:

  1. A person inserts exactly one ticket into the machine.
  2. The machine computes K: the number of tickets inserted into the machine since it last gave out a prize. (This includes the ticket inserted in the previous step. If the machine didn't give out any prizes yet, K is simply the total number of tickets inserted into the machine today.)
  3. With probability min(K^2,L^2)/L^2, the machine gives out a prize with value V. Otherwise, the machine does nothing.

You are given the description of the vending machines: int[]s luck and value. For each valid i, there is a vending machine with luck factor luck[i] and prize value value[i]. Each machine can be used arbitrarily many times and contains a sufficient supply of prizes (each of the same value).

Cat Noku is very stubborn. Whenever he chooses a vending machine, he keeps on inserting tickets into the machine until he either wins a prize or runs out of tickets. Additionally, Noku likes variety: whenever he gets a prize from a vending machine, he goes to a different machine. In other words, Noku will never claim two consecutive prizes from the same machine.

Given the above constraint, Cat Noku wants to maximize the sum of values of prizes he gets. More precisely, he is interested in the strategy that maximizes the expected value of that sum. Find that strategy and return that expected value.

Definition

Class:
VendingMachines
Method:
expectedValue
Parameters:
int, int[], int[]
Returns:
double
Method signature:
double expectedValue(int tickets, int[] luck, int[] value)
(be sure your method is public)

Notes

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

Constraints

  • tickets will be between 1 and 40,000, inclusive.
  • n will be between 2 and 15, inclusive.
  • luck,value will have exactly n elements.
  • Each element of luck will be between 1 and 1,000,000,000, inclusive.
  • Each element of value will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 2

    {1,1}

    {2,3}

    Returns: 5.0

    Cat Noku has 2 tickets. There are two vending machines. Each of them has luck factor 1, which means that the machine always gives out a prize. Since Noku doesn't want to claim two consecutive prizes from the same machine, he will use each machine exactly once. Thus, he is guaranteed to get a prize worth 2 and a prize worth 3, which means that the answer is 2+3 = 5.

  2. 3

    {1,1,1}

    {2,3,4}

    Returns: 11.0

    Cat Noku can use a particular machine multiple times, he just has to switch machines each time he gets a prize. Here, the optimal strategy is to use machine 2 (0-based index), then machine 1, and then machine 2 again. This leaves Noku with prizes worth 4+3+4 = 11.

  3. 100

    {1, 1, 1}

    {100,100,100}

    Returns: 9999.99999999991

  4. 4

    {2,3}

    {4,5}

    Returns: 7.693072702331962

    In this case, Noku has 4 tickets and there are two machines. Machine 0 has luck factor 2 and gives out prizes with value 4. Machine 1 has luck factor 3 and gives out prizes with value 5. One example of how Cat Noku can spend his tickets: Cat Noku chooses to put his first ticket into machine 0. This machine computes that K=1. This means that Noku will get the prize with probability (1^2)/(2^2) = 1/4 = 0.25. Suppose he is unlucky and doesn't get the prize. Due to his stubbornness, Noku must continue by putting his second ticket into machine 0. The machine now computes that K=2, which means that Noku is guaranteed to get the prize with value 4. Now, Noku must switch machines. He therefore moves to machine 1. Noku puts the next ticket (his third one) into machine 1. This machine computes that K=1. This means that Noku will only get its prize with probability 1/9. Suppose this time he's lucky and gets the prize (with value 5). Noku switches machines again, returning back to machine 0. Noku puts his last ticket into machine 0. This is the first ticket that was put into this machine since it last gave out a prize. Hence, we are now back to having K=1, and therefore the probability of getting the next prize is 1/4. Suppose he does not win this prize. In this scenario, Noku's total value of prizes is 4 + 5 = 9.

  5. 11

    {2,3,4}

    {55,58,60}

    Returns: 292.20826703848974

  6. 1001

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    {1, 4, 9, 29, 35, 40, 49, 55, 63, 72}

    Returns: 12321.244694733025

  7. 40000

    {1000000000, 1}

    {1000000000, 1}

    Returns: 21333.928554321847

  8. 40000

    {495,350,340,180,113,552,584,719,601,77,498,920,573,476,591}

    {240,120,113,31,12,299,335,508,355,5,243,832,322,222,343}

    Returns: 238428.2509387636

  9. 40000

    {54,764,48,254,211,816,993,391,380,147,387,457,328,554,562}

    {2,415,1,45,31,473,701,108,102,15,106,148,76,218,224}

    Returns: 195421.85876699974

  10. 40000

    {62754,84014,99910,43087,47092,91025,10154,66192,33067,21153,66383,66094,7669,87596,56721}

    {6196,11107,15707,2921,3489,13038,162,6894,1720,704,6934,6874,92,12074,5062}

    Returns: 207966.2311339482

  11. 40000

    {70478,47301,89284,79004,98356,89772,98773,87354,80040,78480,2093,88663,25767,81374,46067}

    {21348,9615,34261,26825,41577,34636,41930,32795,27533,26471,18,33786,2853,28459,9120}

    Returns: 589761.5506553064

  12. 40000

    {215644,566956,11091,162507,676040,973663,455773,320691,357867,454933,978574,529735,542516,152200,706329}

    {14300,98848,37,8121,140544,291532,63880,31625,39383,63645,294481,86295,90509,7123,153420}

    Returns: 797956.2234492035

  13. 40000

    {376457,844650,683343,503685,652230,960872,93732,307157,900080,485114,635760,758792,930176,653211,356520}

    {61172,307947,201558,109506,183621,398523,3792,40723,349691,101580,174465,248524,373468,184174,54864}

    Returns: 1080454.2721870663

  14. 40000

    {633847899,294272810,133428071,533902159,934514173,605899628,242847442,635144819,198522691,227457897,837479258,981470929,789374245,178451267,685985415}

    {272930381,58827723,12094173,193644482,593271597,249392359,40063495,274048413,26773310,35146639,476463779,654389998,423299424,21633213,319677107}

    Returns: 14492.805006482717

  15. 40000

    {35162966,664736792,405609264,359428521,414482522,455734417,163190395,591133867,330082590,616545699,208512778,920199631,134490889,728190270,242580563}

    {311641,111373955,41466744,32561865,43300873,52348936,6712331,88075657,27461828,95810864,10958460,213426489,4559003,133651536,14831880}

    Returns: 5377.176500311884

  16. 1

    {1000000000, 3}

    {1000000000, 4}

    Returns: 0.44444444444444436

  17. 40000

    {10000, 35000, 30000, 40000, 30000, 20000, 20000, 30000, 20000, 40000, 20000, 10000, 1000000, 2000, 10000 }

    {11231412, 123234, 23423, 342324, 234234, 234234, 234234, 234234, 324234, 234234, 234234, 234234, 123123, 4353463, 324123324 }

    Returns: 1.6322359795325588E10

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: