GRDJUMP - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You start at (0, 0) and want to reach (A, B).
You can:

  • Move upto two steps right, for a cost of P.
  • Move upto two steps up, for a cost of Q.
  • Move one step right and one up, for a cost of R.

Find the minimum cost to reach (A, B).

EXPLANATION:

The up/right movements are basically independent of each other - only the diagonal move combines them.

So, let’s try and fix the number of diagonal moves we make.
Suppose we make d diagonal moves. This has a cost of d\cdot R, and will leave us at (d, d).

After that, only up/right moves can be made, and those are independent so we treat them separately.

  • The x-coordinate is currently d but needs to become A.
    • If d \gt A this is impossible since we can only increase it.
    • So, assume d \le A, and we need to cover a distance of A-d with the rightward moves.
    • It’s optimal to move two steps as many times as we can; with maybe only the last move being one step.
      So, the number of moves equals \text{ceiling}\left(\frac{A-d}{2}\right), with the cost being this quantity multiplied by P.
  • The y-coordinate is currently d but needs to become B.
    • Again, if d \gt B this is impossible.
    • If d \le B then the same reasoning tells us that the number of moves needed equals \text{ceiling}\left(\frac{B-d}{2}\right), so multiply this by Q to get the cost of this part.

Thus, with d fixed, the remaining cost can be computed in constant time.

Since A, B \le 100 and we only need to try d \in [0, \min(A, B)], this \mathcal{O}(\min(A, B)) algorithm is perfectly fast - we can simply try all valid d, compute the cost for each, and take the best answer.

TIME COMPLEXITY:

\mathcal{O}(\min(A, B)) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    a, b, x, y, z = map(int, input().split())

    ans = 10**9
    for d in range(0, min(a, b)+1):
        ans = min(ans, d*z + x*((a-d+1)//2) + y*((b-d+1)//2))
    print(ans)