Problem C
Selling Spatulas

Photo by Evan-Amos

You have finally realized your life-long dream: you opened your own chain of retail stores specializing in hard-to-find spatulas. Being your own boss is great – but you have to make all the decisions, like when your stores should be open. Being somewhat methodical, you decided to spend the first several days with the stores open all day and all night to see when the most profitable times are at each store. As a result, you have a lot of data on when people like to buy spatulas. In fact, you have recorded each sale and its timestamp. Now you have to analyze the data.

A store should be open when it is most profitable, so you want to write a program that determines the single period that is most profitable for each store individually. There is a constant cost of $0.08 per minute to keep each store running while it is open, and you assume there are no costs associated with keeping a store closed.


Input consists of several (up to $150$) stores’ sales records. Each record starts with a line containing an integer $1 \le n \le 1\, 000$. The next $n$ lines each contain a sale from that store. Each sale has the number of minutes after opening (in the range $0$ to $1\, 439$) and the profit (a real number in the range $[-100,100]$ with two digits after the decimal). The profit can be negative because sometimes you have loss-leader sales where your store actually loses money. Transactions are ordered by time, and there are never two sales in the same minute. Input ends when $n=0$.


For each store, print the maximum profit (as a real number with two digits past the decimal point), followed by the beginning and ending minutes when the profit is realized. If two different periods both have the maximum profit, then choose the shortest one, and if there are still ties, choose the period that starts earliest. If the store never can turn a profit, print no profit. Stores must open and close on minute boundaries.

Sample Input 1 Sample Output 1
15 0.37
36 3.51
65 3.72
72 1.89
120 0.20
28 0.38
140 4.90
313 2.77
400 4.32
446 2.54
485 1.97
1 0.08
2 0.03
6.16 36 72
4.82 140 140
no profit

Please log in to submit a solution to this problem

Log in