It doesn't matter if it's in ascending order or in descending order, so all you have to do is check if you can stack them one by one.
from heapq import heappush, heapreplace
N, *A = map(int, open(0).read().split())
A.sort()
q = [A[0]]
for a in A[1:]:
if a <= q[0] + 1:
heappush(q, a)
else:
heapreplace(q, a)
print(len(q))
Bounce once x, bounce once 3/2 * x, bounce twice 7/4 * x, bounce 3 times 15/8 * x, bounce n times (2 n + 1) </ sup> -1) / 2 n </ sup> * x. D ≤ 10 18 </ sup>, so if you bounce 60 times, the flight distance will not increase after that. You should check if there is an answer when you bounce 60 times, 59 times, ..., once. Since there is an effect of truncation, I checked about ± 100 before and after appropriately and AC.
D = int(input())
def f(x):
result = 0
while x != 0:
result += x
x //= 2
if result >= D:
break
return result
for i in range(60, 0, -1):
t = D * (2 ** (i - 1)) // (2 ** i - 1)
for j in range(-100, 100):
if t + j < 0:
continue
if f(t + j) == D:
print(t + j)
exit()
Recommended Posts