2005 Canadian Computing Competition, Stage 1
Problem S5: Pinball Ranking
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 and 1 000 000 000, is that achieved by the player in the game just ended. The rank is displayed as "r of n". n is the total number of games ever played on the machine, and r is the position of the score for the just-ended game within this set.
More precisely, r is one greater than the number of games whose score exceeds that of the game just ended.
You are to implement the pinball machine's ranking algorithm. The first line of input contains a positive integer, t, the total number of games played in the lifetime of the machine. t lines follow, given the scores of these games, in chronological order.
You are to output the average of the ranks (rounded to two digits after the decimal) that would be displayed on the board.
At least one test case will have t ≤ 100. All test cases will have t ≤ 100 000.
5 100 200 150 170 50
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.
Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 128M
Added: Sep 28, 2008
- Data Structures
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Edit: I guess I'll just use a BIT. Thanks Brian!
One of the cases has an answer which evaluates to *exactly* ?.?45. This should be rounded DOWN to ?.?4, not up to ?.?5.
However, all the other solutions use some sort of insertion sort.
However, you have to be extremely clever with mergesort - this solution only sorts once (instead of t times), the entire list of scores. If you sort t times, as you normally would, you'll still TLE.
Test Case #10: Hardware failure [1.468s, 600K] (0/10)