結果

問題 No.2398 ヒドラ崩し
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:49:54
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 901 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 82,036 KB
実行使用メモリ 410,148 KB
最終ジャッジ日時 2025-04-15 23:52:01
合計ジャッジ時間 10,927 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def count_trailing_pairs(s):
    count = 0
    i = len(s) - 1
    while i >= 1 and s[i-1] == '(' and s[i] == ')':
        count += 1
        i -= 2
    return count

def is_balanced(s):
    stack = 0
    for c in s:
        if c == '(':
            stack += 1
        else:
            stack -= 1
            if stack < 0:
                return False
    return stack == 0

def is_winning(h):
    k = count_trailing_pairs(h)
    h_prime = h[:len(h) - 2*k]
    if not h_prime:
        return k % 2 == 1
    if len(h_prime) >= 2 and h_prime[0] == '(' and h_prime[-1] == ')' and is_balanced(h_prime):
        h1 = h_prime[1:-1]
        h1_win = is_winning(h1)
        prime_win = not h1_win
    else:
        prime_win = is_winning(h_prime)
    return (prime_win and (k % 2 == 1)) or (not prime_win and (k % 2 == 0))

H = input().strip()
result = is_winning(H)
if result:
    print(0)
else:
    print(1)
0