z-rings
For his 8th birth day, Little Z. got a map of the secret pirate treasure. When he turned 18. Little Z. decided to try to find the place where the treasure is hidden. After months of traveling and trying to understand the puzzles on the map, he found the cave where the treasure is hidden.
When he entered the cave, he saw a pile of gold rings. All the rings had the different thickness and radius. In order to leave some of the treasure for future adventurers (e.g. Indiana Jones) the map had a message saying that only one ring can be taken out of the cave. It said that there will be a monster at the exit checking how many rings had been taken out. While looking for the largest ring, little Z noticed that the rings are made in such a way so that when a larger ring is put above a smaller one, then the smaller one can't be seen by the monster. More precisely, a ring whose inner radius is equal to some other ring's outer radius can be put on top of it.
Little Z. decided to arrange some of the rings so that he obtains the thickest ring possible (the thickness of the ring is defined as the difference between its outer and inner radius).
In the lines 2 to N+1, there will be two integers Ri_u and Ri_s , representing the inner and outer radius of each of the i-th ring. (0 < Ri_u < Ri_s <= 2000000000).
10
1 3
1 5
2 3
3 9
5 6
7 10
7 11
6 8
2 3
10 11Output:
8Explanation: Except for the rings themselves, the following thicknesses can be obtained by combining rings:
Combining 1-3 with 3-9 (1-9);
Combining 2-3 with 3-9 (2-9);
Combining 1-5 with 5-6 and with 6-8 (1-8);
Combining 7-10 with 10-11 (7-11);
The thickest obtained ring is the first one listed above, and it has the thickness of 9-1=8.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.