Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd

N = int(input())
A = list([int(x) for x in input().split()])

max_a = 10**6 + 1

before = 0
result = [0 for _ in range(max_a + 1)]

for i in A:
    before = gcd(before, i)
    result[i] += 1

is_pairwise = True
for i in range(2, max_a + 1):
    cnt = 0
    for j in range(i, max_a + 1, i):
        cnt += result[j]

    if cnt > 1:
        is_pairwise = False
        break

if is_pairwise:
    print('pairwise coprime')
    exit()

if before == 1:
    print('setwise coprime')
else:
    print('not coprime')


Fixed submission:
from math import gcd


def main():
    N = int(input())
    A = list([int(x) for x in input().split()])

    max_a = max(A)

    before = 0
    result = [0 for _ in range(max_a + 1)]

    for i in A:
        before = gcd(before, i)
        result[i] += 1

    is_pairwise = True
    for i in range(2, max_a + 1):
        cnt = 0
        for j in range(i, max_a + 1, i):
            cnt += result[j]

        if cnt > 1:
            is_pairwise = False
            break

    if is_pairwise:
        print('pairwise coprime')
        exit()

    if before == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd

N = int(input())
A = list([int(x) for x in input().split()])

before = 0
result = [0] * (max(A) + 1)

for i in A:
    before = gcd(before, i)
    result[i] += 1

is_pairwise = True
for i in range(2, max(A) + 1):
    cnt = 0
    for j in range(i, max(A) + 1, i):
        cnt += result[j]

    if cnt > 1:
        is_pairwise = False
        break

if is_pairwise:
    print('pairwise coprime')
    exit()

if before == 1:
    print('setwise coprime')
else:
    print('not coprime')


Fixed submission:
from math import gcd


def main():
    N = int(input())
    A = list([int(x) for x in input().split()])

    max_a = max(A)

    before = 0
    result = [0 for _ in range(max_a + 1)]

    for i in A:
        before = gcd(before, i)
        result[i] += 1

    is_pairwise = True
    for i in range(2, max_a + 1):
        cnt = 0
        for j in range(i, max_a + 1, i):
            cnt += result[j]

        if cnt > 1:
            is_pairwise = False
            break

    if is_pairwise:
        print('pairwise coprime')
        exit()

    if before == 1:
        print('setwise coprime')
    else:
        print('not coprime')


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
H, W, M = [int(x) for x in input().split()]

width = [0] * W
height = [0] * H

obj = set()
for i in range(M):
    h, w = [int(x) - 1 for x in input().split()]

    width[w] += 1
    height[h] += 1
    obj.add((h, w))

for idx_h, h in [(idx_h, h) for idx_h, h in enumerate(height) if h == max(height)]:
    for idx_w, w in [(idx_w, w) for idx_w, w in enumerate(width) if w == max(width)]:
        if not (idx_h, idx_w) in obj:
            print(h + w)
            exit()

print(max(height) + max(width) - 1)


Fixed submission:
import numpy
H, W, M = [int(x) for x in input().split()]

width = numpy.array([0] * W, dtype='int64')
height = numpy.array([0] * H, dtype='int64')

obj = set()
for i in range(M):
    h, w = [int(x) - 1 for x in input().split()]

    width[w] += 1
    height[h] += 1
    obj.add((h, w))

result_h = set(numpy.where(height == numpy.max(height))[0])
result_w = set(numpy.where(width == numpy.max(width))[0])

if len(result_h) * len(result_w) > M:
    print(numpy.max(height) + numpy.max(width))
    exit()

for h in result_h:
    for w in result_w:
        if not (h, w) in obj:
            print(numpy.max(height) + numpy.max(width))
            exit()

print(numpy.max(height) + numpy.max(width) - 1)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N, K = [int(x) for x in input().split()]
A = list([int(x) for x in input().split()])

before = 1

for i in range(K):
    before *= A[i]

for i in range(K, N):
    after = before // A[i-K]
    after *= A[i]

    if after > before:
        print('Yes')
    else:
        print('No')

    before = after


Fixed submission:
N, K = [int(x) for x in input().split()]
A = list([int(x) for x in input().split()])

for i in range(K, N):
    if A[i] / A[i-K] > 1:
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Runtime Error):

N = int(input())
A = list([int(x) for x in input().split()])

max_money = 1000
stock = 0

for i in range(N-1):
    if A[i] < A[i+1]:
        stock += money // A[i]
        money -= A[i] * stock
    else:
        money += stock * A[i]
        stock = 0


print(max_money)


Fixed submission:
N = int(input())
A = list([int(x) for x in input().split()])

money = 1000
stock = 0

for i in range(N-1):
    if A[i] <= A[i+1]:
        stock += money // A[i]
        money -= (money // A[i]) * A[i]
    else:
        money += A[i] * stock
        stock = 0

print(money + stock * A[N-1])

Buggy python submission (verdict: Runtime Error):

N = int(input())
A = list([int(x) for x in input().split()])

max_money = 1000
stock = 0

for i in range(N-1):
    if A[i] < A[i+1]:
        stock += money // A[i]
        money -= money - A[i] * stock
    else:
        money += stock * A[i]
        stock = 0


print(max_money)


Fixed submission:
N = int(input())
A = list([int(x) for x in input().split()])

money = 1000
stock = 0

for i in range(N-1):
    if A[i] <= A[i+1]:
        stock += money // A[i]
        money -= (money // A[i]) * A[i]
    else:
        money += A[i] * stock
        stock = 0

print(money + stock * A[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N = int(input())
A = list([int(x) for x in input().split()])

stack = deque()

stack.appendleft((0, 1000, 0))
max_money = 1000

while stack:
    target = stack.popleft()

    day = target[0]
    money = target[1]
    stock = target[2]

    if day + 1 <= N:
        stack.appendleft((day + 1, money + stock * A[day], 0))
        stack.appendleft(
            (day + 1, money - (money // A[day]) * A[day], money // A[day]))
    else:
        if max_money < money:
            max_money = money

print(max_money)


Fixed submission:
N = int(input())
A = list([int(x) for x in input().split()])

money = 1000
stock = 0

for i in range(N-1):
    if A[i] <= A[i+1]:
        stock += money // A[i]
        money -= (money // A[i]) * A[i]
    else:
        money += A[i] * stock
        stock = 0

print(money + stock * A[N-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N = int(input())
A = list([int(x) for x in input().split()])

stack = deque()

stack.appendleft((0, 1000, 0))
max_money = 1000

while stack:
    target = stack.popleft()

    day = target[0]
    money = target[1]
    stock = target[2]

    if day + 1 <= N:
        max_buy = money // A[day]
        max_fee = stock * A[day]

        stack.appendleft((day + 1, money + stock * A[day], 0))
        stack.appendleft(
            (day + 1, money - (money // A[day]) * A[day], money // A[day]))
    else:
        if max_money < money:
            max_money = money

print(max_money)


Fixed submission:
N = int(input())
A = list([int(x) for x in input().split()])

money = 1000
stock = 0

for i in range(N-1):
    if A[i] <= A[i+1]:
        stock += money // A[i]
        money -= (money // A[i]) * A[i]
    else:
        money += A[i] * stock
        stock = 0

print(money + stock * A[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())


def func(n):
    result = 0
    for x in range(1, n+1):
        for y in range(1, n+1):
            for z in range(1, n+1):
                check = x**2 + y**2 + z**2 + x * y + y * z + z * x
                if check == n:
                    #print("n :{} ({},{},{})".format(n, x, y, z))
                    result += 1

                if check > n:
                    break

    return result


for i in range(1, N+1):
    print(func(i))


Fixed submission:
from math import sqrt

N = int(input())
result = [0] * N

n = int(sqrt(N))

for x in range(1, n+1):
    for y in range(1, n+1):
        for z in range(1, n+1):
            check = x**2 + y**2 + z**2 + x * y + y * z + z * x

            if check <= N:
                result[check-1] += 1

for i in result:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())


def func(n):
    result = 0
    for x in range(1, n+1):
        for y in range(1, n+1):
            for z in range(1, n+1):
                check = x**2 + y**2 + z**2 + x * y + y * z + z * x
                if check == n:
                    #print("n :{} ({},{},{})".format(n, x, y, z))
                    result += 1

                if check > n:
                    break

    return result


for i in range(1, N+1):
    print(func(i))


Fixed submission:
from math import sqrt

N = int(input())
result = [0] * N

n = int(sqrt(N))

for x in range(1, n+1):
    for y in range(1, n+1):
        for z in range(1, n+1):
            check = x**2 + y**2 + z**2 + x * y + y * z + z * x

            if check <= N:
                result[check-1] += 1

for i in result:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list([int(x) for x in input().split()])

A.sort(reverse=True)


comfort = 0

comfort_list = []

for a in A:
    if comfort_list == []:
        comfort_list.append(a)
    else:
        max_comfort = comfort_list.pop(0)
        comfort += max_comfort
        comfort_list.append(min(a, max_comfort))
        comfort_list.append(min(a, max_comfort))

print(comfort)


Fixed submission:
from collections import deque

N = int(input())
A = list([int(x) for x in input().split()])

A.sort(reverse=True)

comfort = 0
comfort_list = deque()

for a in A:
    if len(comfort_list) == 0:
        comfort_list.append(a)
    else:
        max_comfort = comfort_list.popleft()
        comfort += max_comfort
        comfort_list.append(min(a, max_comfort))
        comfort_list.append(min(a, max_comfort))

print(comfort)
Buggy python submission (verdict: Runtime Error):
from collections import deque

N, M, K = [int(x) for x in input().split()]

a_book = [0]
for index, i in enumerate(input().split(), 1):
    a_book.append(a_book[index-1] + int(i))

b_book = [0]
for index, i in enumerate(input().split(), 1):
    b_book.append(b_book[index-1] + int(i))

search = deque()
check = {}


def search_count(v):
    search.appendleft(v)
    while search:
        v = search.popleft()

        if not v in check:
            check[v] = v[0] + v[1]

            if not (v[0] + 1, v[1]) in check:
                if v[0] + 1 <= N:
                    if a_book[v[0] + 1] + b_book[v[1]] <= K:
                        search.appendleft((v[0] + 1, v[1]))

            if not (v[0], v[1] + 1) in check:
                if v[1] + 1 <= M:
                    if a_book[v[0]] + b_book[v[1] + 1] <= K:
                        search.appendleft((v[0], v[1] + 1))


search_count((0, 0))

print(max(check.values()))


Fixed submission:
a = int(input())

print(a + a**2 + a**3)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
np_a = np.array(A)

ng_count = 0

for a in A:
    # 自分は必ず割り切れる 他にいたら 0が2以上になるはず
    if np.count_nonzero(a % np_a == 0) > 1:
        ng_count += 1

print(N - ng_count)


Fixed submission:
import numpy as np
from collections import Counter
from math import sqrt
from time import time


def main():
    N = int(input())
    np_a_o = list([int(x) for x in input().split()])
    np_a = Counter(np_a_o)

    np_a_keys = set(np_a.keys())

    div_list = set()
    key_max = max(np_a_keys)

    c = 0

    for key in np_a_keys:
        for div in range(key*2, key_max+1, key):
            div_list.add(div)

    r = np_a_keys - div_list

    u, count = np.unique(np.array(np_a_o), return_counts=True)
    r -= set(u[count > 1])

    print(len(r))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
np_a = np.array(A)

ng = []

for a in A:
    # 自分は必ず割り切れる 他にいたら 0が2以上になるはず
    if Counter(a % np_a)[0] > 1:
        ng.append(a)

print(N - len(ng))


Fixed submission:
import numpy as np
from collections import Counter
from math import sqrt
from time import time


def main():
    N = int(input())
    np_a_o = list([int(x) for x in input().split()])
    np_a = Counter(np_a_o)

    np_a_keys = set(np_a.keys())

    div_list = set()
    key_max = max(np_a_keys)

    c = 0

    for key in np_a_keys:
        for div in range(key*2, key_max+1, key):
            div_list.add(div)

    r = np_a_keys - div_list

    u, count = np.unique(np.array(np_a_o), return_counts=True)
    r -= set(u[count > 1])

    print(len(r))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys

N, K = map(int, input().split())
town_list = list(map(int, input().split()))

roop = 0
queue = [1]

start = -1

for now_town in queue:
    if town_list[now_town - 1] in queue:
        start = town_list[now_town - 1]
        break
    queue.append(town_list[now_town - 1])

if start == -1:
    print(queue[K])
    sys.exit()

before_len = queue.index(start)
roop = len(queue) - before_len

print(queue[before_len + (K - before_len) % roop])


Fixed submission:
S = input()
T = input()

if S == T[0:-1]:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import math


K = int(input())
result = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            result += math.gcd(math.gcd(a, b), c)

print(result)


Fixed submission:
import math


K = int(input())
result = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        r = math.gcd(a, b)
        for c in range(1, K+1):
            result += math.gcd(r, c)

print(result)
Buggy python submission (verdict: Runtime Error):
K, N = [int(x) for x in input().split()]
A = list([int(x) for x in input().split()])

result = []

for i in range(N):
    if i == N - 1:
        result.append(K - A[i] + A[0])
    else:
        result.appnd(A[i + 1] - A[i])

result.sort()

print(sum(result[:-1]))


Fixed submission:
K, N = [int(x) for x in input().split()]

A = list([int(x) for x in input().split()])

r_list = []

for i in range(N):
    if i == N - 1:
        r_list.append(A[0] + K - A[i])

    else:
        r_list.append(A[i + 1] - A[i])

r_list.sort()

print(sum(r_list[:-1]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from operator import mul
from functools import reduce

N = int(input())

line = [int(x) for x in input().split()]
counter = Counter(line)

result = {}

for i in range(N):
    target = line[i]
    collection = 0
    if target in result:
        print(result[target])
    else:
        for key, value in counter.items():
            if key == target:
                value -= 1

            collection += int((value * (value-1) / 2))
        result[target] = collection
        print(collection)


Fixed submission:
from collections import Counter
from operator import mul
from functools import reduce

N = int(input())

line = [int(x) for x in input().split()]
counter = Counter(line)

collect = {key: int(value * (value - 1) / 2)
           for key, value in counter.items()}
min_collect = {key: int((value - 1) * (value - 2) / 2)
               for key, value in counter.items()}

max_value = sum(collect.values())

for i in line:
    print(min_collect[i] + max_value - collect[i])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

S = input()

result = deque(S)


def input_str(line):
    r = line.split()
    if len(r) == 1:
        return int(r[0]), None, None
    else:
        return int(r[0]), int(r[1]), r[2]


for _ in range(int(input())):
    Q, F, C = input_str(input())
    if Q == 1:
        result.reverse()
    if Q == 2:
        if F == 1:
            result.appendleft(C)
        else:
            result.append(C)

print(''.join(result))


Fixed submission:
from collections import deque
from itertools import islice

S = input()

result = deque(S)


def input_str(line):
    r = line.split()
    if len(r) == 1:
        return int(r[0]), None, None
    else:
        return int(r[0]), int(r[1]), r[2]


reverse_flag = False

for _ in range(int(input())):
    Q, F, C = input_str(input())
    if Q == 1:
        reverse_flag ^= True
    if Q == 2:
        if reverse_flag:
            if F == 1:
                result.append(C)
            else:
                result.appendleft(C)
        else:
            if F == 1:
                result.appendleft(C)
            else:
                result.append(C)

if reverse_flag:
    result.reverse()
print(''.join(result))
Buggy python submission (verdict: Time Limit Exceeded):
from sys import exit

N, K = [int(x) for x in input().split()]
H = list([int(x) for x in input().split()])

H.sort(reverse=True)

if len(H) <= K:
    print(0)
    exit()

for _ in range(K):
    H.pop(0)

print(sum(H))


Fixed submission:
from sys import exit

N, K = [int(x) for x in input().split()]
H = list([int(x) for x in input().split()])

if len(H) <= K:
    print(0)
    exit()

H.sort(reverse=True)
H = H[K:]

print(sum(H))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()])
end_set = set()
count = 0

for a in A:
    if not end_set:
        count += 1
    elif a == min(min(end_set), a):
        count += 1
    end_set.add(a)

print(count)


Fixed submission:
N = int(input())
A = list([int(x) for x in input().split()])
count = 0

min_a = N+1

for a in A:
    if a == min(min_a, a):
        count += 1
        min_a = a

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()])

count = 0

for index, a in enumerate(A):
    if np.all(A[:index+1] >= a):
        count += 1

print(count)


Fixed submission:
N = int(input())
A = list([int(x) for x in input().split()])
count = 0

min_a = N+1

for a in A:
    if a == min(min_a, a):
        count += 1
        min_a = a

print(count)
Buggy python submission (verdict: Runtime Error):
N, M = [int(x) for x in input().split()]

ok = 0
ng = 0
ng_l = {}
end = set()

for _ in range(M):
    p, S = [x for x in input().split()]
    p = int(p)

    if not p in end:
        if S == 'AC':
            ok += 1
            ng += ng_l[p]
            end.add(p)
        else:
            if p in ng_l:
                ng_l[p] += 1
            else:
                ng_l[p] = 1

print('{} {}'.format(ok, ng))


Fixed submission:
N, M = [int(x) for x in input().split()]

ok = 0
ng = 0
ng_l = {}
end = set()

for _ in range(M):
    p, S = [x for x in input().split()]
    p = int(p)

    if not p in end:
        if S == 'AC':
            ok += 1
            end.add(p)

            if p in ng_l:
                ng += ng_l[p]
        else:
            if p in ng_l:
                ng_l[p] += 1
            else:
                ng_l[p] = 1

print('{} {}'.format(ok, ng))
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

N = int(input())
A = list([int(x) for x in input().split()])

count = 0
while True:
    # 中心に最も近い点を探す
    ironbar = list(accumulate(A))
    center = sum(A) // 2

    i = 0
    j = len(A) - 1

    while i + 1 < j:
        check = ironbar[(i + j) // 2]
        if check < center:
            i = (i + j) // 2
        elif check > center:
            j = (i + j) // 2
        else:
            print(count)
            exit()

    if check > center:
        A[j] -= 1
    else:
        A[j] += 1

    count += 1


Fixed submission:
from itertools import accumulate

N = int(input())
A = list([int(x) for x in input().split()])

count = 0
ironbar = list(accumulate(A))

min_value = ironbar[-1]
for i in range(N):
    bet = abs(ironbar[i] - (ironbar[-1] - ironbar[i]))

    if min_value > bet:
        min_value = bet
    else:
        print(min_value)
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())


def make_prime(n):
    array = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                array.append(i)
                temp = temp // i

    if temp != 1:
        array.append(temp)

    if array == []:
        array.append(n)

    return array


def devide(array, result):
    if array == []:
        return result

    # xに値を掛けた場合
    x_target = devide(array[1:], (result[0] * array[0], result[1]))

    y_target = devide(array[1:], (result[0], result[1] * array[0]))

    if sum(x_target) <= sum(y_target):
        return x_target
    else:
        return y_target


result = devide(make_prime(N), (1, 1))

print(sum(result) - 2)


Fixed submission:
from math import sqrt

N = int(input())

search_max = int(sqrt(N))

min_number = 10**12
for x in range(1, search_max + 1):
    if N % x == 0:
        y = N // x
        if x + y < min_number:
            min_number = x + y

print(min_number-2)
Buggy python submission (verdict: Time Limit Exceeded):

def is_triangle(a, b, c):
    if a >= b + c:
        return False

    if b >= a + c:
        return False

    if c >= a + b:
        return False

    return True


def main():
    N = int(input())
    L = list([int(x) for x in input().split()])

    L.sort(reverse=True)

    count = 0
    for index, a in enumerate(L):
        if index + 2 == N:
            break

        for b_i in range(index+1, N):
            b = L[b_i]
            c_i = 1

            while not is_triangle(a, b, L[-c_i]):
                if c_i + b_i == N:
                    break
                c_i += 1

            count += (N - b_i - c_i)

    print(count)


if __name__ == '__main__':
    main()


Fixed submission:

def is_triangle(a, b, c):
    if a >= b + c:
        return False

    if b >= a + c:
        return False

    if c >= a + b:
        return False

    return True


def main():
    N = int(input())
    L = list([int(x) for x in input().split()])

    L.sort()

    count = 0
    for index, a in enumerate(L):
        if index + 2 == N:
            break

        for b_i in range(index+1, N):
            b = L[b_i]
            c = 1

            while not is_triangle(a, b, L[-c]):
                c += 1

            count += (N - b_i - c)

    print(count)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):

def is_triangle(a, b, c):
    if a >= b + c:
        return False

    if b >= a + c:
        return False

    if c >= a + b:
        return False

    return True


def main():
    N = int(input())
    L = list([int(x) for x in input().split()])

    L.sort()

    count = 0
    for index, a in enumerate(L):
        if index + 2 == N:
            break

        for b_i in range(index+1, N):
            b = L[b_i]
            c = 1

            while not is_triangle(a, b, L[-c]):
                c += 1

            count += (N - b_i - c)

    print(count)


if __name__ == '__main__':
    main()


Fixed submission:

def is_triangle(a, b, c):
    if a >= b + c:
        return False

    if b >= a + c:
        return False

    if c >= a + b:
        return False

    return True


def main():
    N = int(input())
    L = list([int(x) for x in input().split()])

    L.sort()

    count = 0
    for index, a in enumerate(L):
        if index + 2 == N:
            break

        for b_i in range(index+1, N):
            b = L[b_i]
            c = 1

            while not is_triangle(a, b, L[-c]):
                c += 1

            count += (N - b_i - c)

    print(count)


if __name__ == '__main__':
    main()