Canadian Computing Competition: 2020 Stage 1, Senior #1
Trick E. Dingo is trying, as usual, to catch his nemesis the Street Sprinter. His past attempts using magnets, traps and explosives have failed miserably, so he's catching his breath to gather observational data and learn more about how fast Street Sprinter is.
Trick E. Dingo and Street Sprinter both inhabit a single straight west-east road with a particularly famous rock on it known affectionately as The Origin. Positions on this straight road are measured numerically according to the distance from The Origin, using negative numbers for positions west of The Origin and positive numbers for positions east of The Origin.
The observations by Trick E. Dingo each contain two numbers: a time, and the value of Street Sprinter's position on the road at that time. Given this information, what speed must Street Sprinter be capable of?
Input Specification
The first line contains a number , the number of observations that follow. The next
lines each contain an integer
indicating the time, in seconds, of when a measurement was made, and an integer
indicating the position, in metres, of the Street Sprinter at that time. No two lines will have the same value of
.
For of the
available marks,
.
Output Specification
Output a single number , such that we can conclude that Street Sprinter's speed was at least
metres/second at some point in time, and such that
is as large as possible. If the correct answer is
, the grader will view
as correct if
.
Sample Input 1
3
0 100
20 50
10 120
Output for Sample Input 1
7.0
Explanation of Output for Sample Input 1
Since the Street Sprinter ran from position to position
between time
and time
, we know its speed must have been at least
at some point in time: if it was always less than
, then the distance of
could not be covered in
seconds. Likewise, the speed must have been at least
in order to travel between position
and
in
seconds.
Sample Input 2
5
20 -5
0 -17
10 31
5 -3
30 11
Output for Sample Input 2
6.8
Comments
The checker has been updated to heed the constraints described in the problem.
This comment is hidden due to too much negative feedback. Show it anyway.
I can't get batch #3 to pass. I'm using python3. Here is my code: https://pastebin.com/iEztHv4J
Any suggestions?
I suggest you reread the problem, is it possible to be at time 20 before time 10?
Using a temporary list and iterating through it (nested for loop) effectively squares the number of operations the program does before printing. Try implementing an algorithm that avoids doing this.
Your solution is O(N^2). The intended solution is O(N log N). Try thinking of a faster way to calculate the speeds.
Edit: Forgot sorting existed
The intended solution is not necessarily
. I think
would be more correct.
There are no restrictions on the number of decimal points; More precise is better
I only printed to 1 decimal place during CCC 🐒
orz timothy cco chad passing s1 with only 1 decimal place
This comment is hidden due to too much negative feedback. Show it anyway.
If you want to print a floating-point value
x
in decimal format withn
digits after the decimal point withstd::cout
, use the following:Use doubles not floats.