[Solution] Rocket Pack solution codechef

Table of Contents

Rocket Pack solution codechef

Rocket Pack solution codechef – 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.

Rocket Pack solution codechef

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).

Input Rocket Pack solution codechef

  • 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).

Rocket Pack solution codechef

  • 1 \leq T \leq 10
  • 1 \leq K \leq 10^5
  • 0 \leq X_i,Y_i \leq 2*10^9
  • 1 \leq N,M,C_i,E_i \leq 2*10^9
  • The sum of K over all test cases won’t exceed 10^5.

Sample 1:

Input

Output

2
5 5 3
0 0 10 10
0 0 2 4
2 2 1 1
5 5 4
0 0 10 10
0 0 2 4
2 2 1 1
4 1 3 5
10
6

Rocket Pack solution codechef 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).

For Solution

“Click Here”

Leave a Comment