Battle of Black Water
All submissions for this problem are available.
During the Battle of Blackwater, Tyrion Lannister was the Hand of the King. So, the responsibility of saving King's Landing was on him as he knew about the bravery of King Joffrey and also Stannis had larger army. Tyrion knew that he will not be able to defeat Stannis in fair battle, so he approached Alchemists' Guild for wildfire, an extremely volatile substance which explodes with tremendous force and burns with a fire that water cannot extinguish.
Stannis' army was divided into n parts, each part in one ship. On the night of battle, Tyrion saw n ships approaching towards the port, each ship at some distance from the port and all ships moving in a straight line. In order to destroy all the ships in one explosion, he loaded all the wildfire in one ship. Tyrion has only 15 minutes left to ignite the wildfire or it will be self-ignited and Stannis' whole army will not be destroyed and they'll lose the battle. Otherwise, if the ship containing wildfire reaches the desired spot before 15 min, Tyrion can monitor when it will ignite and thus, he will win the battle. At the present moment, he knows the position of each ship, x1i (y-coordinate) and the position of that ship after 15 minutes, x2i (y-coordinate). At present, the ship containing wildfire is at y-coordinate x0.
What is the minimum distance that the ship containing wildfire should move in 15 minutes in order to destroy all the ships of Stannis? The wildfire will destroy a ship i if it is within the segment that the ship i covers in 15 minutes.
If no possible solution exist, print -1.
The first line of the input contains the number of test cases t. Then t test cases follow.
First line of each test case contains 2 space-separated integers, n and x0 where n is number of ships of Stannis' army and x0 is present position of ship containing wildfire.
Then n lines follow, each containing two space-separated integers x1i and x2i where x1i is initial position of i-th ship and x2i is the position of i-th ship after 15 minutes.
Print the minimum distance to be covered by the ship containing wildfire in order to defeat Stannis in 15 minutes.
1 <= t <= 100
1 <= n <= 100
0 <= x0 <= 1000
0 <= x2i <= x1i <= 1000
Input: 1 4 0 10 5 8 3 12 5 20 5 Output: 5
In order to destroy all the 4 ships, the ship containing wildfire should be in between coordinates 8 to 5. As its present coordinate is 0, minimum distance to be covered is 5 units.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.