Connection Status:
Competition Arena > NewItemShopTwo

NewItemShopTwo

SRM 515 · 2011-05-25 · by lyrically

SRM 515 · 2011-05-25 · by lyrically · Search, Simple Math
Class Name: NewItemShopTwo
Return Type: double
Method Name: getMaximum
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{ "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%).

1)
{ "8,1,80 16,100,11", "12,10,90 13,30,5" }
Returns: 19.4
2)
{ "0,90,25 2,90,25 4,90,25 6,90,25", "7,100,80" }
Returns: 90.0
3)
{ "0,90,25 2,90,25 4,90,25 6,90,25", "7,100,95" }
Returns: 95.0
4)
{ "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

Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NewItemShopTwo with a public method double getMaximum(vector<string> customers) · 72 test cases · 2 s / 256 MB per case

Submitting as anonymous