Interview Questions/Coding/Jump Pad Exit Tracker

Jump Pad Exit Tracker

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Jump Pad Exit Tracker

A training corridor has numbered jump pads in one row. Pad i has a power value a_i. When a token lands on pad i, it immediately jumps to i + a_i. If that position is outside the corridor, the token exits. The control room processes two kinds of operations: update one pad's power, or launch a token from a pad and report the last pad touched before exit and the number of jumps made. Input Format: The first line contains t. Each case starts with n and m. The next line contains n power values. Each of the next m lines is either 0 a b, meaning set pad a to power b, or 1 a, meaning launch from pad a. Output Format: For every launch operation, print two integers: the last pad touched and the jump count.

Examples

Example 1

Input:

1
8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2

Output:

8 7

Explanation: Launching from pad 1 first walks through pads 1 to 7 before leaving from pad 8 after 7 jumps. Later updates change the path lengths shown in the following output lines.

Approach hint

Many launches repeat long stretches of the same corridor.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp