Time of collisionsProblem code: COLLTIME |
All submissions for this problem are available.
Identical small balls are located on a straight line and can move along this line only. Each ball moves with a constant velocity, but velocities of different balls may be different. When two balls meet, a perfectly elastic collision occurs. It's a common-known physical fact that when two equal-mass physical bodies, say A and B, collide perfectly elastically, they swap their velocities. That is, A's new velocity is B's old velocity and B's new velocity is A's old velocity. Your task is to find the sum of all moments of time when collisions occur. If three or more balls collide at the same moment of time in the same place then the following will occur. Let the collision involves k >= 3 balls then you should consider this collision as simultaneous k*(k-1)/2 collisions. It means that you should count the moment of time of this collision k*(k-1)/2 times in you answer. The new velocities of these balls after all collisions have occurred will be as follows: the 1-st and k-th balls swap their velocities, 2-nd and k-1-th balls swap their velocities and so on. Explicitly, for each i between 1 and k/2 balls i and k+1-i swap their velocities. Here we enumerate balls in order they were on the line in the moment of time just before the collision.
Input
The first line contains a single positive integer T <= 10, the number of test cases. T test cases follow. The first line of each test case contains the number of balls N (1 <= N <= 50000) . Each of the following N lines contains 2 space-separated integers - the starting coordinate and the velocity of corresponding ball. All start coordinates are not greater than 1000000 in absolute value and all velocities are not greater than 20 in absolute value. All start coordinates are different.
Output
For each test case, output a single line containing number S - the sum of moments of time of all collisions. If there are infinitely many collisions then print "INF". If there are only finitely many of them then it is guaranteed that the answer S is rational and you should print it in the form of a mixed number. That is if S is an integer then just print S, otherwise if it is less then one and equals to irreducible fraction P/Q then print "P/Q", otherwise print "A P/Q" where A is an integer part of S and P/Q is its fractional part in irreducible form. Note that for all fractions P/Q in output specifications we have P < Q.
Example
Input:
3
2
-1 1
1 -1
2
0 1
1 -1
3
-1 1
2 -1
3 -5
Output:
1
1/2
2 5/12
Explanation
In the third test case we have collisions in the following moments of time: 1/4, 2/3 and 3/2.
| Author: | anton_lunyov |
| Date Added: | 16-01-2011 |
| Time Limit: | 3 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
HELP
Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:
- Accepted
Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark. - Time Limit Exceeded
Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. - Wrong Answer
Your program compiled and ran succesfully but the output did not match the expected output. - Runtime Error
Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section. - Compilation Error
Your code was unable to compile. When you see this icon, click on it for more information.
If you are still having problems, see a sample solution here.
