Solve Prime Jumps and Pipeline Scaling

An online assessment contains two independent coding problems. Solve both.

Problem 1: Prime-Constrained Score Jump

You are given an integer array score of length n and an integer k. You start at index 0, and your initial total is score[0]. On each move, you may jump from index i to index j only if:

• j > i,
• j - i <= k, and
• j - i is a prime number.

When you land on an index, you add score[j] to your total. Return the maximum total score you can obtain when reaching index n - 1. If index n - 1 cannot be reached, return null.

Assume score may contain negative values.

Problem 2: Maximize Pipeline Throughput

You are given a serial processing pipeline with n services. Service i has:

• base throughput t[i], and
• expansion cost cost[i].

The pipeline throughput is the minimum throughput among all services.

You may expand any service any nonnegative integer number of times. If service i is expanded x times, then:

• its throughput becomes t[i] * (1 + x), and
• the total money spent on that service is x * cost[i].

Given a total budget budget, return the maximum possible overall pipeline throughput.

Part 1: Prime-Constrained Score Jump

You are given an integer array score and an integer k. You start at index 0 with an initial total equal to score[0]. On each move, you may jump from index i to index j only if j > i, j - i <= k, and j - i is a prime number. When you land on an index, you add score[j] to your total. Return the maximum total score obtainable when reaching index len(score) - 1. If the last index cannot be reached, return None. The score array may contain negative values.

Constraints

• 1 <= len(score) <= 5000
• -100000 <= score[i] <= 100000
• 0 <= k <= 5000
• A jump length must be prime, so length 1 is not allowed.

Examples

Example 1

Input: ([5, -2, 4, 10, -1], 3)
Output: 8

Explanation: Valid jump lengths are 2 and 3. The only way to reach index 4 is 0 -> 2 -> 4, giving 5 + 4 - 1 = 8.

Example 2

Input: ([10, -100, -5, 20, 1, 50], 3)
Output: 80

Explanation: The best path is 0 -> 3 -> 5 using jumps of length 3 and 2, for a total of 10 + 20 + 50 = 80.

Hints

1. First generate all prime jump lengths up to min(k, len(score) - 1).
2. Use dynamic programming: let dp[i] be the best total score achievable when landing on index i.

Part 2: Maximize Pipeline Throughput

You are given a serial processing pipeline with n services. Service i has base throughput t[i] and expansion cost cost[i]. The pipeline throughput is the minimum throughput among all services. You may expand any service any nonnegative integer number of times. If service i is expanded x times, its throughput becomes t[i] * (1 + x), and the money spent on that service is x * cost[i]. Given a total budget, return the maximum possible overall pipeline throughput.

Constraints

• 1 <= len(t) == len(cost) <= 100000
• 1 <= t[i] <= 1000000
• 1 <= cost[i] <= 1000000
• 0 <= budget <= 1000000000000
• Each service can be expanded only an integer number of times.

Examples

Example 1

Input: ([10, 20, 30], [5, 10, 15], 10)
Output: 20

Explanation: Spend 5 to expand the first service once, raising it to 20. Reaching 25 or more would require also expanding the second service and would exceed the budget.

Example 2

Input: ([7], [3], 10)
Output: 28

Explanation: With one service, spend at most 10 on expansions costing 3 each. Three expansions are possible, so throughput is 7 * 4 = 28.

Hints

1. For a proposed target throughput X, compute the minimum number of expansions each service needs to reach at least X.
2. The feasibility of a target throughput is monotonic: if X is affordable, then every smaller target is also affordable.