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 A_i to B_i, inclusive (1 ≤ A_i ≤ B_i ≤ 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 h₁, he may only perform one of the following two possible actions:

1. Jump upwards by a height of exactly J (1 ≤ J ≤ H), such that his new height is h₂ = h₁ + J, but only if the rope is not covered in itching powder at height h₂.
2. Drop downwards by any height, such that his new height is any integer h₂ (0 ≤ h₂ < h₁), but only if the rope is not covered in itching powder at height h₂.

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.

Subtasks

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.

Input Format

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, A_i and B_i, for i = 1..N.

Output Format

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

5

Sample Input 2

5 2 2
1 1
4 4

Sample Output 2

-1

Sample Explanation

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.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 4.00s
Memory Limit: 128M
Added: Nov 17, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)