Woburn Challenge 2018-19 Round 1 - Senior Division
Problem 3: Reach for the Top
It's time for Bob to face his biggest fear at H.S. High School: the dreaded gym class rope climb. In this brutal test of strength and endurance, Bob is tasked with ascending part of the way up an infinitely long vertical rope. He begins by grabbing onto the bottom of the rope, at a height of 0, and must reach any height of H (1 ≤ H ≤ 1,000,000) or greater (measured in metres).
To make matters even worse than usual, Alice has pranked Bob by spreading itching powder on some sections of the rope, which he'll need to avoid along the way! She's done so for N (0 ≤ N ≤ H − 1) sections, the i-th of which covers all heights from Ai to Bi, inclusive (1 ≤ Ai ≤ Bi ≤ H − 1). No two sections overlap with one another, even at their endpoints.
Bob's rope-climbing style is… unusual, to say the least, which may come in handy for avoiding Alice's itching powder. At any point, given that he's currently holding onto the rope at some height h1, he may only perform one of the following two possible actions:
- Jump upwards by a height of exactly J (1 ≤ J ≤ H), such that his new height is h2 = h1 + J, but only if the rope is not covered in itching powder at height h2.
- Drop downwards by any height, such that his new height is any integer h2 (0 ≤ h2 < h1), but only if the rope is not covered in itching powder at height h2.
Both types of actions involved in this technique are understandably quite tiring, so Bob would like to avoid performing more of them than necessary. Help him determine the minimum number of actions he must perform to reach a height of at least H metres, or determine that it's sadly impossible for him to ever reach such a height.
In test cases worth 8/27 of the points, H ≤ 1000 and J ≤ 2.
In test cases worth another 12/27 of the points, H ≤ 1000.
The first line of input consists of three space-separated integers, H, J, and N.
N lines follow, the i-th of which consists of two space-separated integers, Ai and Bi, for i = 1..N.
Output a single integer, either the minimum number of actions required for Bob to reach a height of at least H metres, or −1 if it's impossible for him to do so.
Sample Input 1
12 5 2 2 4 10 10
Sample Output 1
Sample Input 2
5 2 2 1 1 4 4
Sample Output 2
In the first case, Bob can jump up to a height of 5, drop down to a height of 1, jump up to a height of 6, jump up to a height of 11, and finally jump up to a height of 16. This is the only strategy which involves 5 actions, which is the minimum possible number of actions.
In the second case, Bob must start by jumping up to a height of 2. From there, he may not jump upwards to a height of 4 (as the rope is covered in itching powder there), and similarly may not drop down to a height of 1, meaning that he can never grab the rope at any height aside from 0 or 2.
Point Value: 12 (partial)
Time Limit: 4.00s
Memory Limit: 128M
Added: Nov 17, 2018
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3