Return of the Digger
The adventures of "Digger" continue as he once again searches for treasure. This time, his money senses detect it underground. His plan is to dig down to it using an automatic pickaxe and his souped-up pneumatic drill.
The treasure is within a thin stretch of land, running West to East, that is made up of dirt and some rocks. The stretch is L (1 ≤ L ≤ 200) metres long. Digger's money senses are very exact, and he knows the location of the treasure he seeks - it is no more than 10000 metres below the surface. In addition to money senses, he apparently also has rock senses, which can pinpoint N (1 ≤ N ≤ 5000) rocks among the dirt, none of which will be at a depth of more than 10000 metres.
Digger's specially-designed pneumatic drill can only go straight down, and it can tunnel through dirt easily - however, it isn't equipped with breaks, so it keeps on going until it hits a rock. When this happens, it stops just above the rock, but the drill bit also breaks. This time, Digger doesn't have to worry about fuel - instead, he just wants to avoid breaking his drill bits! Once stationary, Digger can also use his pickaxe to dig left and right (yes, even through rocks!), but he can't dig up or down with it.
The treasure is pretty fragile, so Digger definitely doesn't want to drill right into it. Instead, he can either get to the same depth as it and use his pickaxe to dig to it, or he can use his pneumatic drill to go right past it (either 1 metre to the left or right of it). However, once he gets his hands on the treasure, Digger's plan isn't complete - he intends to keep drilling down until he gets to China. As such, he must first navigate past the deepest of the N rocks - at that point, it's all dirt (or so he hopes...).
Digger can start anywhere on the surface. Determine the minimum amount of drill bits that he must break in order to retrieve the treasure and dig down past all the rocks, if it's possible at all.
Input
| Line 1: | L and N — respectively, the length of the stretch of land and the number of rocks. |
| Lines 2..N+1: | A, B, — the i-th line gives the location of the (i-1)-th rock, where A is its depth in metres, and B is its distance from the West edge of the stretch of land (in metres). |
| Lines N+2: | Y and X — the location of the treasure, where Y is its depth in metres, and X is its distance from the West edge of the stretch of land (in metres). The treasure will not be within a rock. |
Output
If it's impossible for Digger to reach the treasure and dig down past all the rocks, output "Use dynamite".
Otherwise, output a single number - the minimum number of drill bits Digger must break to accomplish this.
Sample Input
10 20 1 5 2 1 2 2 2 4 2 5 2 6 2 8 2 9 3 3 4 7 4 8 4 9 5 3 5 4 5 5 5 6 6 3 10 1 10 2 10 7 8 6
Explanation
A bird's-eye-view cross-section of the cave would look like this ('.': dirt, 'x': rock, 'T': treasure):
0 2 4 etc 1 .....x.... .xx.xxx.xx 3 ...x...... .......xxx 5 ...xxxx... ...x..... e .......... t ......T... c .......... .xx....x.. ..........
Sample Output
3
Explanation
Digger starts on the surface, 7 metres from the West edge of the stretch of land. He drills down for 3 metres until he hits a rock and breaks his first drill bit. He then uses his pickaxe to walk to the left, and drills down another metre, hitting another rock and breaking his second drill bit. He then walks to the rick (through a rock), and drills down for 5 metres, picking up the treasure on the way, until he hits another rock and breaks his third and final drill bit. He then walks to the right and drills down past the last rock. This route is shown below ('D': drill, '<' or '>': pickaxe):
xxDxxxxxxxxx xx...xxxxxxx xxxxDDxxxxxx xxxxx.xxxxxx xxxxxDxxxxxx xxxxx.Txxxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxx
All Submissions
Best Solutions
Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Oct 05, 2008
Author: SourSpinach
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
instead of minimum drill bits to be stationary at a certain level,
deepest valid level for a certain number of drill bits would be faster on average (less levels are likely to be checked)
PS.
BB, Any good websites for IOI topics?
PPS
Omegle no longer works on this site
Also, if you're already below the treasure, make sure you've already picked it up - otherwise, there's no point in going on.
As such, you only really need to figure the minimum number of drill bits to be stationary (not in mid-drill) on a certain level.