CCC '26 S1 - Baby Hop, Giant Hop - Olympiads Online Judge

CCC '26 S1 - Baby Hop, Giant Hop

Points: 3 (partial)

Time limit: 3.0s

Memory limit: 1G

Problem type

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$ ~A~ and would like to hop onto a lily pad numbered $B$ ~B~. She can take a giant hop of length $K$ ~K~, or a baby hop of length $1$ ~1~. Each hop can be either forwards or backwards.

Samantha would like to know the fewest number of hops needed to get from $A$ ~A~ to $B$ ~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$ ~A~, the starting lily pad ( $-10^{18} \leq A \leq 10^{18}$ ~-10^{18} \leq A \leq 10^{18}~).

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

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

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

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

Marks Awarded	Bounds on $A,B$ ~A,B~	Bounds on $K$ ~K~	Bounds on $T$ ~T~	Additional Restrictions
5 marks	$0 \le A, B \le 10$ ~0 \le A, B \le 10~	$K=2$ ~K=2~	$T=1$ ~T=1~	Only hops in the positive direction needed
6 marks	$-10^{18} \leq A, B \leq 10^{18}$ ~-10^{18} \leq A, B \leq 10^{18}~	$2 \leq K \leq 10^{18}$ ~2 \leq K \leq 10^{18}~	$T=1$ ~T=1~	None
2 marks	$0 \le A, B \le 100$ ~0 \le A, B \le 100~	$2 \le K\leq 4$ ~2 \le K\leq 4~	$T=1$ ~T=1~ or $T=2$ ~T=2~	None
2 marks	$-10^{18} \leq A, B \leq 10^{18}$ ~-10^{18} \leq A, B \leq 10^{18}~	$2 \leq K \leq 10^{18}$ ~2 \leq K \leq 10^{18}~	$T=1$ ~T=1~ or $T=2$ ~T=2~	None

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$ ~T=1~
the second fewest number of hops, if $T=2$ ~T=2~

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

Sample Input 1

Output for Sample Input 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$ ~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

Comments

0

JamesJiao commented on Feb. 26, 2026, 11:35 p.m.

I've never been so happy to solve a 3p before

19

Ryan_Sharma commented on Feb. 26, 2026, 5:20 a.m.

I hope this problem dies

0

do_ur_homwork commented on Feb. 26, 2026, 8:45 p.m.

why 3p???

1

Kirito commented on Feb. 26, 2026, 10:41 p.m.

One point for each if statement you need in the solution.