Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial as f
n,a,b = map(int,input().split())
print(2**n-f(n)//(f(a)*f(n-a))-f(n)//(f(b)*f(n-b))-1)

Fixed submission:
mod = 10**9+7
n,a,b = map(int,input().split())
base = pow(2,n,mod)-1
def comb(n,k):
  comb = 1
  for i in range(n-k+1,n+1):
    comb *= i
    comb %= mod
  for i in range(1, k+1):
    comb *= pow(i,mod-2,mod)
    comb %= mod
  return comb
print((base-comb(n,a)-comb(n,b))%mod)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))[
ans = 1
for a in A:
  if a%2==0:
    if a%3!=0 and a%5!=0:
      ans = 0
print('APPROVED' if ans else 'DENIED')

Fixed submission:
n = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
  if a%2==0:
    if a%3!=0 and a%5!=0:
      ans = 0
print('APPROVED' if ans else 'DENIED')
Buggy python submission (verdict: Time Limit Exceeded):
c={}
for _ in range(int(input())): s=input(); c[s]=c.get(s,0)+1
print(*sorted(k for k in c if c[k]==max(c.values())))

Fixed submission:
N = int(input())
count = {}
for i in range(N):
    s = input()
    count.setdefault(s, 0)
    count[s] += 1
p = max(count.values())
ans = []
for k in count.keys():
    if count[k] == p:
        ans.append(k)
ans.sort()
for a in ans:
    print(a)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = {input().split()}
print('YNEOS'[len(A)==N::2])


Fixed submission:
N = int(input())
A = set(input().split())
print('YNEOS'[len(A)!=N::2])

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = {input().split()}
print('YNEOS'[len(A)==N::2]

Fixed submission:
N = int(input())
A = set(input().split())
print('YNEOS'[len(A)!=N::2])
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
dices = list(map(int, input().split()))

exv = [(e+1)/2 for e in dices]
temp = sum(m[0:K])
result = temp
for i in range(N-K):
    temp -= dices[i]
    temp += dices[i+K]
    if temp > result:
        result = temp
print(result)

Fixed submission:
N, K = map(int, input().split())
dices = list(map(int, input().split()))

exv = [(e+1)/2 for e in dices]
temp = sum(exv[0:K])
result = temp
for i in range(N-K):
    temp -= exv[i]
    temp += exv[i+K]
    if temp > result:
        result = temp
print(result)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
Dices = list(map(int, input().split()))
Que = []
Eyes = {}
for i in range(K):
    Que.append(Dices[i])
Eyes[K]=sum(Que)
for i in range(K+1, N):
    Que.pop(0)
    Que.append(Dices[i])
    Eyes[i] = Eyes[i-1]-Que[0]+Que[-1]
a = 0
b = 0
for k, v in Eyes.items():
    if v > a:
        a = v
        b = k
ans = 0
for i in range(k-K+1, k+1):
    ans += (Dices[i]+1)/2
print(ans)

Fixed submission:
N, K = map(int, input().split())
dices = list(map(int, input().split()))

exv = [(e+1)/2 for e in dices]
temp = sum(exv[0:K])
result = temp
for i in range(N-K):
    temp -= exv[i]
    temp += exv[i+K]
    if temp > result:
        result = temp
print(result)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
Dices = list(map(int, input().split()))
Que = []
Eyes = {}
for i in range(K):
    Que.append(Dices[i])
for i in range(K, N):
    Eyes[i] = sum(Que)
    Que.pop(0)
    Que.append(Dices[i])
a = 0
b = 0
for k, v in Eyes.items():
    if v > a:
        a = v
        b = k
ans = 0
for i in range(k-K+1, k+1):
    ans += (Dices[i]+1)/2
print(ans)

Fixed submission:
N, K = map(int, input().split())
dices = list(map(int, input().split()))

exv = [(e+1)/2 for e in dices]
temp = sum(exv[0:K])
result = temp
for i in range(N-K):
    temp -= exv[i]
    temp += exv[i+K]
    if temp > result:
        result = temp
print(result)
Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
spel = [list(map(int,input().split())) for i in range(n)]
dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(h):
  for damage,cost in spel:
    n_i = min(i+damage,h)
    dp[n_i] = min(dp[n_i],dp[i]+cost)
print(dp[h])

Fixed submission:
h,n = map(int,input().split())
spel = [list(map(int,input().split())) for i in range(n)]
dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(h):
  for damage,cost in spel:
    n_i = min(i+damage,h)
    dp[n_i] = min(dp[n_i],dp[i]+cost)
print(dp[h])
Buggy python submission (verdict: Runtime Error):
s = input()
st = 'abcdefghijklmnopqrstuvwxyz'
print(st[index(s)+1])

Fixed submission:
s = input()
st = 'abcdefghijklmnopqrstuvwxyz'
print(st[st.index(s)+1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
tst = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        st[i].append([x,y])
ans = 0
for bit in range(1<<n):
    honest = [0]*n
    check = 1
    for i in range(n):
        if (bit>>i)&1:
            honest[-1-i] = 1
    for i in range(n):
        if not honest[i]:
            continue
        for l in tst[i]:
            if l[1]!=honest[l[0]-1]:
                check = 0
                break
    if check:
        ans = max(ans,sum(honest))
print(ans)

Fixed submission:
n = int(input())
tst = [[] for i in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x,y = map(int,input().split())
    tst[i].append([x,y])
ans = 0
for bit in range(1<<n):
  liars = [0]*n
  check = 1
  for i in range(n):
    if (bit>>i)&1:
      liars[-1-i] = 1
  for i in range(n):
    if liars[i]:
      for l in tst[i]:
        if l[1]!=liars[l[0]-1]:
          check = 0
          break
  temp = 0
  if check:
    temp = sum(liars)
  ans = max(ans,temp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int,input().split()))
a = [format(i,'b') for i in A]
ans = 0
mod = 10**9+7
for i in range(60):
  cnt = 0
  for v in a:
    if len(v)<i+1:
      continue
    if v[-1-i]=='1':
      cnt += 1
  cnt = cnt*(n-cnt)%mod
  ans += cnt*(2**i)%mod
print(ans%mod)

Fixed submission:
n = int(input())
A = list(map(int,input().split()))
a = [format(i,'b') for i in A]
ans = 0
mod = 10**9+7
for i in range(60):
  cnt = 0
  for v in a:
    if len(v)<i+1:
      continue
    if v[-1-i]=='1':
      cnt += 1
  cnt = cnt*(n-cnt)%mod
  ans += cnt*(2**i)%mod
print(ans%mod)
Buggy python submission (verdict: Runtime Error):
s = input()
d = ['SUN','MON','TUE','WED','THU','FRI','SAT','a']  
print(d.index(s)[::-1])

Fixed submission:
s = input()
d = ['SUN','MON','TUE','WED','THU','FRI','SAT','a']  
d.reverse()
print(d.index(s))
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()
if s%2==1:
  print('No')
else:
  print('Yes' if s[:n//2]==s[n//2:] else 'No')

Fixed submission:
n = int(input())
s = input()
if n%2==1:
  print('No')
else:
  m = n//2
  print('Yes' if s[:m]==s[m:] else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
x,y = map(int,input().split())
mod = 10**9+7
def count_route(x,y):
  if x<=0 or y<=0:
    return 0
  elif x/y>2 or y/x>2:
    return 0
  elif x%y==0 and x//y==2:
    return 1
  elif y%x==0 and y//x==2:
    return 1
  else:
    return sum([count_route(x-1,y-2)%mod,count_route(x-2,y-1)%mod])
print(count_route(x,y))


Fixed submission:
x,y = map(int,input().split())
mod = 10**9+7
def comb(a,b):
  comb = 1
  chld = 1
  for i in range(b):
    comb = comb*(a-i)%mod
    chld = chld*(b-i)%mod
  return (comb*pow(chld,mod-2,mod))%mod
if (x+y)%3!=0:
  print(0)
else:
  nm = (x+y)//3
  n = y-nm
  m = x-nm
  if n>=0 and m>=0:
    print(comb(n+m,m))
  else:
    print(0)

Buggy python submission (verdict: Runtime Error):
x,y = map(int,input().split())
mod = 10**9+7
def count_route(x,y):
  if x<=0 or y<=0:
    return 0
  elif x/y>2 or y/x>2:
    return 0
  elif x%y==0 and x//y==2:
    return 1
  elif y%x==0 and y//x==2:
    return 1
  else:
    return sum([count_route(x-1,y-2)%mod,count_route(x-2,y-1)%mod])
print(count_route(x,y))

Fixed submission:
x,y = map(int,input().split())
mod = 10**9+7
def comb(a,b):
  comb = 1
  chld = 1
  for i in range(b):
    comb = comb*(a-i)%mod
    chld = chld*(b-i)%mod
  return (comb*pow(chld,mod-2,mod))%mod
if (x+y)%3!=0:
  print(0)
else:
  nm = (x+y)//3
  n = y-nm
  m = x-nm
  if n>=0 and m>=0:
    print(comb(n+m,m))
  else:
    print(0)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
p = list(map(int,input().split()))
Q = deque()
Q.append(p)
cnt = 0
while Q:
  temp = Q.popleft()
  x,y = temp
  s = [x-1,y-2]
  t = [x-2,y-1]
  if x-1>=2 or y-2>=2:
    Q.append(s)
  if x-2>=2 or y-1>=2:
    Q.append(t)
  if s==[0,0] or t==[0,0]:
    cnt += 1
print(cnt)

Fixed submission:
x,y = map(int,input().split())
mod = 10**9+7
def comb(a,b):
  comb = 1
  chld = 1
  for i in range(b):
    comb = comb*(a-i)%mod
    chld = chld*(b-i)%mod
  return (comb*pow(chld,mod-2,mod))%mod
if (x+y)%3!=0:
  print(0)
else:
  nm = (x+y)//3
  n = y-nm
  m = x-nm
  if n>=0 and m>=0:
    print(comb(n+m,m))
  else:
    print(0)
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().spilit())
h = list(map(int,input().split()))
ans = 0
for a in h:
  if a>=k:
    ans += 1
print(ans)

Fixed submission:
n,k = map(int,input().split())
h = list(map(int,input().split()))
ans = 0
for a in h:
  if a>=k:
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
s = int(input())
l = ['Sunny', 'Cloudy', 'Rainy', 'Sunny']
print(l[l.index(s)+1])

Fixed submission:
s = input()
l = ['Sunny', 'Cloudy', 'Rainy', 'Sunny']
print(l[l.index(s)+1])
Buggy python submission (verdict: Runtime Error):
import heapq as hq
n,m=input().split()
hq.heapify(a:=[-int(x) for x in input().split()])
for i in range(int(m)):hq.heappush(a,-(-hq.heappop(a)//2))
print(-sum(a))

Fixed submission:
n,k,q = map(int,input().split())
pts = [0]*(n+1)
for _ in range(q):
  a = int(input())
  pts[a] += 1
ans = [k+a-q for a in pts]
for v in ans[1:]:
  print('Yes' if v>0 else 'No')
Buggy python submission (verdict: Runtime Error):
import heapq as hq
m=input()
hq.heapify(a:=[-int(x) for x in input().split()])
for i in range(int(m[2])):hq.heappush(a,-(v:=-hq.heappop(a)//2))
print(-sum(a))

Fixed submission:
import heapq
n,m = map(int,input().split())
a = list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(a)
for i in range(m):
  maxv = heapq.heappop(a)*(-1)
  heapq.heappush(a,(maxv//2)*(-1))
print(sum(a)*(-1))

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(m):
  v = max(a)//2
  a[a.index(max(a))] = v
print(sum(a))

Fixed submission:
import heapq
n,m = map(int,input().split())
a = list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(a)
for i in range(m):
  maxv = heapq.heappop(a)*(-1)
  heapq.heappush(a,(maxv//2)*(-1))
print(sum(a)*(-1))
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
dp = [0]*(n+1)
dp[1],dp[2] = 1,1

for _ in range(m):
  a = int(input())
  dp[a] = -1

for i in range(1,n-1):
  if dp[i+2]==-1:
    continue
  if dp[i]==-1 and dp[i+1]==-1:
    dp[i+2] = -1
  elif dp[i]==-1:
    dp[i+2] = dp[i+1]
  elif dp[i+1]==-1:
    dp[i+2] = dp[i]
  else:
    dp[i+2] = dp[i] + dp[i+1]
    
print(dp[n]%(10**9+7) if dp[n]!=-1 else 0)

Fixed submission:
n,m = map(int,input().split())
def Fib(n):
  seq = []
  a,b = 0,1
  for i in range(1,n+10):
    if i == 1:
      seq.append(0)
    elif i == 2:
      seq.append(1)
    else:
      a, b = b, a + b
      seq.append(b)
  return seq
table = Fib(n)
temp = -1
route = 1
mod = 10**9+7
for _ in range(m):
  a = int(input())
  dif = a-temp-1
  temp = a
  route = route*table[dif]%mod
print(route*table[n-temp]%mod)

Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
def Fib(n):
  seq = []
  a,b = 0,1
  for i in range(1,n+1):
    if i == 1:
      seq.append(0)
    elif i == 2:
      seq.append(1)
    else:
      a, b = b, a + b
      seq.append(b)
  return seq
table = Fib(n)
temp = -1
route = 1
mod = 10**9+7
for _ in range(m):
  a = int(input())
  dif = a-temp-1
  temp = a
  route = route*table[dif]%mod
print(route*table[n-temp]%mod)  

Fixed submission:
n,m = map(int,input().split())
def Fib(n):
  seq = []
  a,b = 0,1
  for i in range(1,n+10):
    if i == 1:
      seq.append(0)
    elif i == 2:
      seq.append(1)
    else:
      a, b = b, a + b
      seq.append(b)
  return seq
table = Fib(n)
temp = -1
route = 1
mod = 10**9+7
for _ in range(m):
  a = int(input())
  dif = a-temp-1
  temp = a
  route = route*table[dif]%mod
print(route*table[n-temp]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = map(int,input().split())
ans = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    p = N-(r*R+g*G)
    if p%B==0 and p>=0:
      ans += 1
print(ans)

Fixed submission:
R,G,B,N = map(int,input().split())
ans = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    p = N-(r*R+g*G)
    if p%B==0 and p>=0:
      ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float('inf')]*n
dp[0] = 0
for i in range(1,n):
  for j in range(max(0,i-k),i):
    dp[i] = min(dp[i],dp[j]+abs(h[j]-h[i]))
print(dp[-1])

Fixed submission:
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float('inf')]*n
dp[0] = 0
for i in range(1,n):
  for j in range(max(0,i-k),i):
    dp[i] = min(dp[i],dp[j]+abs(h[j]-h[i]))
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
N=int(input())
T,A=map(int, input().split())
list=list(map(int, input().split()))
l_b=[]
d=0
for i in range(N):
  d=A-(T-list[i]*0.006)
  if d<0:
    d=-d
  l_b.append(d)
print(l_b.index(min(l_b))+1


Fixed submission:
N=int(input())
T,A=map(int, input().split())
list=list(map(int, input().split()))
l_b=[]
d=0
for i in range(N):
  d=A-(T-list[i]*0.006)
  if d<0:
    d=-d
  l_b.append(d)
print(l_b.index(min(l_b))+1)
Buggy python submission (verdict: Runtime Error):
m=int((input().count("o"))
print(str(700+m*100))

Fixed submission:
m=input().count("o")
print(700+m*100)

Buggy python submission (verdict: Runtime Error):
m= (input().count('o')
print(str(700+m*100))


Fixed submission:
m=input().count("o")
print(700+m*100)

Buggy python submission (verdict: Runtime Error):
m= int((input=().count('o'))
print(700+m*100)


Fixed submission:
m=input().count("o")
print(700+m*100)

Buggy python submission (verdict: Runtime Error):
m=int((input=().count('o'))
print(str(700+m*100))


Fixed submission:
m=input().count("o")
print(700+m*100)

Buggy python submission (verdict: Runtime Error):
m= (input=().count('o')
print(str(700+m*100))

Fixed submission:
m=input().count("o")
print(700+m*100)
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
m=[int(input() for i in range(N)]
print(N+(X-sum(m))//min(m))       

Fixed submission:
N, X = map(int, input().split())
m=[int(input()) for i in range(N)]
print(N+(X-sum(m))//min(m))
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=list(map(int, input().split()))
a.sort()[::-1]
Alice=0
Bob=0
for i in range(N):
  if i%2==0:
    Alice += a[i]
  else:
    Bob += a[i]
print(Alice-Bob)


Fixed submission:
N=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
Alice=0
Bob=0
for i in range(N):
  if i%2==0:
    Alice += a[i]
  else:
    Bob += a[i]
print(Alice-Bob)

Buggy python submission (verdict: Runtime Error):
N=int(input())
a=list(map(int, input().split()))
a.sort()[::1]
Alice=0
Bob=0
for i in range(N):
  if i%2==0:
    Alice += a[i]
  else:
    Bob += a[i]
print(Alice-Bob)


Fixed submission:
N=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
Alice=0
Bob=0
for i in range(N):
  if i%2==0:
    Alice += a[i]
  else:
    Bob += a[i]
print(Alice-Bob)
Buggy python submission (verdict: Runtime Error):
l = [list(map(int, input().split())) for i in range(3)]
d = [None]*3
for i in range(3):
  d[i] = [l[i] - l[i+1] for i in range(2)]
print('Yes' if all(d[i] == d[i+1] for i in range(2)) else 'No')


Fixed submission:
d = [None]*3
for i in range(3):
  c = list(map(int, input().split()))
  d[i] = [c[i] - c[i+1] for i in range(2)]
print('Yes' if all(d[i] == d[i+1] for i in range(2)) else 'No')

Buggy python submission (verdict: Runtime Error):
l = [list(map(int, input().split())) for i in range(3)]
d = [None]*3
d[i] = [l[i] - l[i+1] for i in range(2)]
print('Yes' if all(d[i] == d[i+1] for i in range(2)) else 'No')

Fixed submission:
d = [None]*3
for i in range(3):
  c = list(map(int, input().split()))
  d[i] = [c[i] - c[i+1] for i in range(2)]
print('Yes' if all(d[i] == d[i+1] for i in range(2)) else 'No')
Buggy python submission (verdict: Runtime Error):
N = int(input())
plan = [0] + list(map(int, input().split())) for i in range(N)
f = True
for i in range(N):
    time = plan[i+1][0]-plan[i][0]
    dist = abs(plan[i+1][1]-plan[i][1])+abs(plan[i+1][2]-plan[i][2])
    if dist>time or dist%2 != time%2:
        f = False    
print('Yes' if f else 'No')

Fixed submission:
N = int(input())
t,x,y = 0,0,0
f = True
for i in range(N):
    ti,xi,yi = map(int, input().split())
    p=ti-t
    d=abs(xi-x)+abs(yi-y)
    if p<d or p%2 != d%2:
        f = False
        break 
    t,x,y = ti,xi,yi
print('Yes' if f else 'No')

Buggy python submission (verdict: Runtime Error):
N = int(input())
t,x,y = 0,0,0
f = True
for i in range(N):
    ti,xi,yi = map(int, input()split())
    p=ti-t
    d=abs(xi-x)+abs(yi-y)
    if p<d or p%2 != d%2:
        f = False
        break 
    t,x,y = ti,xi,yi
print('Yes' if f else 'No')

Fixed submission:
N = int(input())
t,x,y = 0,0,0
f = True
for i in range(N):
    ti,xi,yi = map(int, input().split())
    p=ti-t
    d=abs(xi-x)+abs(yi-y)
    if p<d or p%2 != d%2:
        f = False
        break 
    t,x,y = ti,xi,yi
print('Yes' if f else 'No')
Buggy python submission (verdict: Runtime Error):
print(input().replace('2017', '2018')

Fixed submission:
print(input().replace('2017', '2018'))
Buggy python submission (verdict: Runtime Error):
s=input()
print(s[0]+str(len(s)-2)+s[len(s-2)])


Fixed submission:
s=input()
print(s[0]+str(len(s)-2)+s[len(s)-1])

Buggy python submission (verdict: Runtime Error):
s=input()
print(s[0]+str(len(s)-2)+s[len(s)])

Fixed submission:
s=input()
print(s[0]+str(len(s)-2)+s[len(s)-1])
Buggy python submission (verdict: Time Limit Exceeded):
words = ['dream', 'dreamer', 'erase', 'eraser']
S = input()
T = []
for a in S[::-1]:
  T += a
  for s in words:
    if ''.join(T)[::-1] == s:
      T = []
print('YES' if T == [] else 'NO')

Fixed submission:
words = ['maerd', 'remaerd', 'esare', 'resare']
S = input()
T = ''
for a in S[::-1]:
  T += a
  for s in words:
    if T == s:
      T = ''
print('YES' if T == '' else 'NO')
Buggy python submission (verdict: Runtime Error):
value_index = dict()
 n, x, m = map(int, input().split())
 a = [0] * m
 s = [0] * (m + 1)
 for i in range(m):
     a[i] = x % m
     s[i+1] = s[i] + a[i]
     if i == n - 1:
         print(s[i+1])
         quit()
     if a[i] in value_index:
         break
     value_index[a[i]] = i
     x = x * x % m 
 l = value_index[a[i]]
 r = i 
 loop_sum = s[r] - s[l]
 loop_n = (n - l) // (r - l)
 rem = (n - l) % (r - l) 
 ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
 print(ans)

Fixed submission:

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 2)

for i in range(m + 1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)

Buggy python submission (verdict: Runtime Error):

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 1)

for i in range(m+1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)


Fixed submission:

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 2)

for i in range(m + 1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)

Buggy python submission (verdict: Runtime Error):

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * m
s = [0] * (m + 1)

for i in range(m+1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)
ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)


Fixed submission:

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 2)

for i in range(m + 1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)
Buggy python submission (verdict: Runtime Error):
 n = int(input())
 a = list(map(int, input().split()))
 stock = 0
 rest  = 0
 value = 1000
 for i in range(1, n + 1):
    value = max(value, stock * a[i - 1] + rest)
    stock = value // a[i - 1]
    rest = value % a[i - 1]
 print(value)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

stock_dp = [[0, 0] for _ in range(n+1)]
value_dp = [0] * (n + 1)

value_dp[0] = 1000
for i in range(1, n + 1):
    x = value_dp[i - 1]
    y = stock_dp[i - 1][0] + stock_dp[i - 1][1] * a[i - 1]
    if x > y:
        value_dp[i] = x
    else:
        value_dp[i] = y
    x = value_dp[i - 1] // a[i - 1] 
    y = stock_dp[i - 1][0] // a[i - 1] + stock_dp[i - 1][1]
    rx = value_dp[i - 1] % a[i - 1]
    ry = stock_dp[i - 1][0] % a[i - 1]
    if x > y:
        stock_dp[i][0] = rx
        stock_dp[i][1] = x
    elif x < y:
        stock_dp[i][0] = ry
        stock_dp[i][1] = y
    else:
        stock_dp[i][0] = max(rx, ry)
        stock_dp[i][1] = x
print(value_dp[n])