Implement a Coin-Constrained Jump Strategy

Problem Description

An autonomous rover is navigating a one-dimensional coordinate track starting at position 0 with an initial speed of 0 and a budget of initial_coins. The goal is to reach position target in the minimum number of jumps without letting the coin balance drop below 0 at any point.

Motion Rules

• At each step, if the rover's current speed is v, it chooses a new speed v' such that: max(1, v - 1) <= v' <= min(max_speed, v + 1) (Note: From the starting state where v = 0, the first jump must always select v' = 1.)
• The rover leaps forward to new_position = current_position + v'.
• The rover cannot jump past target (i.e., new_position <= target).
• The rover cannot land on any position listed in obstacles.

Coin Mechanics

• Track positions may have coin modifiers given by a dictionary coin_changes mapping coordinate p to integer delta:
  • A positive delta adds coins upon landing.
  • A negative delta represents a toll or hazard that subtracts coins upon landing.
  • Positions not present in coin_changes have a delta of 0.
• Upon landing on new_position, the rover's coins update: coins = coins + coin_changes.get(new_position, 0).
• If coins = 0). If target cannot be reached, return -1.

Function Signature

def min_jumps_to_target(
    target: int,
    initial_coins: int,
    obstacles: list[int],
    coin_changes: dict[int, int],
    max_speed: int
) -> int:
    pass

Examples

Example 1

Input:
target = 10
initial_coins = 5
obstacles = []
coin_changes = {6: -10}
max_speed = 4

Output: 5

Explanation: The quickest physical path in distance would take 4 jumps: 0 -> 1 (v=1) -> 3 (v=2) -> 6 (v=3) -> 10 (v=4). However, landing on position 6 deducts 10 coins, dropping the balance to 5 - 10 = -5 1 (v=1) -> 2 (v=1) -> 4 (v=2) -> 7 (v=3) -> 10 (v=3), entirely bypassing position 6 and keeping coins = 5 >= 0.

Example 2

Input:
target = 4
initial_coins = 0
obstacles = [2]
coin_changes = {}
max_speed = 3

Output: -1

Explanation: From position = 0, v = 0, the only valid first move is v' = 1 landing on position 1. From position 1 with v = 1, the possible next speeds are 1 (landing on 2, which is an obstacle) or 2 (landing on 3). From position 3 with v = 2, the next speed must be at least 1, landing at >= 4. A speed of 1 lands on 4 (target). Total jumps: 0 -> 1 -> 3 -> 4 (3 jumps). (Note: If position 3 were also blocked, it would return -1.)

Constraints

• 1 <= target <= 1000
• 0 <= initial_coins <= 1000
• 1 <= max_speed <= 50
• 0 <= len(obstacles) <= target
• All positions in obstacles satisfy 1 <= pos < target.
• coin_changes maps positions 1 <= pos <= target to integers between -1000 and 1000.
• 0 is never an obstacle and has no coin modifier.