CCC '26 S1 - Baby Hop, Giant Hop

Canadian Computing Competition: 2026 Stage 1, Senior #1

Samantha the Frog is hopping between lily pads arranged in a straight line, evenly spaced. There are an infinite number of lily pads. The lily pads are numbered, in order, using integers. For every integer, there is also a lily pad. Samantha starts on a lily pad numbered $A$ and would like to hop onto a lily pad numbered $B$. She can take a giant hop of length $K$, or a baby hop of length $1$. Each hop can be either forwards or backwards.

Samantha would like to know the fewest number of hops needed to get from $A$ to $B$. But sometimes, she would like to know the second fewest number of hops needed.

Input Specification

The first line of input contains a single integer, $A$, the starting lily pad ($-10^{18} \le A \le 10^{18}$).

The second line of input contains a single integer, $B$, the ending lily pad ($-10^{18} \le B \le 10^{18}$).

The third line of input contains a single integer, $K$, the distance of a giant hop ($2 \le K \le 10^{18}$).

The fourth line of input contains the integer, $T$, which is either $1$ or $2$, indicating if the fewest (when $T = 1$) or second fewest (when $T = 2$) number of steps should be found.

The following table shows how the 15 available marks are distributed:

Note that for full marks, solutions will need to handle 64-bit integers. For example:

• in C/C++, the type long long should be used;
• in Java, the type long should be used.

Output Specification

On a single line, output:

• the fewest number of hops, if $T = 1$
• the second fewest number of hops, if $T = 2$

required to move from lily pad $A$ to lily pad $B$.

Sample Input 1

Sample Output 1

Explanation for Sample Output 1

Samantha hops to lily pads labeled 3, 6, and 9, with three giant hops, and then hops to the lily pad labeled 10 with one baby hop.

---

Sample Input 2

Sample Output 2

Explanation for Sample Output 2

Samantha hops to lily pads labeled 4, 8, and 12, with three giant hops, and then hops to the lily pad labeled 11 with one (backwards) baby hop.

---

Sample Input 3

Sample Output 3

Explanation for Sample Output 3

The fewest number of hops needed (4) was found in Sample 2. In this input, the second fewest number of steps is to be found, since $T = 2$. Samantha hops to lily pads labeled 4 and 8 with two giant hops, and then hops to the lily pad labeled 11 with three baby hops.

---

Sample Input 4

Sample Output 4