CCC '05 S5 - Pinball Ranking - DMOJ: Modern Online Judge

CCC '05 S5 - Pinball Ranking

Points: 12 (partial)

Time limit: 0.2s

Java 0.3s

Memory limit: 256M

Problem types

Canadian Computing Competition: 2005 Stage 1, Senior #5

Pinball is an arcade game in which an individual player controls a silver ball by means of flippers, with the objective of accumulating as many points as possible. At the end of each game, the player's score and rank are displayed. The score, an integer between $0$ ~0~ and $1\,000\,000\,000$ ~1\,000\,000\,000~, is that achieved by the player in the game just ended. The rank is displayed as " $r$ ~r~ of $n$ ~n~". $n$ ~n~ is the total number of games ever played on the machine, and $r$ ~r~ is the position of the score for the just-ended game within this set.

More precisely, $r$ ~r~ is one greater than the number of games whose score exceeds that of the game just ended.

Input Specification

You are to implement the pinball machine's ranking algorithm. The first line of input contains a positive integer, $t$ ~t~, the total number of games played in the lifetime of the machine. $t$ ~t~ lines follow, given the scores of these games, in chronological order.

Output Specification

You are to output the average of the ranks up to an absolute error of $10^{-2}$ ~10^{-2}~ that would be displayed on the board.

At least one test case will have $t \le 100$ ~t \le 100~. All test cases will have $t \le 100\,000$ ~t \le 100\,000~.

Sample Input

Sample Output

2.20

Explanation for Sample Output

The pinball screen would display (in turn):

1 of 1
1 of 2
2 of 3
2 of 4
5 of 5

The average rank is $(1+1+2+2+5)/5 = 2.20$ ~(1+1+2+2+5)/5 = 2.20~.

Comments

3

maxcruickshanks commented on April 21, 2022, 1:47 a.m.

Since the data were not language friendly, the specificity for the answer has been updated (refer to the problem statement), and all submissions were rejudged.

2

Lemonsity commented on Dec. 2, 2018, 9:16 p.m.

Can we assume no two input are the same?

If they are the same, what should I output?

4

Relativity commented on Dec. 3, 2018, 11:58 p.m.

Inputs are not necessarily distinct

-7

septence123 commented on Jan. 6, 2017, 4:48 a.m.

I implemented BST and still got TLE? Is there something faster?

This comment is hidden due to too much negative feedback. Show it anyway.

-5

ZQFMGB12 commented on Jan. 6, 2017, 5:25 a.m.

Read this for more info.

This comment is hidden due to too much negative feedback. Show it anyway.

-7

MathBunny123 commented on Jan. 30, 2016, 3:11 a.m. ← edited →

According to DMOJ my code is too slow, but I run the test-files from CCC's website and it finishes all of them instantly. Is my approach wrong? I feel like the 0.3sec time limit is too close to my solution or something.

This comment is hidden due to too much negative feedback. Show it anyway.

-2

jeffreyxiao commented on Jan. 30, 2016, 4:03 a.m. ← edited →

Your solution is $\mathcal O(N^2 \log N)$ ~\mathcal O(N^2 \log N)~ because insertion into an ArrayList at an arbitrary position takes $\mathcal O(N)$ ~\mathcal O(N)~ time.

-3

MathBunny commented on Jan. 30, 2016, 5:10 p.m.

Really? Okay thanks a lot!

-25

bobhob314 commented on Jan. 24, 2015, 2:20 p.m.

Will the scores be repeated?

This comment is hidden due to too much negative feedback. Show it anyway.

-20

Sentient commented on Jan. 24, 2015, 4:00 p.m.

Yes, scores can be repeated; they are not guaranteed to be distinct

This comment is hidden due to too much negative feedback. Show it anyway.

-18

lolzballs commented on March 19, 2015, 3:53 p.m.

When they are repeated, is the rank the same, lower or higher?

This comment is hidden due to too much negative feedback. Show it anyway.

-15

quantum commented on March 19, 2015, 4:04 p.m.

Look at the italicized line.

This comment is hidden due to too much negative feedback. Show it anyway.

-18

FatalEagle commented on March 19, 2015, 3:59 p.m.

More precisely, $r$ ~r~ is one greater than the number of games whose score exceeds that of the game just ended.

This comment is hidden due to too much negative feedback. Show it anyway.