CCC '05 S5 - Pinball Ranking

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 128M

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 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.

Input Specification

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.

Output Specification

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 \le 100. All test cases will have t \le 100\,000.

Sample Input

5
100
200
150
170
50

Sample Output

2.20

Explanation

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.


Comments


  • 0
    Lemonsity  commented on Dec. 2, 2018, 4:16 p.m.

    Can we assume no two input are the same?

    If they are the same, what should I output?


    • 0
      icyblue87  commented on Dec. 3, 2018, 6:58 p.m.

      Inputs are not necessarily distinct


  • -1
    Xue_Alex  commented on July 29, 2017, 9:22 p.m.

    tfw changing all floats to doubles AC's


  • -2
    Pleedoh  commented on May 15, 2017, 5:14 p.m.

    Round to 2 decimal places?


    • 0
      mse387  commented on May 15, 2017, 5:38 p.m.

      Output Specification

      "...output the average of the ranks (rounded to two digits after the decimal) that...."


      • -1
        Pleedoh  commented on May 15, 2017, 6:41 p.m.

        Right,sorry.


  • -3
    septence123  commented on Jan. 5, 2017, 11:48 p.m.
    Still getting TLE?

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


    • -1
      ZQFMGB12  commented on Jan. 6, 2017, 12:25 a.m.

      Read this for more info.


  • -10
    Kirito  commented on July 31, 2016, 8:18 p.m. edit 3
    NVM

    Saw the site update popup.


    • -10
      Xyene  commented on July 31, 2016, 8:19 p.m.

      Yes.


  • -6
    MathBunny123  commented on Jan. 29, 2016, 10:11 p.m.
    Too slow? Help?

    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 1sec time limit is too close to my solution or something.


    • -5
      jeffreyxiao  commented on Jan. 29, 2016, 11:03 p.m.

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


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

        Really? Okay thanks a lot!


  • -17
    bobhob314  commented on Jan. 24, 2015, 9:20 a.m.
    Score

    Will the scores be repeated?


    • -17
      Sentient  commented on Jan. 24, 2015, 11:00 a.m.

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


      • -15
        lolzballs  commented on March 19, 2015, 11:53 a.m.

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


        • -16
          quantum  commented on March 19, 2015, 12:04 p.m.

          Look at the italicized line.


        • -15
          FatalEagle  commented on March 19, 2015, 11:59 a.m.

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


  • -11
    quantum  commented on Dec. 1, 2014, 2:11 p.m.
    Partial Points

    This problem now have partial points enabled. The test cases have been re-weighted to give reasonable points for different algorithms to solve this problem. All non-AC submissions have been rejudged.


  • -10
    BMP  commented on Nov. 28, 2014, 5:01 p.m.
    moar time limit

    plz


    • -9
      FatalEagle  commented on Nov. 28, 2014, 6:05 p.m.

      Your program isn't going to pass within a resasonable amount of time. Brute force like you are doing will not pass every problem on the judge. The best solution so far uses 0.057s in the worst case.