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

Fixed submission:
import itertools

N, K = map(int,input().split())
D = list(map(int,input().split()))
N = str(N)
d = []
d_min = 10
for i in range(10):
    if i in D:
        continue
    else:
        if i != 0:
            d_min = min(d_min, i)
        d.append(str(i))
if '0' in d:
    ans = str(d_min) + '0' * len(N)
else:
    ans = str(d_min) * (len(N) + 1)
ans = int(ans)
for s in itertools.product(d, repeat=len(N)):
    s = ''.join(s)
    s = int(s)
    if s >= int(N):
        ans = min(ans, s)
print(ans)

Buggy submission (verdict: Runtime Error):
import itertools

N, K = map(int,input().split())
D = list(map(int,input().split()))
N = str(N)
d = []
d_min = 10
for i in range(10):
    if i in D:
        continue
    else:
        if i != 0:
            d_min = min(d_min, i)
        d.append(str(i))
if '0' in d:
    ans = str(d_min) + '0' * len(N)
else:
    ans = str(d_min) * len(N+1)
ans = int(ans)
for s in itertools.product(d, repeat=len(N)):
    s = ''.join(s)
    s = int(s)
    if s >= int(N):
        ans = min(ans, s)
print(ans)
Problem p02556 (python)

Fixed submission:

N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]

ans = 0

def measure(originX,originY):
    dist = []
    for X,Y in XY:
        dist.append(abs(X-originX)+abs(Y-originY))
    return max(dist)-min(dist)

originX = 0
originY = 0
ans = max(ans,measure(originX,originY))

originX = 10**9
originY = 0
ans = max(ans,measure(originX,originY))

originX = 0
originY = 10**9
ans = max(ans,measure(originX,originY))

originX = 10**9
originY = 10**9
ans = max(ans,measure(originX,originY))

print(ans)

Buggy submission (verdict: Runtime Error):
import statistics

N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]

sumX = []
sumY = []
for x,y in XY:
    sumX.append(x)
    sumY.append(y)
avaX = statistics.median(sumX)
avaY = statistics.median(sumY)

zone1 = []
zone2 = []
zone3 = []
zone4 = []
for x,y in XY:
    if x < avaX and y >= avaY:
        zone1.append((x,y,abs(x-avaX)+abs(y-avaY)))
    elif x < avaX and y < avaY:
        zone4.append((x,y,abs(x-avaX)+abs(y-avaY)))
    elif x >= avaX and y >= avaY:
        zone2.append((x,y,abs(x-avaX)+abs(y-avaY)))
    elif x >= avaX and y < avaY:
        zone3.append((x,y,abs(x-avaX)+abs(y-avaY)))

zone1.sort()
zone2.sort()
zone3.sort()
zone4.sort()

ans = 0
ans = max(ans,zone1[-1][2]+zone3[-1][2])
ans = max(ans,zone2[-1][2]+zone4[-1][2])
print(ans)
Problem p02574 (python)

Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
countA = Counter(A)

#pairwiseかどうかを調べる
memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0
for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in countA:
            if countA[i] >= 2:
                break
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in countA:
                if countA[j] >= 2:
                    break
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
else:
    print("pairwise coprime")
    exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Buggy submission (verdict: Runtime Error):
from math import gcd

"""
pairwise coprimeであるための条件は、全てのAに関して素因数に重複がないことである。
したがって、各Aに関して素因数分解を行う⇒各数の素因数の種類数をカウントし総和する。⇒全体の素因数の種類数をカウントし、先ほどの総和と比較する。
"""
N = int(input())
A = list(map(int,input().split()))
primes = set()
cnt = 0
for i in range(N):
    a = A[i]
    d = 2
    ceil = int(a**0.5)+1
    for d in range(2,ceil)
        if a % d == 0:
            cnt += 1
            primes.add(d)
            for _ in range(100):
                if a % d==0:
                    a //= d
                else:
                    break
        d += 1

if cnt == len(primes):
    print('pairwise coprime')
    exit()
g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print('setwise coprime')
else:
    print('not coprime')

Buggy submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
setA = set(A)

#pairwiseかどうかを調べる
memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0
for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in setA:
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in setA:
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
elif len(setA) == len(A):
    print("pairwise coprime")
    exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")
Problem p02588 (python)

Fixed submission:
def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]
#dp[i][j] -> 2の素因数がi以上,5の素因数がj以上の数字の数

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)

Buggy submission (verdict: Runtime Error):
"""
小数の状態だと処理しづらいので、与えられた数を全て10**9倍して小数を確実になくした上で
問題文を下記のように言い換える。
「積が10**18の倍数になるような数の組み合わせの数がいくつあるか」
数Aiがあり、Aiの2の素因数の数がn, 5の素因数の数がmのとき、
数Ai自体ですでにmin(n,m)個の0の数を持っている。この場合、のこり必要な0の数はx = 18-min(n,m)個である。
ここで、n == mの場合：
Aiの相方は少なくとも2,5の素因数をそれぞれx個以上持っていなくてはならない。
n > mの場合：
Aiの相方は少なくとも2の素因数をx-(n-m)個、5の素因数をx個持っていなくてはいけない。

m > nの場合：
Aiの相方は少なくとも2の素因数をx個以上、5の素因数をx-(m-n)個以上持っていなくてはならない。
"""
N = int(input())
dp = [[0]*(19) for _ in range(19)]
ans = 0
for _ in range(N):
    a = float(input())
    a *= 10**9
    two = 0
    while a % 2 == 0:
        a //= 2
        two += 1
    five = 0
    while a % 5 == 0:
        a //= 5
        five += 1

    ans += dp[18-two][18-five]
    for i in range(two+1):
        for j in range(five+1):
            dp[i][j] += 1
print(ans)
Problem p02694 (python)

Fixed submission:
import math
X = int(input())
d = 100
year = 0
while True:
    year += 1
    if d+math.floor(d*0.01) >= X:
        print(year)
        exit()
    else:
        d += math.floor(d*0.01)

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
Nlist = []
for i in range(1,N+1):
    Nlist.append(i)
count = 0
for i in range(N):
    count += 1
    if count>M:
        break
    print(Nlist[i],Nlist[-(i+1)])

Buggy submission (verdict: Runtime Error):
N,M = map(int,input().split())
#Dストックを昇順で生成する。
Dstock = {}
Nstock = {}
for i in range(1,N):
    Dstock[i]=""
    Nstock[i]=""
Nstock[N] = ""

count = 0
while Nstock and count<M:
    count += 1
    for i in Dstock.keys():
        for j in Nstock.keys():
            print(j,j+i)
            del Nstock[j]
            del Nstock[j+i]
            del Dstock[i]
            del Dstock[N-i]
            break
        else:
            continue
        break
Problem p02787 (python)

Fixed submission:
#モンスターの体力は H
#トキはN種類の魔法が使え、
#i番目の魔法を使うと、モンスターの体力を Ai減らすことができますが、
#トキの魔力を Bi消耗します。

#dp[i] = モンスターの体力を i 減らすため消耗する魔力の最小値
#dp[i+1] = min(dp[i-Ai]+Bi,dp[i])
#dp[0]=0

import numpy as np
 
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab = np.array(ab)
 
a = ab[:, 0]
b = ab[:, 1]
 
dp = np.zeros(100001, dtype=np.int)
for i in range(1, h+1):
    dp[i] = (dp[i-a]+b).min()
print(dp[h])

Buggy submission (verdict: Runtime Error):
import math

H,N = map(int,input().split())
ab = [list(map(int,input().split()))for _ in range(N)]

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
      mana = dp[i-1][j-(a*k)][0]+b*k
      damage = dp[i-1][j-(a*k)][1]+(a*k)
      if damage >= j:
        if dp[i][j][0] > mana:
          dp[i][j]=[mana,damage]
print(dp[N][H][0])

Buggy submission (verdict: Runtime Error):
import math

H,N = map(int,input().split())
ab = [list(map(int,input().split()))for _ in range(N)]

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
        mana = dp[i-1][j-(a*k)][0]+b*k
        damage = dp[i-1][j-(a*k)][1]+(a*k)
        if damage >= j:
            if dp[i][j][0] > mana:
                dp[i][j]=[mana,damage]
print(dp[N][H][0])

Buggy submission (verdict: Runtime Error):
import math

H,N = map(int,input().split())
ab = [list(map(int,input().split()))for _ in range(N)]

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
        mana = dp[i-1][j-(a*k)][0]+b*k
        damage = dp[i-1][j-(a*k)][1]+(a*k)
        if damage >= j:
            if dp[i][j][0] > mana:
                dp[i][j]=[mana,damage]

print(dp[N][H])

Buggy submission (verdict: Runtime Error):
import math

H,N = map(int,input().split())
ab = [list(map(int,input().split()))for _ in range(N)]

dp=[[[float('INF'),0] for _ in range(H+1)]for i in range(N+1)]
dp[0]=[[0,0]for _ in range(H+1)]
for i in range(1,N+1):
  a = ab[i-1][0]
  b = ab[i-1][1]
  for j in range(1,H+1):
    limit = math.floor(j/a)+2
    for k in range(limit):
        mana = dp[i-1][j-(a*k)][0]+b*k
        damage = dp[i-1][j-(a*k)][1]+(a*k)
        if damage >= j:
            if dp[i][j][0] > mana:
                dp[i][j]=[mana,damage]
        

print(dp[N][H][0])
Problem p02796 (python)

Fixed submission:
n = int(input())
robotList=[]
for i in range(n):
  x,l = map(int,input().split())
  s = max(x-l,0)
  t = min(10**9,x+l)  
  robotList.append([t,s])
  
robotList.sort()

count = 0
tmp = 0
for robot in robotList:
  if robot[1] >= tmp:
    count += 1
    tmp = robot[0]

print(count)

Buggy submission (verdict: Runtime Error):
N = int(input())
ts = []
for _ in range(N):
    x, l = map(int,input().split())
    t = min(x+l,10**9)
    s = max(x-l,0)
    ts.appned([t,s])

ts.sort()

tmp = 0
count = 0
for n in ts:
    if tmp<=n[1]:
        count += 1
        tmp = n[0]

print(count)

Buggy submission (verdict: Runtime Error):
N = int(input())
ts=[]
for i in range(N):
  x, l = map(int,input().split())
  if x + l <= 10**9:
    t = x + l
  else:
    t = s
  if x-l >= 0:
    s = x-l
  else:
    s = 0
  ts.append([t,s])
ts.sort()

count = 0
lastT = 0
for i in ts:
  if i[1]>=lastT:
    count+=1
    lastT=i[0]
print(count)

Buggy submission (verdict: Runtime Error):
N = int(input())
ts=[]
for i in range(N):
  x, l = map(int,input().split())
  if x + l <= 100000:
    t = x + l
  else:
    t = s
  if x-l >= 0:
    s = x-l
  else:
    s = 0
  ts.append([t,s])
ts.sort()

count = 0
lastT = 0
for i in ts:
  if i[1]>=lastT:
    count+=1
    lastT=i[0]
print(count)

Buggy submission (verdict: Runtime Error):
N = int(input())
ts=[]
for i in range(N):
  x, l = map(int,input().split())
  if x + l <= 100000:
    t = x + l
  else:
    t = s
  if x-l >= 0:
    s = x-l
  else:
    s = 0
  ts.append([t,s])
ts.sort()

count = 0
lastT = 0
for i in ts:
  if i[1]>=lastT:
    count+=1
    lastT=i[0]
print(count)
Problem p02997 (python)

Fixed submission:
"""
Nの制約数の少なさてきに、全探索するのがよさそう。
とはいえ、ありうるすべてのグラフパターンを全探索したら、2**(N^2)かかる

N本目以降は、辺の数を増やせば増やすほど、有効なペアの数が減っていく。
逆にいうと、ペアの数を減らしたい場合は、N本目以降を追加する
"""
N,K = map(int,input().split())
if K > N*(N-1)//2-(N-1):
    print(-1)
    exit()
edges = []
base = 1
for i in range(base+1,N+1):
    edges.append(" ".join([str(base),str(i)]))

diff = (N-1)*(N-2)//2 - K
base = 2
while diff:
    for i in range(base+1,N+1):
        if diff == 0:
            break
        else:
            edges.append(" ".join([str(base),str(i)]))
            diff -= 1
    base += 1
print(len(edges))
for ans in edges:
    print(ans)

Buggy submission (verdict: Runtime Error):
"""
最短距離が2であるようなノードの組み合わせは、最高で(N-1)C2個存在する。
そこで、この(N-1)C2個の組み合わせがある状態をデフォルトとして、K個になるまで辺を増やしていく。
"""
import math
def choose(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
N,K = map(int,input().split())
if K > choose(N-1,2):
    print(-1)
else:
    edges = []
    for i in range(2,N+1):
        edges.append((1,i))
    rest = choose(N-1,2) - K
    for i in range(2,N+1):
        for j in range(i+1,N+1):
            if rest == 0:
                break
            else:
                edges.append((i,j))
                rest -= 1
        else:
            continue
        break
    print(len(edges))
    for u,v in edges:
        print(" ".join([str(u),str(v)]))
Problem p03044 (python)

Fixed submission:
def main():
    import sys
    input = sys.stdin.readline
    import heapq

    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w))
        edges[v].append((u,w))
    
    colors = [-1]*(N+1)
    que = [(0,1)]
    heapq.heapify(que)
    while que:
        c,n = heapq.heappop(que)
        if colors[n] == -1:
            colors[n] = c
            for nx,w in edges[n]:
                if w%2==0:
                    nxC = c
                else:
                    nxC = (c+1)%2
                heapq.heappush(que,(nxC,nx))

    for i in range(1,N+1):
        print(colors[i])

main()

Buggy submission (verdict: Runtime Error):
N = int(input())
edges = [[]for _ in range(N+1)]
for _ in range(N-1):
    u,v,w = map(int,input().split())
    edges[u].append((v,w%2))
    edges[v].append((u,w%2))
colors = [0]*(N+1)
def dfs(n,p,c):
    colors[n] = c
    for nx,w in edges[n]:
        if nx != p:
            if w%2 == 0:
                dfs(nx,n,c)
            else:
                dfs(nx,n,(c+1)%2)

dfs(1,0,0)
for i in range(1,N+1):
    print(colors[i])

Buggy submission (verdict: Runtime Error):
def main:
    import sys
    input = sys.stdin.readline
    import heapq

    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v,w = map(int,input().split())
        edges[u].append((v,w))
        edges[v].append((u,w))
    
    colors = [-1]*(N+1)
    que = [(0,1)]
    heapq.heapify(que)
    while que:
        c,n = heapq.heappop(que)
        if colors[n] == -1:
            colors[n] = c
            for nx,w in edges[n]:
                if w%2==0:
                    nxC = c
                else:
                    nxC = (c+1)%2
                heapq.heappush((nxC,nx))

    for i in range(1,N+1):
        print(colors[i])

main()
Problem p03061 (python)

Fixed submission:
"""
問題文を言い換えると、「最大公約数が最大になるように数字を一つ書き換えろ」ということ。
さらに言い換えると、「最大公約数が最大になるように数字を一つ消せ」ということ。
単純な線形探索でできるか？→NO

最大公約数を小さくする要因となっている数字を一つ消す。
どういう数字が最大公約数を小さくする要因になっているか？
他の数字と共通する素因数が少ない、小さい、次数が小さい。ただ、この3つを総合的に判断するのは難しすぎる。
素因数分解はやめて、単純に約数で探せばよいか。
各Aの約数を昇順で列挙しておく。
まずA1は必ず残すと仮定して、A1の約数の大きい方から順番に、ほかのAの約数になるかどうかを調べる。
その約数を含んでいないAが一つだけ存在するとき、そのAを消せば、その約数が最大公約数となる。

次に、A1を消す場合の最大公約数も求めて、A1を含める場合の最大公約数と比較して大きい方を採用する。
"""

N = int(input())
A = list(map(int,input().split()))

#A1を必ず入れる場合の最大公約数を求める。
yakusu = []

a = A[0]
d = 1
while d*d < a:
    if a % d == 0:
        yakusu.append(d)
        yakusu.append(a//d)
    d += 1
if d*d == a:
    yakusu.append(d)
yakusu.sort(reverse=True)

ans = 1
for v in yakusu:
    cnt = 0
    for i in range(1,N):
        if A[i]%v != 0:
            cnt += 1
    if cnt <= 1:
        ans = v
        break

#A1を入れない場合の最大公約数を求める。
import math
g = A[1]
for i in range(2,N):
    g = math.gcd(g,A[i])

ans = max(ans,g)

print(ans)

Buggy submission (verdict: Runtime Error):
"""
最大公約数をもっとも落としている数Xを削る（＝見ないことにする）、という発想に置き換える。
方針１：
Xを特定する。
どうやって特定する？
各Aを素因数分解する。このとき、他の

方針２：
約数をカウントする。すべてのAの約数をカウントして総和する。
このとき、カウントがN個になる約数は初期状態での公約数である。
一方で、カウントがN-1個の約数は、その約数をもたない数が一つだけ存在するということなので、
そのような数Aを削ったときに、公約数になる。
したがって、カウントがN-1個以上の約数のうち最大のものが、数Xを削ったときの最大公約数である。
問題はどうやって約数をカウントするかだ。愚直にやるとO(N√max(A))かかるため間に合わない。
ただ、約数の数自体はせいぜい1000個くらいのはず。いったん素因数分解してから、各素因数を何個累乗させるかで考えればよいか。
"""
def main():
    N = int(input())
    A = list(map(int,input().split()))
    count = {}

    for a in A:
        tmp = []
        d = 2
        while d*d <= a:
            while a%d == 0:
                tmp.append(d)
                a //= d
            d += 1
        if a != 1:
            tmp.append(a)
        divides = [1]
        for k,v in Counter(tmp).items():
            M = len(divides)
            for i in range(1,v+1):
                for j in range(M):
                    divides.append(divides[j]*pow(k,i))
        
        for d in divides:
            if d not in count:
                count[d] = 0
            count[d] += 1

    ans = 0
    for k,v in count.items():
        if v >= N-1:
            ans = max(ans,k)
    print(ans)
main()
Problem p03305 (python)

Fixed submission:
import heapq

n,m,s,t = map(int,input().split())
edgesYen = [[]for _ in range(n+1)]
edgesSnuuk = [[]for _ in range(n+1)]

for _ in range(m):
    u,v,a,b = map(int,input().split())
    edgesYen[u].append((v,a))
    edgesYen[v].append((u,a))
    edgesSnuuk[u].append((v,b))
    edgesSnuuk[v].append((u,b))


def dijkstra(edges,costDic,que):
    while que:
        cost,now = heapq.heappop(que)
        if now not in costDic:
            costDic[now] = cost
            for nx,c in edges[now]:
                if nx not in costDic:
                    heapq.heappush(que,(cost+c,nx))
#都市sから各都市に円で行く場合の最小コストを求める。
costYen = {}
que1 = [(0,s)]
heapq.heapify(que1)
dijkstra(edgesYen,costYen,que1)

costSnuuk = {}
que2 = [(0,t)]
heapq.heapify(que2)
dijkstra(edgesSnuuk,costSnuuk,que2)


minimumCosts = []
for i in range(1,n+1):
    cost = costYen[i] + costSnuuk[i]
    minimumCosts.append((cost,i))
heapq.heapify(minimumCosts)

money = 10**15
tmp = heapq.heappop(minimumCosts)
for i in range(n):
    while tmp[1] <= i:
        tmp = heapq.heappop(minimumCosts)
    print(money-tmp[0])

Buggy submission (verdict: Runtime Error):
"""
前処理として、各地点で両替した場合に最終的に残るスヌークを計算しておく。
これは、s地点から各地点までの円での最小コストと t地点から各地点までのスヌークでの最小コストを計算することで可能である。
次に、各地点で両替した場合に残るスヌークを昇順で保持しておく。
これで前処理は完了。

あとは、小さい順に残スヌークを取り出し、その両替地点の番号がi以下であれば、新しい最小値を取り出し、そうでなければ、その値を出力する。
"""
def main():
    import sys
    input = sys.stdin.readline
    import heapq
    n,m,s,t = map(int,input().split())
    def dijkstra(edges,costDic,startPoint):
        que=[(0,startPoint)]
        heapq.heapify(que)
        while que:
            cost,now = heapq.heappop(que)
            if now not in costDic:
                costDic[now] = cost
                for nx,c in edges[now]:
                    if nx not in costDic:
                        heapq.heappush(que,(cost+c,nx))

    yenEdges = [[] for _ in range(n+1)]
    snuukEdges = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v,a,b = map(int,input().split())
        yenEdges[u].append((v,a))
        yenEdges[v].append((u,a))
        snuukEdges[u].append((v,b))
        snuukEdges[v].append((u,b))
    yenDic = {}
    snuukDic = {}

    dijkstra(yenEdges,yenDic,s)
    dijkstra(snuukEdges,snuukDic,t)

    remainingSnuuk = []
    for i in range(1,n+1):
        remainingSnuuk.append((10**15-(yenDic[i]+snuukDic[i])),i)
    remainingSnuuk.sort(key=lambda x: x[0], reverse=True)

    j = 0
    for i in range(n):
        while remainingSnuuk[j][1] <= i:
            j += 1
        print(remainingSnuuk[j][0])
main()
Problem p03404 (python)

Fixed submission:
"""

Wは100で固定する。
1行目でできるかぎり連結成分の数が多くなるようにする。


W=100で固定し、白黒格子上になるように列を組む。
白と黒どちらかが規定数をオーバーしたら次の行で調整を入れて数を減らす。
ここでは、白が規定数に達したと仮定しよう。
白色の数に調整を入れたら、次の行では
"""
A,B = map(int,input().split())
N = 100
n = N//2
grid = [["#"]*N for _ in range(N)]
for i in range(n,N):
    for j in range(N):
        grid[i][j] = "."

A -= 1
B -= 1

for i in range(0,A//n*2,2):
    for j in range(0,N,2):
        grid[i][j] = "."

for j in range(0,A%n*2,2):
    grid[A//n*2][j] = "."

grid = grid[::-1]
for i in range(0,B//n*2,2):
    for j in range(0,N,2):
        grid[i][j] = "#"

for j in range(0,B%n*2,2):
    grid[B//n*2][j] = "#"

print(" ".join([str(N),str(N)]))
for i in range(N):
    print("".join(grid[i]))

Buggy submission (verdict: Runtime Error):
"""

Wは100で固定する。
1行目でできるかぎり連結成分の数が多くなるようにする。


W=100で固定し、白黒格子上になるように列を組む。
白と黒どちらかが規定数をオーバーしたら次の行で調整を入れて数を減らす。
ここでは、白が規定数に達したと仮定しよう。
白色の数に調整を入れたら、次の行では
"""
A,B = map(int,input().split())
N = 10
n = N//2
grid = [["#"]*N for _ in range(N)]
for i in range(N//2,N):
    for j in range(N):
        grid[i][j] = "."

A -= 1
B -= 1

for i in range(0,A//n*2,2):
    for j in range(0,N,2):
        grid[i][j] = "."

for j in range(0,A%n*2,2):
    grid[A//n*2][j] = "."

grid = grid[::-1]
for i in range(0,B//n*2,2):
    for j in range(0,N,2):
        grid[i][j] = "#"

for j in range(0,B%n*2,2):
    grid[B//n*2][j] = "#"

print(grid)
Problem p03408 (python)

Fixed submission:
from collections import Counter
N = int(input())
blue = []
for _ in range(N):
    blue.append(input())
blue = Counter(blue)

M = int(input())
red = []
for _ in range(M):
    red.append(input())
red = Counter(red)

diff = blue - red
if len(diff)==0:
    print(0)
else:
    print(max(diff.values()))

Buggy submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
S = Counter([input() for _ in range(N)])
M = int(input())
T = Counter([input() for _ in range(M)])
G = S-T
print(max([a for a in G.values()]))
Problem p03526 (python)

Fixed submission:
N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

maxH = max(men)[0]
inf = maxH+1
#dp[i][j] -> i人目までみたとき、j人が座布団を積む場合の最小枚数
dp = [[-1]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if 0 <= dp[i-1][j-1] <= h:
            if dp[i-1][j] == -1:
                dp[i][j] = dp[i-1][j-1]+p
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != -1:
        print(j)
        break

Buggy submission (verdict: Runtime Error):
N = int(input())
"""
dp[i][j] -> i番目の人間までみる。j人が積むときの最小値。

"""
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x:x[0]+x[1])
dp = [[float("INF")]*(N+1) for _ in range(N)]
for i in range(N):
    dp[i][0] = 0
dp[0][1] = HP[1][1]
for i in range(1,N):
    for j in range(1,N+1):
        if dp[i-1][j-1] <= HP[i][0]:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+HP[i][1])
        else:
            dp[i][j] = dp[i-1][j]
for j in range(N,-1,-1):
    if dp[-1][j] != float("INF"):
        print(j)
        break

Buggy submission (verdict: Runtime Error):
N = int(input())
HP = [list(map(int,input().split())) for _ in range(N)]
HP.sort(key=lambda x: x[0]+x[1])
ceil = max(HP,key=lambda x: x[0])[0]
#dp[i][j] -> i人目まで見る。j人積むときの、座布団の枚数の最小値
dp = [ceil+1]*(N+1)
ans = 0
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    h,p = HP[i]
    for j in range(N,0,-1):
        if dp[j-1]<=h:
            dp[j] = min(dp[j],dp[j-1]+p)
            ans = max(ans,j)

print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

inf = max(H)+1
dp = [[inf]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1] <= h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != inf:
        print(j)
        break