[Solution] Rocket Pack CodeChef Solution 2022

Problem

Chef's robot starts from the coordinate $(0, 0)$ and wishes to reach to the coordinate $(N, M)$.

The initial energy of the robot is $0$. There are $K$ batteries kept at some of the coordinates such that picking up the $i^{th}$ battery costs $C_i$ units, and, on picking the $i^{th}$ battery, the current energy of the robot becomes $E_i$.

Note that one coordinate can have multiple batteries but the robot can pick at most one battery out of those.

For example, if the robot reaches a certain coordinate with energy $A$ and there are two batteries with energy $B_1$ and $B_2$ on that coordinate, the robot may choose at most one battery out of these. On choosing the first battery, the energy of the robot becomes $B_1$ (not $A+B_1$).

The robot can walk in all the four directions as follows:

• Move up: Moving from coordinate $(X, Y)$ to $(X, Y+1)$, the robot loses $1$ unit of energy.
• Move down: Moving from coordinate $(X, Y)$ to $(X, Y-1)$, the robot gains $1$ unit of energy.
• Move right: Moving from coordinate $(X, Y)$ to $(X+1, Y)$, the robot loses $1$ unit of energy.
• Move left: Moving from coordinate $(X, Y)$ to $(X-1, Y)$, the robot gains $1$ unit of energy.

Find the minimum cost to reach $(N, M)$ if the robot maintains a non-negative energy throughout the journey (including the destination).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Input Format

• The first line of input contains a single integer $T$, the number of test cases. The description of the test cases follows.
• Each test cases consists of two lines of input.
  • The first line contains three positive integers $N, M,$ and $K$, the coordinates of the destination and the number of batteries.
  • Next $K$ lines have four space-separated integers each: $X_i, Y_i, C_i, E_i$. The $i^{th}$ line indicates that the coordinate $(X_i, Y_i)$ has a battery with cost $C_i$ and energy $E_i$.
• The input data guarantees that the robot can reach the destination.

Output Format

For each test case, output a single integer, the minimum cost from $(0,0)$ to $(N, M)$.

Explanation:

Test case $1$: Use the first battery with cost $10$. Thus, at coordinate $(0, 0)$, the energy of the robot becomes $10$ units. The robot can traverse the path :$(0,0) - (0, 1) - \ldots - (0, 5) - (1, 5) - \ldots - (5,5)$. It can be shown that the robot cannot reach the destination in less than $10$ units cost.

Test case $2$:

• Use the $2^{nd}$ battery: At coordinate $(0, 0)$, robot picks the $2^{nd}$ battery and the energy of the robot becomes $4$ units. The robot can move to coordinate $(2, 2)$ using this energy. On reaching $(2, 2)$, robot's energy is $0$.
• Use the $3^{rd}$ battery: At coordinate $(2, 2)$, robot picks the $3^{rd}$ battery and the energy of the robot becomes $1$ unit. The robot can move from $(2, 2)$ to $(2, 1)$ and gain $1$ unit of energy. Thus, it has $2$ units of energy now. It can now move from $(2, 1)$ to $(4, 1)$ using this energy.
• Use the $4^{th}$ battery: At coordinate $(4, 1)$, robot picks the $4^{th}$ battery and the energy of the robot becomes $5$ units. The robot can now move from $(4, 1)$ to $(5, 5)$.