Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def ctoi(c):  # a~zを0~25に変換する(各アルファベットを数字に変換する)
    return ord(c) - 97


N = int(input())
S = list(input())
bits = [[0]*(N+1) for _ in range(26)]  # Binary Indexed Treeを26種類の各アルファベットについてもつ(0初期化, 1-index)


def BIT_query(idx):  # 各文字について1からidx番目までの文字数を数える
    res = [0]*26
    for i in range(26):
        tmp = 0
        p = idx
        while p > 0:  # 1からidx番目までの要素の和を取る
            tmp += bits[i][p]
            p -= p&(-p)  # 区間の長さを引くことで次のindexを得ることができる
        res[i] = tmp
    return res


def BIT_update(idx, alphabet, x):  # alphabet番目のアルファベットについてidx番目の要素の値にxを加える
    while idx <= N:  # idx番目の要素を含む全ての要素についてxを加える
        bits[alphabet][idx] += x
        idx += idx&(-idx)


for i in range(N):  # 各BITを与えられた文字列で初期化する
    BIT_update(i+1, ctoi(S[i]), 1)  # Sのi番目(0-index)の文字に対応するBITのi+1番目の要素を1として更新する

Q = int(input())
for _ in range(Q):
    flag, a, b = map(str, input().split())
    flag = int(flag)
    a = int(a)
    if flag == 1:
        if S[a-1] == b:  # 同じ文字の場合, 変更しない
            continue
        else:
            BIT_update(a, ctoi(S[a-1]), -1)  # a番目の要素を別のものに変えるので、-1
            BIT_update(a, ctoi(b), 1)  # a番目の要素を文字bに変えるので+1
            S[a-1] = b  # 文字列のa番目の文字を変更する
    elif flag == 2:  # aとbは区間の左端と右端
        b = int(b)
        cnt1 = BIT_query(b)  # 1からbまでの各文字の文字数
        cnt2 = BIT_query(a-1)  # 1からa-aまでの各文字の文字数
        ans = 0
        for i in range(26):
            if cnt1[i]-cnt2[i] > 0:  # lからrまでのその文字の文字数が1以上であれば、その文字はlからrまでの部分文字列に現れるので種類数を1増やす
                ans += 1
        print(ans)


Fixed submission:
def ctoi(c):  # a~zを0~25に変換する(各アルファベットを数字に変換する)
    return ord(c) - 97


N = int(input())
S = list(input())
bits = [[0]*(N+1) for _ in range(26)]  # Binary Indexed Treeを26種類の各アルファベットについてもつ(0初期化, 1-index)


def BIT_query(idx):  # 各文字について1からidx番目までの文字数を数える
    res = [0]*26
    for i in range(26):
        tmp = 0
        p = idx
        while p > 0:  # 1からidx番目までの要素の和を取る
            tmp += bits[i][p]
            p -= p&(-p)  # 区間の長さを引くことで次のindexを得ることができる
        res[i] = tmp
    return res


def BIT_update(idx, alphabet, x):  # alphabet番目のアルファベットについてidx番目の要素の値にxを加える
    while idx <= N:  # idx番目の要素を含む全ての要素についてxを加える
        bits[alphabet][idx] += x
        idx += idx&(-idx)


for i in range(N):  # 各BITを与えられた文字列で初期化する
    BIT_update(i+1, ctoi(S[i]), 1)  # Sのi番目(0-index)の文字に対応するBITのi+1番目の要素を1として更新する

Q = int(input())
for _ in range(Q):
    flag, a, b = map(str, input().split())
    flag = int(flag)
    a = int(a)
    if flag == 1:
        if S[a-1] == b:  # 同じ文字の場合, 変更しない
            continue
        else:
            BIT_update(a, ctoi(S[a-1]), -1)  # a番目の要素を別のものに変えるので、-1
            BIT_update(a, ctoi(b), 1)  # a番目の要素を文字bに変えるので+1
            S[a-1] = b  # 文字列のa番目の文字を変更する
    elif flag == 2:  # aとbは区間の左端と右端
        b = int(b)
        cnt1 = BIT_query(b)  # 1からbまでの各文字の文字数
        cnt2 = BIT_query(a-1)  # 1からa-aまでの各文字の文字数
        ans = 0
        for i in range(26):
            if cnt1[i]-cnt2[i] > 0:  # lからrまでのその文字の文字数が1以上であれば、その文字はlからrまでの部分文字列に現れるので種類数を1増やす
                ans += 1
        print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 通過の種類は10の100乗 + 1 種類
# 10の(10の100乗)乗の桁数は10の100乗桁 (1グーゴル)
# 10の6乗 = 1000000 (100万)
# 通過の方が圧倒的に大きい

s = input()[::-1]  # 与えられた数を下の桁から見る
length = len(s)
dp = [[0]*2 for _ in range(length+1)]  # j=1を更新するとき、お釣りの部分を格納していることになる（支払った1枚の紙幣は次のタイムステップで更新される）
for i in range(length):
    # 今見ている桁に関して、ちょうど支払うとき
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+int(s[i])+1)

    # 今見ている桁に関して、1つ大きい桁の紙幣を1枚使って支払う
    if i != 0:
        # ここで格納される値はお釣りの部分と考えることができる
        dp[i+1][1] = min(dp[i][0]+10-int(s[i]), dp[i][1]+(10-1)-int(s[i]))
    else:
        dp[i+1][1] = dp[i][0]+10-int(s[i])  # お釣りの部分のみが格納されている

print(min(dp[length][0], dp[length][1]+1))


Fixed submission:
# 通過の種類は10の100乗 + 1 種類
# 10の(10の100乗)乗の桁数は10の100乗桁 (1グーゴル)
# 10の6乗 = 1000000 (100万)
# 通過の方が圧倒的に大きい

s = input()[::-1]  # 与えられた数を下の桁から見る
length = len(s)
dp = [[0]*2 for _ in range(length+1)]  # j=1を更新するとき、お釣りの部分を格納していることになる（支払った1枚の紙幣は次のタイムステップで更新される）
for i in range(length):
    # 今見ている桁に関して、ちょうど支払うとき
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+int(s[i])+1)

    # 今見ている桁に関して、1つ大きい桁の紙幣を1枚使って支払う
    if i != 0:
        # ここで格納される値はお釣りの部分と考えることができる
        dp[i+1][1] = min(dp[i][0]+10-int(s[i]), dp[i][1]+(10-1)-int(s[i]))
    else:
        dp[i+1][1] = dp[i][0]+10-int(s[i])  # お釣りの部分のみが格納されている

print(min(dp[length][0], dp[length][1]+1))
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

# 個数制限なしナップサック
# i番目までの魔法を使ったときにHダメージを実現できるときの最小の魔力
dp = [[float('inf')]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # i番目の魔法を使わない時
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # i番目の魔法を使う時
        dp[i+1][min(H, j+A[i])] = min(dp[i][j]+B[i], dp[i+1][j]+B[i], dp[i+1][min(j+A[i], H)])

print(dp[N][H])


Fixed submission:
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]
# i番目までの魔法を使った時にjを削るために必要な最小のコスト
dp = [[10**10]*(H+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for j in range(H+1):
        # 使わない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 使う場合
        dp[i+1][min(j+magic[i][0], H)] = min(dp[i+1][min(j+magic[i][0], H)], dp[i+1][j] + magic[i][1])
print(dp[N][H])
Buggy python submission (verdict: Runtime Error):
import math
from bisect import bisect_right
N, D, A = map(int, input().split())  # N体のモンスター, 爆弾の範囲D, 爆弾の威力A
XH = []
X = []
for _ in range(N):
    x, h = map(int, input().split())
    XH.append(x, math.ceil(x/A))  # 座標と必要な爆弾の個数を格納する
    X.append(x)  # こっちは座標のみ, あとで座標を二分探索するときに使う
# 座標でソートする
XH.sort()
X.sort()
T = [0]*(N+1)
j = 0
now = 0
ans = 0
for i in range(N):
    x, h = XH[i]
    now -= T[i]
    if now >= h:
        continue
    else:
        T[bisect_right(X, x+D*2)] += h - now
        ans += h - now
        now = h
print(ans)

Fixed submission:
import math
from bisect import bisect_right
N, D, A = map(int, input().split())  # N体のモンスター, 爆弾の範囲D, 爆弾の威力A
XH = []
X = []
for _ in range(N):
    x, h = map(int, input().split())
    XH.append((x, math.ceil(h/A)))  # 座標と必要な爆弾の個数を格納する
    X.append(x)  # こっちは座標のみ, あとで座標を二分探索するときに使う
# 座標でソートする
XH.sort()
X.sort()
T = [0]*(N+1)
now = 0
ans = 0
for i in range(N):
    x, h = XH[i]
    now -= T[i]
    if now >= h:
        continue
    else:
        T[bisect_right(X, x+D*2)] += h - now
        ans += h - now
        now = h
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
robots = []
for _ in range(N):
    x, l = map(int, input().split())
    robots.append((x, l))

robots = sorted(robots, key=lambda x: x[0])
rightest_point = robots[0][0] + robots[0][1] - 1
ans = 0
# 無理やり一体目を置いた時
for i in range(1, len(robots)):
    if robots[i][0]-robots[i][1] + 1 < rightest_point:
        ans += 1
        continue
    else:
        rightest_point = robots[i][0]+robots[i][1] - 1
first = N-ans

# 1体目を置かない場合
rightest_point = robots[1][0] + robots[1][1] - 1
ans = 0
for i in range(2, len(robots)):
    # print("rightest_point: ", rightest_point)
    if robots[i][0]-robots[i][1] + 1 < rightest_point:
        ans += 1
        continue
    else:
        rightest_point = robots[i][0]+robots[i][1] - 1
# print("rightest_point: ", rightest_point)
second = N-ans-1
print(max(first, second))


Fixed submission:
N = int(input())
robots = []
for _ in range(N):
    x, l = map(int, input().split())
    robots.append((x-l, x+l))

robots.sort(key=lambda x: x[1])  # 終端を昇順ソート
# print(robots)
cnt = 0
last = -10**18  # 最初、最右のものははるか左側にあると考える
for left, right in robots:
    if left >= last:  # 残せるのであれば
        cnt += 1
        last = right
print(cnt)

Buggy python submission (verdict: Runtime Error):
N = int(input())
robots = []
for _ in range(N):
    x, l = map(int, input().split())
    robots.append((x, l))

robots = sorted(robots, key=lambda x: x[0])
# print(robots)
rightest_point = robots[0][0] + robots[0][1] - 1

ans = 0
for i in range(1, N):
    # print("rightest_point: ", rightest_point)
    if robots[i][0]-robots[i][1] + 1 < rightest_point:
        ans += 1
        continue
    else:
        rightest_point = robots[i][0]+robots[i][1] - 1
# print("rightest_point: ", rightest_point)
first = N-ans
# 最初だけは例外

# ２体目から考える
rightest_point = robots[1][0] + robots[1][1] - 1

ans = 0
for i in range(2, N):
    # print("rightest_point: ", rightest_point)
    if robots[i][0]-robots[i][1] + 1 < rightest_point:
        ans += 1
        continue
    else:
        rightest_point = robots[i][0]+robots[i][1] - 1
second = N-ans
if robots[1][0] - robots[1][1] + 1 < robots[0][0] + robots[0][1] - 1:
    second -= 1

print(max(first, second))


Fixed submission:
N = int(input())
robots = []
for _ in range(N):
    x, l = map(int, input().split())
    robots.append((x-l, x+l))

robots.sort(key=lambda x: x[1])  # 終端を昇順ソート
# print(robots)
cnt = 0
last = -10**18  # 最初、最右のものははるか左側にあると考える
for left, right in robots:
    if left >= last:  # 残せるのであれば
        cnt += 1
        last = right
print(cnt)
Buggy python submission (verdict: Runtime Error):
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 10007
MOD = 1000000007
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()


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

# 最大値を固定してそのパターン数を数える
max_value_sum = 0
for i in range(N):
    max_value_sum += (A[i] * COM(i, K-1) + MOD) % MOD

A.reverse()
min_value_sum = 0
for i in range(N):
    min_value_sum += (A[i] * COM(i, K-1) + MOD) % MOD

ans = max_value_sum - min_value_sum + MOD

print(ans % MOD)


Fixed submission:
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 510000
MOD = 1000000007
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()


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

# 最大値を固定してそのパターン数を数える
max_value_sum = 0
for i in range(N):
    max_value_sum += (A[i] * COM(i, K-1) + MOD) % MOD

# 最小値を固定してそのパターン数を数える
A.reverse()
min_value_sum = 0
for i in range(N):
    min_value_sum += (A[i] * COM(i, K-1) + MOD) % MOD

ans = max_value_sum - min_value_sum + MOD

print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 10005
MOD = 1000000007
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

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

ans = 0
prepro = [1]
for i in range(2, N+1):
    prepro.append((prepro[-1]+inverse[i]) % MOD)

for i in range(N-1):
    ans += (X[i+1]-X[i]) * prepro[i] % MOD
    
ans *= factrial[N-1]  # 期待値の総和に(N-1)!をかける

print(ans % MOD)


Fixed submission:
# 二項係数を"やるだけ"にしてくれるライブラリ
MAX = 510000
MOD = 1000000007
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

N = int(input())
X = list(map(int, input().split()))
# expected_value = [1]
# for i in range(2, N):
#     expected_value.append(expected_value[-1]+(1/i))
ans = 0
f = factrial[N-1]
c = 0
for i in range(1, N):
    c += f * inverse[i]
    c %= MOD
    ans += c * (X[i] - X[i-1])
    ans %= MOD

print(ans % MOD)
Buggy python submission (verdict: Runtime Error):
from collections import deque
N = int(input())
visited = [False]*N
tree = [[] for _ in range(N)]
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    tmp.append((a, b))  # 順番を保持するため

ans = {}  # 連想配列で保持する

q = deque([0])  # 開始のノード
colors = [-1]*N  # そのノードにささっている辺の色
while len(q):  # 幅優先探索を開始する
    v = q.pop()  # 部分木の親のノード
    color = 1
    for e in v:  # 子供に対して操作を行う
        if visited[e]:
            continue
        visited[e] = True
        if colors[v] == color:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)

print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])
    


Fixed submission:
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
ans = {}
tmp = []
flag = [False] * N  # そのノードに到達済みか判定する
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
    tmp.append((a, b))  # 最後に出力する時に使う
    ans[(a, b)] = -1
q = deque([0])  # 開始のノード
colors = [-1]*N
now_color = 0
while len(q):
    v = q.pop()
    flag[v] = True
    color = 1
    # vからeへの辺の色を塗る
    for e in graph[v]:

        if flag[e]:
            continue
        q.append(e)
        if color == colors[v]:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])

Buggy python submission (verdict: Runtime Error):
from collections import deque
N = int(input())
visited = [False]*N
tree = [[] for _ in range(N)]
tmp = []
for _ in range(N-1):
    a, b = map(lambda x: int(x-1), input().split())
    tree[a].append(b)
    tree[b].append(a)
    tmp.append((a, b))  # 順番を保持するため

ans = {}  # 連想配列で保持する

q = deque([0])  # 開始のノード
colors = [-1]*N  # そのノードにささっている辺の色
while len(q):  # 幅優先探索を開始する
    v = q.pop()  # 部分木の親のノード
    color = 1
    for e in v:  # 子供に対して操作を行う
        if visited[e]:
            continue
        visited[e] = True
        if colors[v] == color:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
        q.append(e)

print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])
    

Fixed submission:
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
ans = {}
tmp = []
flag = [False] * N  # そのノードに到達済みか判定する
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
    tmp.append((a, b))  # 最後に出力する時に使う
    ans[(a, b)] = -1
q = deque([0])  # 開始のノード
colors = [-1]*N
now_color = 0
while len(q):
    v = q.pop()
    flag[v] = True
    color = 1
    # vからeへの辺の色を塗る
    for e in graph[v]:

        if flag[e]:
            continue
        q.append(e)
        if color == colors[v]:
            color += 1
        ans[(v, e)] = color
        colors[e] = color
        color += 1
print(max(colors))
for a, b in tmp:
    print(ans[(a, b)])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

left_side = 0
right_side = 0
ans = 1e12

for i in range(1, N):
    left_side = sum(A[:i])
    right_side = sum(A[i:])
    ans = min(ans, abs(left_side-right_side))
print(ans)


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

left_side = 0
right_side = 0
ans = 1e12
# 両サイドの累積和が必要
left_wa = [0, A[0]]
right_wa = [A[-1]]

for i in range(1, N):
    left_wa.append(left_wa[-1] + A[i])
for i in range(2, N+1):
    right_wa.append(right_wa[-1] + A[-i])
# right_wa.append(0)
# print(left_wa)
# print(right_wa)
#
# exit()
for i in range(1, N):
    left_side = left_wa[i]
    right_side = right_wa[-(i+1)]
    # print(left_side, right_side)
    ans = min(ans, abs(left_side-right_side))
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
a, b, c = map(int, input().split())

# 容器に入っている水が半分以下の場合に困る
w = [2]
if a*a*b > 2 * c:
    print(w[4])
    h = (2*c)/(a*a)
    print(math.degrees(math.acos(h/a)))
else:
    h = 2*(a*a*b-c)/(a**2)
    print(math.degrees(math.atan(h/a)))


Fixed submission:
from math import atan, degrees
a, b, x = map(int, input().split())

if 2*x >= a*a*b:
    h = 2*(a*a*b-x)/(a*a)
    print(degrees(atan(h/a)))
else:
    l = 2*(a*a*b-x)/(a*b) - a
    print(degrees(atan(b/(a-l))))

Buggy python submission (verdict: Runtime Error):
import math
a, b, c = map(int, input().split())

# 容器に入っている水が半分以下の場合に困る
a = [2]
if a*a*b > 2 * c:
    print(a[4])
    h = (2*c)/(a*a)
    print(math.degrees(math.acos(h/a)))
else:
    h = 2*(a*a*b-c)/(a**2)
    print(math.degrees(math.atan(h/a)))


Fixed submission:
from math import atan, degrees
a, b, x = map(int, input().split())

if 2*x >= a*a*b:
    h = 2*(a*a*b-x)/(a*a)
    print(degrees(atan(h/a)))
else:
    l = 2*(a*a*b-x)/(a*b) - a
    print(degrees(atan(b/(a-l))))

Buggy python submission (verdict: Runtime Error):
import math
a, b, c = map(int, input().split())

# 容器に入っている水が半分以下の場合に困る
if a**2*b > 2 * c:
    h = (2*c)/(a**2)
    print(math.degrees(math.acos(h/a)))
else:
    h = 2*(a**2*b-c)/(a**2)
    print(math.degrees(math.atan(h/a)))


Fixed submission:
from math import atan, degrees
a, b, x = map(int, input().split())

if 2*x >= a*a*b:
    h = 2*(a*a*b-x)/(a*a)
    print(degrees(atan(h/a)))
else:
    l = 2*(a*a*b-x)/(a*b) - a
    print(degrees(atan(b/(a-l))))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
L = list(map(int, input().split()))

L.sort()
ans = 0
for i in range(N):
    for j in range(i+1, N):
        lower_bound = bisect.bisect_left(L, L[i]+L[j])
        for k in range(lower_bound):
            if k == i or k == j:
                continue
            if L[i]+L[j] > L[k] and L[i]+L[k] > L[j] and L[j]+L[k] > L[i]:
                ans += 1
        # print(L[i], L[j])
        # print(bisect.bisect_left(L, L[i]+L[j])-2)
        # ans += max(bisect.bisect_left(L, L[i]+L[j])-2, 0)
print(ans//3)


Fixed submission:
import bisect
N = int(input())
L = list(map(int, input().split()))

L.sort()
ans = 0
for i in range(N):
    for j in range(i+1, N):
        lower_bound_i_plus_j = bisect.bisect_left(L, L[i]+L[j])
        ans += lower_bound_i_plus_j - (j+1)

print(ans)
Buggy python submission (verdict: Runtime Error):
from scipy.sparse.csgraph import floyd_warshall

# ダイクストラではなくワーシャルフロイドで解く
N, M, L = map(int, input().split())
# graph = [[] for _ in range(N)]
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    if c > L:
        continue
    distant[a][b] = c
    distant[b][a] = c

distant = floyd_warshall(distant)
another = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if distant[i][j] <= L:  # 行けるところまでいくという印象
            another[i][j] = 1
another = floyd_warshall(another)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    if another[i][j] == float("inf"):
        print(-1)
        continue
    print(int(another[s][t])-1)
    # if distant[s][t] == float('inf'):
    #     print(-1)
    #     continue
    # print(int(distant[s][t])//L + min(1, int(distant[s][t]) % L) - 1)
# 燃料が4で
# 1 -> 4 -> 2
# のとき、距離は7だから一見すると補給回数は1で良さそうだけど、実は2回必要
# 今、２点間の最小距離を求めておいて、もう一つのグラフは「最短距離がL以下の2点に辺(重み1)を張る」


Fixed submission:
from scipy.sparse.csgraph import floyd_warshall

# ダイクストラではなくワーシャルフロイドで解く
N, M, L = map(int, input().split())
# graph = [[] for _ in range(N)]
distant = [[float('inf')]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    if c > L:
        continue
    distant[a][b] = c
    distant[b][a] = c

distant = floyd_warshall(distant)
another = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if distant[i][j] <= L:  # 行けるところまでいくという印象
            another[i][j] = 1
another = floyd_warshall(another)
Q = int(input())
for _ in range(Q):
    s, t = map(lambda x: int(x)-1, input().split())
    if another[s][t] == float('inf'):
        print(-1)
        continue
    print(int(another[s][t])-1)
    # if distant[s][t] == float('inf'):
    #     print(-1)
    #     continue
    # print(int(distant[s][t])//L + min(1, int(distant[s][t]) % L) - 1)
# 燃料が4で
# 1 -> 4 -> 2
# のとき、距離は7だから一見すると補給回数は1で良さそうだけど、実は2回必要
# 今、２点間の最小距離を求めておいて、もう一つのグラフは「最短距離がL以下の2点に辺(重み1)を張る」
Buggy python submission (verdict: Runtime Error):
S = str(input())
K = int(input())

# now_s = S[0]
# for i in range(1, len(S)):
#     if now_s == S[i]:
#         cnt += 1
#     now_s = S[i]

cnt = 0
ruisekiwa = [1]
now_s = S[0]
for i in range(1, len(S)):
    if now_s == S[i]:
        ruisekiwa[-1] += 1
    else:
        ruisekiwa.append(1)
    now_s = S[i]

for i in range(len(ruisekiwa)):
    cnt += ruisekiwa[i]//2

cnt = cnt * K

if S[0] == S[-1] and S[-2] != S[-1]:
    cnt += K-1

print(cnt)


Fixed submission:
S = str(input())
K = int(input())

# now_s = S[0]
# for i in range(1, len(S)):
#     if now_s == S[i]:
#         cnt += 1
#     now_s = S[i]

if len(S) == 1:
    print(K//2)
    exit()


cnt = 0
ruisekiwa = [1]
now_s = S[0]
for i in range(1, len(S)):
    if now_s == S[i]:
        ruisekiwa[-1] += 1
    else:
        ruisekiwa.append(1)
    now_s = S[i]

if len(ruisekiwa) == 1:
    if ruisekiwa[0] % 2 == 0:
        print(ruisekiwa[0]//2*K)
        exit()

    # 文字数が奇数
    if K % 2 == 0:
        cnt += (ruisekiwa[0]//2 + 1) * (K//2)
        cnt += (ruisekiwa[0]//2) * (K//2)
    else:
        cnt += (ruisekiwa[0]//2) * (K//2 + 1)
        cnt += (ruisekiwa[0]//2 + 1) * (K//2)
    print(cnt)
    exit()



cnt = 0
for i in range(len(ruisekiwa)):
    cnt += ruisekiwa[i]//2

# 先頭と末尾が違うなら問題ない
if S[0] != S[-1]:
    print(cnt*K)
    exit()




# 先頭と末尾が同じ場合を考える

# 先頭が偶数, 末尾も偶数回数
if ruisekiwa[0] % 2 == 0 and ruisekiwa[-1] % 2 == 0:
    print(cnt * K)
    exit()
# 先頭が偶数, 末尾が奇数
if ruisekiwa[0] % 2 == 0 and ruisekiwa[-1] % 2 == 1:
    print(cnt * K)
    exit()
# 末尾が偶数なら末尾を変えれるから嬉しい
# 先頭が奇数, 末尾が偶数
if ruisekiwa[0] % 2 == 1 and ruisekiwa[-1] % 2 == 0:
    print(cnt * K)
    exit()

# 偶は先頭を変える必要があるから、嬉しい

# 先頭が奇数回数続いていて, 末尾も奇数回数
if ruisekiwa[0] % 2 == 1 and ruisekiwa[-1] % 2 == 1:
    # if K % 2 == 1:
    #     print(cnt * (K//2+1) + (cnt+1) * (K//2))
    # else:
    #     print(cnt * (K//2) + (cnt+1) * (K//2))
    # exit()
    print((cnt+1) * K -1)
    exit()
    # ここを直した, waが減った