AGC044A

AC

Instead of going from 0 to N as the problem states, we will go from N to 0, and avoid the trap of "doing too many +1's and eating up time" by making the choices four: "move up to a multiple of 2 and divide by 2", "do the same for 3", "do the same for 5", and "move up to 0". [time reversal (physics)

Starting from N, the above four operations are performed on the "largest unexplored number (vertex)". Because all operations decrease the number, the largest number has no other choice but to reach that number, and it is determined that the "tentative minimum score" is truly the minimum score.

I put the "tentative minimum score" for each vertex into a Python dict. You don't want to put it in an array because the definition range is 10^18.

I usually kind of do INF=10**10 or something and think "that's good enough", but this problem N is 10^18 max and each cost is 10^9 max, so it easily exceeds. It subtly WAs. I haven't thought about how much is the theoretical maximum, but I'll keep it a large enough number.

AC in pure Python

code:python

INF = 10 ** 27 + 1

def solve(N, A, B, C, D):

cost = {N: 0}

def put(n, c):

heappush(to_visit, -n)

visited = N + 1

while to_visit:

n = -heappop(to_visit)

if n == visited:

continue

visited = n

put(0, c + n * D)

if n % 2 == 0:

put(n // 2, c + A)

else:

put((n+1) // 2, c + A + D)

put((n-1) // 2, c + A + D)

if n % 3 == 0:

put(n // 3, c + B)

elif n % 3 == 1:

put((n-1) // 3, c + B + D)

put((n+2) // 3, c + B + D * 2)

else:

put((n+1) // 3, c + B + D)

put((n-2) // 3, c + B + D * 2)

if n % 5 == 0:

put(n // 5, c + C)

elif n % 5 == 1:

put((n-1) // 5, c + C + D)

put((n+4) // 5, c + C + D * 4)

elif n % 5 == 2:

put((n-2) // 5, c + C + D * 2)

put((n+3) // 5, c + C + D * 3)

elif n % 5 == 3:

put((n+2) // 5, c + C + D * 2)

put((n-3) // 5, c + C + D * 3)

elif n % 5 == 4:

put((n+1) // 5, c + C + D)

put((n-4) // 5, c + C + D * 4)

---