Did you have to play this game on the skating rink?
Look from the back side in order and update high and low Correspondence is different depending on whether the number in the current order is larger than high, smaller than low, or in between at that time. Low is updated every time, but high is not always the point that caught me
math.py
K=int(input())
A=list(map(int,input().split()))
if A[-1]!=2:
print(-1)
exit()
low=2
high=3
for item in A[::-1]:
#print(low,high)
if high<item:
print(-1)
exit()
elif item<low:
low=(-((-low)//item))*item
if low>high:
print(-1)
exit()
high=max(low+item-1,high+item-1-high%item)
else:
low=item
if low>high:
print(-1)
exit()
high=low+item-1
print(low,high)
Since the round is about 10 ** 5 at best, it is okay if it is about logN even if you decide the number of people and simulate So you can find the number of people before the game starts by binary search. If the round setting is not feasible, it will be a bug, so let's finally simulate high and low to see if the answer is correct.
At the beginning, I was wondering whether to truncate the end condition or the middle value by 2. I made a lot of trial and error, but I like the way I write it now Nibutan was crazy when the initial setting range was ridiculous and just before TLE.
bisect.py
K=int(input())
A=list(map(int,input().split()))
def func(num):
for item in A:
num=num//item*item
return num
ok=10**20
ng=0
while ok-ng>1:
mid=(ok+ng)//2
if func(mid)>=2:
ok=mid
else:
ng=mid
low=ok
ok=10**20
ng=0
while ok-ng>1:
mid=(ok+ng)//2
if func(mid)>=4:
ok=mid
else:
ng=mid
high=ng
if func(low)==2 and func(high)==2:
print(low,high)
else:
print(-1)