GlobeX Cup '19 S2 - Predicting Collisions

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
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

The intergalactic war has started! Willie lives in a war zone and he is a soldier who wants to protect his planet. The planet's peacekeepers have gathered intel on the immediate missile launch that may affect Willie's city. This missile launch is composed of two advanced projectiles. There is a secret operation in the planet that Willie lives in. The operation involves extremely reactive substances that may destroy the planet if the two projectiles collide within a specific area. Willie would like to find the collision point of the two projectiles' paths within given boundaries. Due to Willie's dislike for Math and Physics, he has come to you for help.

For simplicity, The universe can be modelled as a 2D plane. The trajectory of each projectile can be modelled as a polynomial function. A collision is defined as a point where the two functions meet and are not tangent to each other. In other words, at a collision point, the two functions have to cross each other and not merely touch. The projectiles will not change course even if they collide because this is a new type of technology. Given the functions that represent the trajectories, find the collision point of the two projectiles within the domain [a,b]. In other words, if the functions are f(x) and g(x), find the value of x such that f(x) = g(x) and a \le x \le b. It is guaranteed that there is only one point in this domain where the two functions meet and that point is a collision point.

Input Specification

Line 1: N, the degree of the first polynomial trajectory.

Line 2: N + 1 integers, separated by a single space, representing the coefficients of the first polynomial in descending order.

Line 3: M, the degree of the second polynomial trajectory.

Line 4: M + 1 integers, separated by a single space, representing the coefficients of the second polynomial in descending order.

Line 5: a and b, separated by a singe space, indicating the domain of the intersection.

Output Specification

The first and only line of output contains the value of x, which is the x-coordinate of the intersection point.

Note: If the official answer is z and |z - x| < 10^{-8}, your answer will be considered correct.


0 \le N,M \le 5

-1000 \le a \le b \le 1000

For any coefficient c in the input, -1000 \le c \le 1000. It is guaranteed that the leading coefficients will not be 0.


Subtask 1 [10%]

0 \le N,M \le 1

Subtask 2 [20%]

0 \le N,M \le 2

Subtask 3 [70%]

No additional constraints.

Sample Input

2 0
-1 3
0 3

Sample Output



There are no comments at the moment.