Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03164 (python)

Fixed submission:
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
V = sum(v)
dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j >= v[i]: dp[i+1][j] = min(dp[i][j] ,dp[i][j-v[i]]+w[i])
        else: dp[i+1][j] = dp[i][j]
ans = 0
for i in range(V+1):
    if dp[N][i]<=W: ans=i
print(ans)

Buggy submission (verdict: Runtime Error):
IN = iter(Input.split('\n')).__next__
def input():
    return IN()

# 入力
N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
V = sum(v)
dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(V+1):
        if j >= v[i]: dp[i+1][j] = dp[i][j-v[i]]+w[i]
        else: dp[i+1][j] = dp[i][j]
ans = 0
for i in range(V+1):
    if dp[N][i]<=W: ans=i
print(ans)

Buggy submission (verdict: Runtime Error):
n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    w_, v_ = wv[i]
    for j in range(w+1):
        if j < w_:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j-w_]+v_, dp[i][j])
print(dp[n][w])
Problem p03436 (python)

Fixed submission:
from collections import deque
h, w = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())

ans = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == ".": ans+=1

d = [[-1]*w for _ in range(h)]
d[0][0] = 1
que = deque([[0, 0]])
while que:
    x, y = que.popleft()
    for i, j in [[1,0],[0,1],[-1,0],[0,-1]]:
        nx, ny = x+i, y+j
        if 0<=nx<w and 0<=ny<h and c[ny][nx]=="." and d[ny][nx]==-1:
            d[ny][nx] = d[y][x]+1
            que.append([nx, ny])
if d[h-1][w-1] == -1:
    print(-1)
else:
    print(ans-d[h-1][w-1])

Buggy submission (verdict: Runtime Error):
IN = iter(Input.split('\n')).__next__
def input():
    return IN()

# 入力
from collections import deque
h, w = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())

ans = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == ".": ans+=1

d = [[-1]*w for _ in range(h)]
d[0][0] = 1
que = deque([[0, 0]])
while que:
    x, y = que.popleft()
    for i, j in [[1,0],[0,1],[-1,0],[0,-1]]:
        nx, ny = x+i, y+j
        if 0<=nx<w and 0<=ny<h and c[ny][nx]=="." and d[ny][nx]==-1:
            d[ny][nx] = d[y][x]+1
            que.append([nx, ny])
if d[h-1][w-1] == -1:
    print(-1)
else:
    print(ans-d[h-1][w-1])
Problem p03476 (python)

Fixed submission:
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > 316: break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A: P.append(a)
    return P
l = eratosthenes(10**5)
ans = [0]*(10**5+1)
d = [0]*(10**5+1)
for i in l: d[i] += 1
for i in range(2, 10**5+1):
    ans[i] += ans[i-1]
    if i%2==1 and d[i] and d[(i+1)//2]: ans[i] += 1
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Buggy submission (verdict: Runtime Error):
def eratosthenes(limit):
    import math
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    while True:
        prime = min(A)
        if prime > math.sqrt(limit): break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A: P.append(a)
    return P
L = eratosthenes(10**5)
ans = [0]*(10**5+1)
d = [0]*(10**5+1)
for i in l: d[i] += 1
for i in range(2, 10**5+1):
    ans[i] += ans[i-1]
    if i%2==1 and d[(i+1)//2]: ans[i] += 1
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])
Problem p03557 (python)

Fixed submission:
#20　AtCoder Beginner Contest 077 C - Snuke Festival
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
c.sort()
ans = 0
for i in b:
    ans+= (bisect.bisect_right(a, i-1))*(n-bisect.bisect_left(c, i+1))
print(ans)

Buggy submission (verdict: Runtime Error):
#20　AtCoder Beginner Contest 077 C - Snuke Festival
import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
c.sort()
ans = 0
for i in b:
    if i <= a[n-1]: lena=len(a[:bisect.bisect_left(a, i)])
    else: lena=n
    if i+1<= c[n-1]: lenc=len(a[bisect.bisect_left(c, i+1):])
    ans += lena*lenc
print(ans)
Problem p02612 (python)

Fixed submission:
n=int(input())
print((1000-n%1000)%1000)

Buggy submission (verdict: Runtime Error):
=int(input())
print((1000-n%1000)%1000)
Problem p02618 (python)

Fixed submission:
import random
D=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split())) for i in [0]*D]
for i in range(D):
    print(random.randint(1,26))

Buggy submission (verdict: Runtime Error):
D=int(input())
c=list(map(int,input().split()))
s=[list(map(int,input().split())) for i in [0]*D]
a=sorted(c)
for i in a:
    print(c.index(a))
Problem p02664 (python)

Fixed submission:
s=list(input())
for i in range(len(s)):
    if s[i]=="?":
        s[i]="D"
print("".join(s))

Buggy submission (verdict: Runtime Error):
s=list(input())
if s[0]=="?":
    if s[1]=="D":
        s[0]="P"
    else:
        s[0]="D"
for i in range(-1,len(s)-2):
    if s[i+1]!="?":
        continue
    if i+2<len(s) and s[i+2]=="D":
        s[i+1]="P"
    else:
        s[i+1]="D"
print("".join(s))

Buggy submission (verdict: Runtime Error):
s=list(input())
if s[0]=="?":
    if s[1]=="D":
        s[0]="P"
    else:
        s[0]="D"
for i in range(len(s)-1):
    if s[i+1]!="?":
        continue
    if i+2<len(s) and s[i+2]=="D":
        s[i+1]="P"
    else:
        s[i+1]="D"
print("".join(s))
Problem p02687 (python)

Fixed submission:
s=input()[1]
print("ABC")if s=="R" else print("ARC")

Buggy submission (verdict: Runtime Error):
]
print("ABC")if s=="R" else print("ARC")
Problem p02741 (python)

Fixed submission:
s="1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"
n=int(input())
print((s.split(", "))[n-1])

Buggy submission (verdict: Runtime Error):
print(("1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51".split(", "))[int(input())])

Buggy submission (verdict: Runtime Error):
print("1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51".split(", ")[int(input())])
Problem p02588 (python)

Fixed submission:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
d = dd(int)
a = []
for i in range(N):
  t = input()[: -1]
  x, y = "", ""
  z = 0
  if "." in t:
    x, y = t.split(".")
    y = y.ljust(9, "0")
    z = int(x) * 10 ** 9 + int(y)
  else: z = int(t) * 10 ** 9
  zz = 1
  while z % 2 == 0:
    z //= 2
    zz *= 2
  while z % 5 == 0:
    z //= 5
    zz *= 5
  d[zz] += 1
  a.append(zz)
ks = sorted(d.keys())
table = dd(int)
for k in ks:
  for kk in ks:
    z = k * kk
    c = 0
    while z % 10 == 0:
      z //= 10
      c += 1
    table[k * kk] = c >= 18
res = 0
for x in ks:
  cc = N
  for k in ks:
    z = x * k
    if table[z]:
      cc -= x == k
      continue
    cc -= d[k]
  res += cc * d[x]
print(res // 2)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N = int(input())
s = set()
base = 37
mod = 1 << 36 - 1

a = [input()[: -1] for _ in range(N)]
a.sort(key = len)
res = 0
for S in a:
  l = len(S)
  t = 0
  pw = [1] * (l + 1)
  h = [0] * (l + 1)
  v1 = 0
  v2 = 1
  for i in range(l):
    h[i + 1] = v1 = (v1 * base + ord(S[i])) % mod
    pw[i + 1] = v2 = v2 * base % mod
  for i in range(l):
    t |= 1 << (ord(S[i]) - ord("a"))
    for j in range(26):
      if t & (1 << j):
        rc = (h[l] - h[i + 1] * pw[l - (i + 1)]) % mod
        res += rc + j * mod in s
  rc = (h[l] - h[1] * pw[l - 1]) % mod
  s.add(rc + (ord(S[0]) - ord("a")) * mod)
print(res)
Problem p02609 (python)

Fixed submission:
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, list(input())[: -1]))
pp = sum(S)
Xp = 0
Xm = 0
S.reverse()
for i in range(N):
  Xp += pow(2, i, pp + 1) * S[i]
  Xp %= pp + 1
  Xm += pow(2, i, max(1, pp - 1)) * S[i]
  Xm %= max(1, pp - 1)
#print(Xp, Xm)
rres = [0] * N
for i in range(N):
  res = 1
  if S[i]:
    if pp == 1: res = 0
    else:
      X = (Xm - pow(2, i, max(1, pp - 1))) % max(1, pp - 1)
      while X:
        c = bin(X).count("1")
        X %= c
        res += 1
  else:
    X = (Xp + pow(2, i, pp + 1)) % (pp + 1)
    while X:
      c = bin(X).count("1")
      X %= c
      res += 1
  rres[i] = res
rres.reverse()
for r in rres: print(r)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, list(input())[: -1]))
pp = sum(S)
Xp = 0
Xm = 0
S.reverse()
for i in range(N):
  Xp += pow(2, i, pp + 1) * S[i]
  Xp %= pp + 1
  Xm += pow(2, i, pp - 1) * S[i]
  Xm %= pp - 1
#print(Xp, Xm)
rres = [0] * N
for i in range(N):
  res = 1
  if S[i]:
    X = (Xm - pow(2, i, pp - 1)) % (pp - 1)
    while X:
      c = bin(X).count("1")
      X %= c
      res += 1
  else:
    X = (Xp + pow(2, i, pp + 1)) % (pp + 1)
    while X:
      c = bin(X).count("1")
      X %= c
      res += 1
  rres[i] = res
rres.reverse()
for r in rres: print(r)
Problem p02632 (python)

Fixed submission:
import sys
input = sys.stdin.readline
K = int(input())
S = list(input())[: -1]
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
###
f = Factorial(10 ** 6 * 3, mod)
res = 0
for i in range(K + 1):
  #i ko migi soto
  t = f.combi(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, mod) % mod
  t = t * pow(26, i, mod) % mod
  res += t
  res %= mod
print(res)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
K = int(input())
S = list(input())[: -1]
mod = 10 ** 9 + 7

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
###
f = Factorial(10 ** 5 * 3, mod)
res = 0
for i in range(K + 1):
  #i ko migi soto
  t = f.combi(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, mod) % mod
  t = t * pow(26, i, mod) % mod
  res += t
  res %= mod
print(res)
Problem p02686 (python)

Fixed submission:
import sys
input = sys.stdin.readline
N = int(input())
css = [0] * N
mns = [0] * N
t = [x for x in range(N)]
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": css[x] += 1
    if S[i] == ")":
      css[x] -= 1
      mns[x] = min(mns[x], css[x])
if sum(css):
  print("No")
  exit(0)
t.sort(key = lambda x: -10 ** 7 if mns[x] == 0 else -10 ** 7 - mns[x] if css[x] >= 0 else mns[x] - css[x])
l = 0
for i in t:
  if l + mns[i] < 0:
    print("No")
    exit(0)
  l += css[i]
print("Yes")

Buggy submission (verdict: Runtime Error):
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l |= 1
  if rs[i] == 0 and (ls[i] > 0): l |= 2
if l < 3:
  print("No")
  exit(0)
l = 0
c = 0
cc = 0
h = []
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  l += -hpop(h)
  cc += 1
  if l < 0:
    print("No")
    exit(0)
print("Yes")
Problem p02697 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, M = map(int, input().split())
res = []

def solve(l, r):
  global res
  if r <= l: return
  res.append((l, r))
  solve(l + 1, r - 1)


solve(1, M + 1)
solve(M + 2, M * 2 + 1)
for r in res: print(*r)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
res = []

def solve(l, r):
  global res
  if r <= l: return
  res.append((l, r))
  solve(l + 1, r - 1)


solve(1, M + 1)
solve(M + 2, M * 2 + 1)
for r in res: print(*r)
Problem p02698 (python)

Fixed submission:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 10
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 6
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 6
lis = [inf] * (N + 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)
Problem p02727 (python)

Fixed submission:
import sys
input = sys.stdin.readline
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort()
q.sort()
r.sort(reverse = True)
t = []
for _ in range(X): t.append(p.pop())
for _ in range(Y): t.append(q.pop())
t.sort()
for i in range(min(C, X + Y)):
  if t[i] < r[i]: t[i] = r[i]
print(sum(t))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort()
q.sort()
r.sort(reverse = True)
t = []
for _ in range(X): t.append(p.pop())
for _ in range(Y): t.append(q.pop())
t.sort()
for i in range(C):
  if t[i] < r[i]: t[i] = r[i]
print(sum(t))
Problem p02798 (python)

Fixed submission:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append(b[j])
    else:
      x.append(a[j])
  sx = sorted(x)
  odd = [0] * 51
  even = [0] * 51
  for j in range(N):
    odd[sx[j]] += j % 2
    even[sx[j]] += (j % 2 == 0)
  for j in range(N):
    if i & (1 << j):
      if j % 2: even[x[j]] -= 1
      else: odd[x[j]] -= 1
    else:
      if j % 2: odd[x[j]] -= 1
      else: even[x[j]] -= 1
  return min(min(odd), min(even)) >= 0
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(N)
  t = 0
  odd = []
  even = []
  for j in range(N):
    if i & (1 << j):
      if j % 2: even.append((b[j], j))
      else: odd.append((b[j], j))
    else:
      if j % 2: odd.append((a[j], j))
      else: even.append((a[j], j))
  #print(t, i)
  odd.sort(key = lambda x: x[0])
  even.sort(key = lambda x: x[0])
  ind = []
  #print(t, i)
  for j in range(N):
    if j % 2: ind.append(odd[j // 2][1])
    else: ind.append(even[j // 2][1])
  #print(t, i, ind)
  for x in ind:
    t += fwk.get(x, N)
    fwk.add(x + 1, 1)
  res = min(res, t)
  #print(t, i)
if res == float("inf"): print(-1)
else: print(res)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
print(-1)import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = float("inf")
for i in range(pow(2, N)):
  x = []
  l = []
  c = 0
  for j in range(N):
    if i & (1 << j):
      c += 1
      x.append((b[j], j))
    else:
      x.append((a[j], j))
  if c % 2: continue
  y = sorted(x, key = lambda x: x[0])
  z = -1
  #print(y, i)
  for j in range(N):
    t = abs(j - y[j][1])
    #print(i & (1 << y[j][1]) > 0, t)
    if i & (1 << j) > 0:
      if t % 2:
        z = max(z, t)
      else:
        z = -1
        break
    else:
      if t % 2 == 0:
        z = max(z, t)
      else:
        z = -1
        break
  if z == -1: continue
  z = 0
  for j in range(N):
    for k in range(j, len(x)):
      if x[k][0] == y[j][0]:
        x.pop(k)
        x.insert(0, (0, 0))
        z += k - j
        break
  res = min(res, z)

  
if res != float("inf"): print(res)
else: print(-1)
Problem p02840 (python)

Fixed submission:
import sys
from fractions import gcd
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, X, D = map(int, input().split())
if D == 0:
  if X == 0: print(1)
  else: print(N + 1)
  exit(0)
a = dd(list)
a[0].append((0, 0))
d = abs(D) // abs(gcd(X, D))
#print(d)

for i in range(1, N + 1):
  l = X * i + D * i * (i - 1) // 2
  r = X * i + D * (i * N - i * (i + 1) // 2)
  if r < l: l, r = r, l
  a[i % d].append((l, r))

res = 0
for x in a.keys():
  s = set()
  for l, r in a[x]:
    s.add(l)
    s.add(r)
    s.add(r + 1)
  xs = sorted(s)
  table = [0] * (len(xs) + 1)
  for l, r in a[x]:
    ll = bl(xs, l)
    rr = bl(xs, r + 1)
    table[ll] += 1
    table[rr] += -1
  for i in range(len(xs)): table[i + 1] += table[i]
  l = xs[0]
  for i in range(len(xs)):
    if table[i]:
      if l == -1: l = xs[i]
      continue
    res += (xs[i - 1] - l) // abs(D) + 1
    l = -1

print(res)

Buggy submission (verdict: Runtime Error):
import sys
from fractions import gcd
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, X, D = map(int, input().split())
if D == 0:
  if X == 0: print(1)
  else: print(N + 1)
  exit(0)
a = dd(list)
a[0].append((0, 0))
d = abs(D) // abs(gcd(X, D))
#print(d)

for i in range(1, N + 1):
  l = X * i + D * i * (i - 1) // 2
  r = X * i + D * (i * N - i * (i + 1) // 2)
  if r < l: l, r = r, l
  a[i % d].append((l, r))

res = 0
for x in range(d):
  s = set()
  for l, r in a[x]:
    s.add(l)
    s.add(r)
    s.add(r + 1)
  xs = sorted(s)
  table = [0] * (len(xs) + 1)
  for l, r in a[x]:
    ll = bl(xs, l)
    rr = bl(xs, r + 1)
    table[ll] += 1
    table[rr] += -1
  for i in range(len(xs)): table[i + 1] += table[i]
  l = xs[0]
  for i in range(len(xs)):
    if table[i]:
      if l == -1: l = xs[i]
      continue
    res += (xs[i - 1] - l) // abs(D) + 1
    l = -1
    #print(res, xs[i - 1], l)
  
  #print(table, xs)
#print(a)
print(res)

Buggy submission (verdict: Runtime Error):
import sys
from fractions import gcd
input = sys.stdin.readline
N, X, D = map(int, input().split())
a = [(0, 0)]
for i in range(1, N + 1):
  l = X * i + D * i * (i - 1) // 2
  r = X * i + D * (i * N - i * (i + 1) // 2)
  if r < l: l, r = r, l
  a.append((l, r))
a.sort()
#print(a)
d = abs(D) // abs(gcd(X, D))
#print(d)
res = 0
for i in range(N + 1):
  l, r = a[i]
  t = 1 + (r - l) // abs(D)
  if i + d <= N:
    if r >= a[i + d][0]: t -= 1 + (r - a[i + d][0]) // abs(D)
  if t > 0: res += t
  #print(t)
print(res)
Problem p02850 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for i in range(N - 1):
  a, b = tuple(map(int, input().split()))
  e[a].append((b, i))
  e[b].append((a, i))
res = [0] * (N - 1)
vis = set()
def dfs(x):
  global vis
  global res
  viss = set()
  svis = set()
  t = 1
  for y, i in e[x]:
    if i in vis: viss.add(res[i])
  #print(x, viss)
  for y, i in e[x]:
    #print(x, y, t)
    while t in viss:
      t += 1
    if i in vis:
      continue
    #print(x, y, t)
    svis.add(y)
    vis.add(i)
    res[i] = t
    t += 1
  for y in svis:
    dfs(y)
  #print(res)
dfs(1)
print(max(res))
for r in res: print(r)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for i in range(N - 1):
  u, v = map(int, input().split())
  e[u].append((v, i))
  e[v].append((u, i))
res = [0] * (N - 1)
def dfs(x):
  global res
  c = 1
  vis = set()
  for y, i in e[x]: vis.add(res[i])
  #print(x, vis)
  for y, i in e[x]:
    if res[i] > 0: continue
    while c in vis: c += 1
    #print(x, c)
    res[i] = c
    vis.add(c)
    dfs(y)
dfs(1)
print(max(res))
for r in res: print(r)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for i in range(N - 1):
  a, b = tuple(map(int, input().split()))
  e[a].append((b, i))
  e[b].append((a, i))
res = [0] * (N - 1)
vis = set()
def dfs(x):
  global vis
  global res
  viss = set()
  t = 1
  for y, i in e[x]:
    if i in vis: viss.add(res[i])
  for y, i in e[x]:
    if i in vis:
      while t in viss:
        t += 1
      continue
    vis.add(i)
    res[i] = t
    t += 1
    dfs(y)
dfs(1)
print(max(res))
for r in res: print(r)