Musstest du dieses Spiel bei Skating Link spielen?
Schauen Sie von der Rückseite in der richtigen Reihenfolge und aktualisieren Sie hoch und niedrig Die Korrespondenz ist unterschiedlich, je nachdem, ob die Anzahl in der aktuellen Reihenfolge zu diesem Zeitpunkt größer als hoch, kleiner als niedrig oder dazwischen ist. Niedrig wird jedes Mal aktualisiert, aber hoch ist nicht immer der Punkt, der mich erwischt hat
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)
Da die Runde bestenfalls 10 ** 5 beträgt, ist es in Ordnung, wenn es um logN geht, auch wenn Sie die Anzahl der Personen festlegen und simulieren Sie können also die Anzahl der Personen vor Spielbeginn durch Dichotomisierung ermitteln Wenn die runde Einstellung nicht möglich ist, ist sie fehlerhaft. Simulieren wir also endlich hoch und niedrig, um zu sehen, ob die Antwort richtig ist.
Am Anfang habe ich mich gefragt, ob ich die Endbedingung oder den Mittelwert um 2 kürzen soll. Ich habe viel probiert, aber ich mag die Art, wie ich es jetzt schreibe Nibutan war verrückt, als ich den anfänglichen Einstellbereich lächerlich machte und kurz vor 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)