CCC '05 S5 - Pinball Ranking

View as PDF

Points: 15 (partial)
Time limit: 0.2s
Java 0.5s
Python 0.5s
Memory limit: 128M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 and , is that achieved by the player in the game just ended. The rank is displayed as " of ". is the total number of games ever played on the machine, and is the position of the score for the just-ended game within this set.

More precisely, 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, , the total number of games played in the lifetime of the machine. 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 . All test cases will have .

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 .

• commented on May 19, 2020, 8:36 p.m. edit 4

If you find that you're WA on only test case 4, it's likely an issue with your rounding.

The test data was generated with an implementation of round which rounds towards even, thus round(4.5) -> 4, but round(5.5) -> 6.

Change your round function accordingly. In C/C++, you can just use rint() instead of std::round().

In case you wanted to see what life was like before C++11: http://man7.org/linux/man-pages/man3/lrint.3.html

• commented on May 7, 2020, 6:55 p.m. edit 2

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on May 19, 2020, 9:03 p.m. edit 2

You're correct -- the test data is actually incorrect with respect to the problem statement: but it's not supposed to be truncation either.

Before C++11 introduced std::round(), people had to implement their own round functions, or use rint/lrint, which reads your system state for the "rounding mode". The default rounding mode for IEEE 754 floating point operations is Banker's Rounding, which rounds halfway numbers to even integers. I believe this is the rounding used to generate the test case, which rounded 24794.5 to 24794.

Note that this is not the behavior of std::round.

EDIT: Looking at many of the other user submissions, many people are just using printf("%.2f", ans);. This just rounds the answer to two decimal places using rint as the backend I think.

• commented on Feb. 19, 2020, 12:22 a.m.

Is this problem order statistic tree?

• commented on Feb. 19, 2020, 9:54 a.m.

• commented on June 28, 2020, 1:59 p.m.

Mind telling me how to join??

• commented on June 28, 2020, 4:59 p.m.
• 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?

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

Inputs are not necessarily distinct

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

tfw changing all floats to doubles AC's

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

Round to 2 decimal places?

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

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

Right,sorry.

• commented on Jan. 5, 2017, 11:48 p.m.

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

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

• commented on Jan. 29, 2016, 10:11 p.m.

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.

• 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

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

Really? Okay thanks a lot!

• commented on Jan. 24, 2015, 9:20 a.m.

This comment is hidden due to too much negative feedback. Click here to view it.

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

This comment is hidden due to too much negative feedback. Click here to view it.

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

This comment is hidden due to too much negative feedback. Click here to view it.

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

This comment is hidden due to too much negative feedback. Click here to view it.

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

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Dec. 1, 2014, 2:11 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Nov. 28, 2014, 5:01 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

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

This comment is hidden due to too much negative feedback. Click here to view it.