I thought that if it was Python, I would go through it from the front without thinking about it, but after all I passed (laughs). To deal with Python 10 10 7 Seems to be needed.
from math import isqrt
N = int(input())
print(len(str(isqrt(N))))
Although it was AC during the contest, it was dropped by a judge by an additional test after the contest.
It's easy to see that you should use the maximum value of A i when you reach the goal. Otherwise, you can basically use the most efficient A i . However, it is a little inefficient to slip in, but the number of operations is small. Using A i may minimize the number of operations, so it will be wrong if it is Greedy. Added. That's the pattern, and during the contest, Greedy was able to AC.
The implementation throws away A i , which has the same number of operations but increases more than that, or uses a priority queue to find the minimum value in a Dijkstra style. It is unknown how effective it was, but it seems that it was twice as fast as the Writer solution.
from heapq import heappop, heappush
N, M, P, *A = map(int, open(0).read().split())
def f(x):
c = 0
while x % P == 0:
c += 1
x //= P
return (x, c)
max_A = max(A)
if max_A > M:
print(1)
exit()
b = {}
for m, c in map(f, A):
b.setdefault(c, 0)
b[c] = max(b[c], m)
t = 1
for k in sorted(b):
if b[k] <= t:
del b[k]
else:
t = b[k]
if len(b) == 0:
print(-1)
exit()
q = [(0, 1)]
max_x = {}
max_x[0] = 1
while q:
c, x = heappop(q)
if max_x[c] > x:
continue
if x * max_A > M:
print(c + 1)
break
for k in b:
nc = c + 1 + k
nx = x * b[k]
max_x.setdefault(nc, 0)
if nx > max_x[nc]:
max_x[nc] = nx
heappush(q, (nc, nx))
Recommended Posts