Statistics

Problem Statement for "NewItemShopTwo"

Problem Statement

Lecette is going to open an item shop. On the first day, she will sell only one magical sword. She will keep the shop open for the whole day, from 00:00 to 23:59.

Since the shop is new, Lecette has only two customers so far, and she has a lot of information about them. The information is given as String[] customers with exactly 2 elements. Each element represents a single customer who may come to the shop at some point during the day. It is formatted as "T1,C1,P1 T2,C2,P2 ... TN,CN,PN" (quotes for clarity), where N is a positive integer. An occurrence of three integers Tj, Cj and Pj within customers[i] means that the following event will happen with a probability of Pj percent: the i-th customer comes to the shop at Tj o'clock and offers to buy a magical sword at a price of Cj units of money. The same customer never comes to the shop more than once. That is, the customer does not come to the shop during the day with a probability of 100 - (P1 + P2 + ... + PN) percent. The values of Tj are such that at most one customer can come to the shop during each hour of the day (see the constraints for further clarification).

When a customer comes to the shop, Lecette can choose to either accept or reject the offer. Let's define S as the amount of money that Lecette will get for the sword (or 0 if she will not sell it). Lecette will act in such a way that maximizes the expected value of S. Return this expected value.

Definition

Class:
NewItemShopTwo
Method:
getMaximum
Parameters:
String[]
Returns:
double
Method signature:
double getMaximum(String[] customers)
(be sure your method is public)

Notes

  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • customers will contain exactly 2 elements.
  • Each element of customers will contain between 5 and 50 characters, inclusive.
  • Each element of customers will be formatted as "T1,C1,P1 T2,C2,P2 ... TN,CN,PN", where Each Tj, Cj and Pj will be nonnegative integers without extra leading zeros.
  • Each Tj will be between 0 and 23, inclusive.
  • Each Cj will be between 1 and 100, inclusive.
  • Each Pj will be between 1 and 100, inclusive.
  • For each t, 0 <= t < 24, there will be at most one pair (i, j) such that the value of Tj in customers[i] is equal to t.
  • In each element of customers, T1 < T2 < ... < TN will hold.
  • In each element of customers, P1 + P2 + ... + PN will not exceed 100.

Examples

  1. { "8,1,80 16,100,11", "12,10,100" }

    Returns: 19.0

    The optimal strategy is as follows: At 08:00, Lecette should not sell the sword even if the first customer comes to the shop. At 12:00, the second customer surely comes. Then, If the first customer has come at 08:00, she should sell the sword to the second customer. Otherwise, she should not sell the sword to the second customer. She should sell it at 16:00 if possible. By this strategy, S will be 10 (80%) or 100 (11%) or 0 (9%).

  2. { "8,1,80 16,100,11", "12,10,90 13,30,5" }

    Returns: 19.4

  3. { "0,90,25 2,90,25 4,90,25 6,90,25", "7,100,80" }

    Returns: 90.0

  4. { "0,90,25 2,90,25 4,90,25 6,90,25", "7,100,95" }

    Returns: 95.0

  5. { "0,3,1 2,4,1 4,5,9 6,2,6 8,5,3 10,5,8 12,9,7 14,9,3", "1,2,3 3,8,4 5,6,2 7,6,4 9,3,3 11,8,3 13,2,7 15,9,5" }

    Returns: 3.0692999999999997

  6. {"9,19,42 18,91,57","6,69,12 12,86,5 13,5,17 14,13,23 15,75,22 22,54,18"}

    Returns: 68.45399999999997

  7. {"0,19,20 1,79,7 2,7,10 3,8,9 7,8,9 9,83,22 16,4,19","5,95,5 6,97,20 8,64,11 10,61,24 14,73,26 19,68,11"}

    Returns: 75.4041

  8. {"0,49,8 2,69,26 4,8,21 5,56,20 7,17,4 11,21,17","1,48,25 3,46,3 6,81,1 8,39,36 10,43,10 16,50,22"}

    Returns: 51.258800000000015

  9. {"2,93,9 9,44,21 18,31,11 20,62,20 22,68,17 23,25,19","0,65,9 1,93,4 4,6,4 6,34,4 7,43,47 16,4,4 19,68,25"}

    Returns: 57.24960000000001

  10. { "21,9,55 22,36,12", "2,20,74 19,36,14" }

    Returns: 20.9524

  11. { "5,7,68 18,21,16", "6,39,51 13,23,32" }

    Returns: 27.8212

  12. { "8,7,68 18,52,9", "10,14,70 19,37,16" }

    Returns: 16.7312

  13. { "2,9,58 6,34,19", "3,52,38 12,14,45" }

    Returns: 28.8682

  14. { "8,9,58 16,33,26", "10,32,31 20,38,27" }

    Returns: 23.4326

  15. { "12,15,34 14,30,44", "4,40,37 23,32,20" }

    Returns: 27.737000000000002

  16. { "4,14,73 15,9,15", "0,22,67 10,33,20" }

    Returns: 21.5155

  17. { "9,21,48 16,8,32", "5,51,39 22,26,36" }

    Returns: 30.906

  18. { "12,14,70 20,29,16", "5,13,37 18,59,21" }

    Returns: 19.681599999999996

  19. { "17,18,56 19,26,25", "12,41,49 15,16,16" }

    Returns: 28.5458

  20. { "17,29,34 21,35,38", "4,15,33 22,38,27" }

    Returns: 26.032799999999998

  21. { "17,30,33 23,37,36", "4,33,45 6,10,28" }

    Returns: 27.621000000000002

  22. { "1,42,36 20,8,39", "5,15,68 15,63,10" }

    Returns: 26.3664

  23. { "1,27,56 19,14,15", "7,77,26 11,20,37" }

    Returns: 28.197000000000003

  24. { "21,54,28 22,38,19", "2,7,67 23,63,11" }

    Returns: 26.012900000000002

  25. { "5,26,57 22,20,21", "12,43,47 15,14,19" }

    Returns: 26.082099999999997

  26. { "3,30,51 4,30,32", "18,16,31 21,29,24" }

    Returns: 26.9264

  27. { "12,43,35 21,58,22", "8,22,46 11,9,32" }

    Returns: 27.81

  28. { "14,40,49 23,10,26", "2,15,67 7,35,14" }

    Returns: 23.992000000000004

  29. { "7,28,72 20,13,11", "3,51,30 21,34,20" }

    Returns: 31.568999999999996

  30. { "11,40,50 12,14,36", "7,19,26 16,25,44" }

    Returns: 26.8104

  31. { "12,30,68 17,15,21", "5,31,48 22,10,25" }

    Returns: 27.401000000000003

  32. { "4,33,60 5,28,21", "14,12,42 20,16,36" }

    Returns: 27.732

  33. { "18,59,34 20,28,36", "12,16,64 13,10,18" }

    Returns: 30.14

  34. { "0,2,9 2,5,3 4,1,6 5,2,8 8,2,6 11,5,1 13,8,4 14,8,5", "1,6,1 3,2,7 6,6,2 7,4,8 9,4,2 12,1,4 17,9,7 18,3,8" }

    Returns: 2.338300000000001

  35. { "1,4,1 2,8,6 4,8,5 5,5,2 6,7,5 11,3,2 12,1,8 18,9,9", "0,1,1 3,4,8 7,9,6 8,9,3 9,4,4 10,2,6 19,9,6 20,6,1" }

    Returns: 3.548000000000001

  36. { "1,8,6 2,2,6 3,5,4 7,3,4 9,9,1 12,2,6 14,2,6 19,9,3", "0,7,1 4,8,3 5,8,4 6,8,7 8,2,2 13,1,5 18,8,9 20,5,6" }

    Returns: 3.1169000000000002

  37. { "3,7,7 5,4,7 6,7,5 7,2,5 8,5,4 10,3,2 15,7,9 18,6,7", "0,5,6 1,1,1 2,3,6 4,4,8 9,3,8 14,3,6 17,5,6 21,3,3" }

    Returns: 3.194200000000001

  38. { "0,7,7 2,5,7 5,5,5 6,3,3 8,7,1 12,5,9 13,2,9 16,2,3", "1,6,9 3,6,5 4,2,2 7,9,6 9,6,7 11,3,8 17,1,3 19,4,1" }

    Returns: 3.3465999999999996

  39. { "0,9,2 1,9,6 2,3,2 3,1,7 9,8,7 12,7,3 21,3,2 23,7,2", "4,4,8 5,1,4 6,8,7 7,8,7 8,5,3 15,8,7 18,7,8" }

    Returns: 3.8073

  40. { "0,9,2 2,6,3 3,3,7 4,9,6 9,1,1 14,8,9 17,2,7 18,8,5", "1,7,5 5,8,3 6,1,5 7,1,5 8,2,4 16,1,6 19,1,3" }

    Returns: 2.8153

  41. { "0,8,6 3,9,4 6,6,8 7,8,1 9,1,7 14,7,7 22,6,1 23,4,2", "1,5,8 2,7,3 4,1,4 5,9,4 8,6,2 15,8,2 16,4,3" }

    Returns: 3.0325999999999995

  42. { "1,4,6 5,8,6 6,3,7 7,2,2 8,8,6 13,4,3 14,7,8", "0,8,4 2,1,4 3,1,1 4,4,4 9,1,8 16,8,8 19,3,9 20,3,8" }

    Returns: 3.156599999999999

  43. { "3,6,8 5,8,8 7,3,6 8,8,5 9,4,2 14,8,5 15,5,4 20,9,7", "0,5,8 1,3,8 2,5,8 4,1,9 6,2,8 17,3,3 22,2,2" }

    Returns: 3.387300000000001

  44. { "2,7,3 4,4,9 9,3,2 15,1,4 16,4,8 18,8,5 23,2,4", "1,2,4 3,6,5 11,2,4 12,9,1 13,1,4 21,9,8 22,8,3" }

    Returns: 2.4834000000000005

  45. { "3,1,3 5,5,1 7,7,6 11,7,4 13,1,6 14,8,9 19,1,8", "8,1,8 10,6,7 15,1,3 16,1,7 20,6,8 22,9,9 23,6,6" }

    Returns: 3.2041999999999997

  46. { "5,52,43 13,40,25", "2,30,61 7,82,7" }

    Returns: 34.9318

  47. { "19,33,63 22,46,8", "0,46,24 4,54,18 5,59,16 6,44,9 21,44,1" }

    Returns: 42.3611

  48. { "2,10,48 4,82,7 13,51,24 14,57,12 16,71,2 19,46,4", "1,70,40 10,92,17 12,32,9 17,58,17 23,47,1" }

    Returns: 62.32770000000001

  49. { "12,75,41", "17,31,62" }

    Returns: 42.0898

  50. { "9,19,49 11,93,8 12,92,23 14,22,9 18,78,7", "4,42,3 17,31,45" }

    Returns: 45.35000000000001

  51. { "0,68,73 1,96,4 9,84,15 15,88,1 19,87,1", "4,1,12 12,73,52 13,76,17 17,12,14 20,97,1" }

    Returns: 70.75110000000001

  52. { "6,88,42 13,62,3 20,36,26", "21,52,59" }

    Returns: 57.077200000000005

  53. { "15,64,52", "3,50,72 6,33,2 20,8,14" }

    Returns: 45.856

  54. { "1,2,4 5,97,46 9,69,36 15,33,9 20,69,1", "0,79,32 8,43,47 12,32,15 17,26,2 19,28,1" }

    Returns: 76.1763

  55. { "19,97,74 21,61,1", "9,83,45 10,73,2 15,22,36 23,63,5" }

    Returns: 77.9642

  56. { "17,40,54 20,76,29", "15,94,49" }

    Returns: 68.3164

  57. { "23,80,72", "8,69,11 17,74,23 21,13,46 22,9,7" }

    Returns: 62.62599999999999

  58. { "7,6,20 22,51,42", "5,51,44 10,93,10 21,73,9" }

    Returns: 46.2354

  59. { "0,57,47 6,50,36 7,51,8 13,56,4 18,82,1 21,38,1", "11,1,68" }

    Returns: 52.31

  60. { "2,4,69 6,18,7 10,89,1 14,41,3 19,31,15 21,75,1", "3,15,57 13,40,11" }

    Returns: 17.998199999999997

  61. { "8,8,1 13,70,39 14,42,44 18,94,6", "3,49,50" }

    Returns: 51.49999999999999

  62. { "6,74,14", "2,28,72 3,79,7 5,37,1" }

    Returns: 28.132

  63. { "1,68,66 14,19,11 19,44,3 23,52,9", "2,97,2 22,71,70" }

    Returns: 63.748000000000005

  64. { "3,86,39 5,81,37 8,89,4 11,97,4 19,92,5", "1,40,49 4,89,33 6,32,10" }

    Returns: 79.6024

  65. { "0,84,16 1,90,24 5,64,34 6,17,15 16,37,3 21,38,4", "2,4,10 19,27,48 20,85,21 22,55,12" }

    Returns: 67.0998

  66. { "0,1,1", "1,1,1" }

    Returns: 0.0199

  67. { "0,100,100", "23,1,1" }

    Returns: 100.0

  68. { "0,1,1", "23,100,100" }

    Returns: 100.0

  69. {"8,1,80 16,100,11", "12,10,90 13,30,5" }

    Returns: 19.4

  70. {"1,1,1", "2,2,2" }

    Returns: 0.049600000000000005

  71. {"0,3,1 2,4,1 4,5,9 6,2,6 8,5,3 10,5,8 12,9,6 14,9,4", "1,2,3 3,8,4 5,6,2 7,6,4 9,3,3 11,8,3 13,2,7 15,9,5" }

    Returns: 3.064400000000001

  72. {"0,3,1 2,4,1 4,5,9 6,2,6 8,5,3 10,5,8 12,9,7 14,9,3", "1,2,3 3,8,4 5,6,2 7,6,4 9,3,3 11,8,3 13,2,7 15,9,5" }

    Returns: 3.0692999999999997

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: