結果

問題 No.2397 ω冪
ユーザー lam6er
提出日時 2025-03-20 20:45:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,067 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 300,688 KB
最終ジャッジ日時 2025-03-20 20:45:26
合計ジャッジ時間 5,958 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 14 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def count_trailing_zeros(s):
    cnt = 0
    for c in reversed(s):
        if c == '0':
            cnt += 1
        else:
            break
    return cnt

def decrement_binary(s):
    if s == '0':
        return '-1'  # Error case, shouldn't happen
    s_list = list(s)
    i = len(s_list) - 1
    while i >= 0 and s_list[i] == '0':
        s_list[i] = '1'
        i -= 1
    if i < 0:
        return '-1'  # Underflow, shouldn't happen
    s_list[i] = '0'
    # Remove leading zeros
    new_s = ''.join(s_list).lstrip('0')
    if not new_s:
        return '0'
    return new_s

def get_a(odd_part_str):
    # Decrement the odd_part_str and then divide by 2
    if odd_part_str == '0':
        return '0'
    # Decrement
    s = decrement_binary(odd_part_str)
    if s == '-1':
        return '0'
    # Now divide by 2 (right shift)
    if s == '0':
        return '0'
    divided = s.rstrip('0')
    if not divided:
        divided = '0'
    return divided

def decompose(s):
    trailing_zeros = count_trailing_zeros(s)
    if trailing_zeros == 0:
        odd_part_str = s
    else:
        odd_part_str = s[:-trailing_zeros] if s[:-trailing_zeros] else '0'
    # Get a_str
    a_str = get_a(odd_part_str)
    # Get b_str (trailing_zeros as a binary string)
    if trailing_zeros == 0:
        b_str = '0'
    else:
        b_str = bin(trailing_zeros)[2:]
    return (a_str, b_str)

def compare(n_str, m_str):
    if n_str == '0':
        return m_str != '0'
    if m_str == '0':
        return False
    a_n, b_n = decompose(n_str)
    a_m, b_m = decompose(m_str)
    # Compare f(b_n) vs f(b_m)
    if compare(b_n, b_m):
        return True
    # Check if f(b_m) < f(b_n)
    if compare(b_m, b_n):
        return False
    # If equal, compare a parts
    return compare(a_n, a_m)

# Read input
n = input().strip()
m = input().strip()

# Handle leading zeros in input (but according to problem statement, inputs are binary numbers)
n_clean = n.lstrip('0') or '0'
m_clean = m.lstrip('0') or '0'

if compare(n_clean, m_clean):
    print("Yes")
else:
    print("No")
0