## TLE '16 Contest 5 P5 - Better Ranking List

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Java 1.5s
Python 2.0s
Memory limit: 128M
Java 256M
Python 256M

Author:
Problem types
The users with the highest PP on the DMOJ.

The DMOJ is a source of countless debates on how to accurately rank users from best to worst. One measurement, called PP, catches the attention of Nathan.

The problems on the DMOJ are numbered from to . When a user submits to a problem, the user will be given a point value (a real number between and inclusive), but only the highest point value reached for that problem will be considered in the rankings. A user will get points from a problem with submissions.

To measure the PP of a user, the first step is to get all of the user's points as a list. Then, this list is sorted in non-increasing order. For simplicity, this sequence will be labelled from to .

The actual calculations can now begin, with the result starting at , and as a given ratio. In the step, the result increases by (it is known that ). In the step, the result increases by . In general, the result increases by . This continues until the list is exhausted, and the final result is the user's PP.

In other words, a user's PP is equal to .

Although it is nice to sort everyone by PP, Nathan does not want to stop there. He wants to plot a user's PP against the date. Since Nathan's code somehow crashes on a user with submissions, can you calculate the information for him?

#### Constraints

1 5
2 10
Also, . In other words, the user will only make submissions to problems in the range .
3 10
4 20
5 30

#### Input Specification

The first line contains a real number , a ratio given to 6 decimal places.

The second line contains , the number of submissions that a user made.

lines of input follow. The line contains an integer, , followed by a real number given to three decimal places, . This signifies that on the submission, the user submitted to problem number and received a point value of .

#### Output Specification

The output will consist of lines. On the line, output the user's PP directly after their submission.

Your answer will be judged as correct if the absolute or relative error does not exceed .

#### Sample Input 1

0.500000
5
2 4.000
1 6.000
2 10.000
3 2.000
3 0.000

#### Sample Output 1

4.000000000
8.000000000
13.000000000
13.500000000
13.500000000

#### Explanation for Sample Output 1

After the submission, and the remaining terms are . Therefore, the user's PP is .

After the submission, , , and the remaining terms are . Therefore, the user's PP is .

After the submission, problem gets bumped from to . As a result, , , and the remaining terms are . Therefore, the user's PP is .

After the submission, the user's PP is .

The submission does not change the sequence , therefore the user's PP stays the same.

#### Sample Input 2

0.010000
8
1 1.000
2 2.000
3 3.000
4 4.000
5 5.000
6 6.000
3 2.000
3 5.000

#### Sample Output 2

1.000000000
2.010000000
3.020100000
4.030201000
5.040302010
6.050403020
6.050403020
6.050504020