結果

問題 No.884 Eat and Add
ユーザー lam6er
提出日時 2025-03-31 17:37:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 90 ms / 1,000 ms
コード長 2,134 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 77,296 KB
最終ジャッジ日時 2025-03-31 17:37:55
合計ジャッジ時間 1,564 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    s = sys.stdin.read().strip()
    reversed_s = s[::-1]
    
    # Initialize carry0 and carry1 (steps needed for carry_in 0 or 1)
    carry0 = 0
    carry1 = float('inf')
    
    for c in reversed_s:
        current_bit = int(c)
        new_carry0 = new_carry1 = float('inf')
        
        # Process possible transitions from previous carry_in 0
        if carry0 != float('inf'):
            s = current_bit + 0
            if s == 0:
                if carry0 < new_carry0:
                    new_carry0 = carry0
            elif s == 1:
                # Subtract 1: carry_out 0, steps +1
                if carry0 + 1 < new_carry0:
                    new_carry0 = carry0 + 1
                # Add 1: carry_out 1, steps +1
                if carry0 + 1 < new_carry1:
                    new_carry1 = carry0 + 1
            elif s == 2:
                # This case should not happen since s = 0 + 0 = 0, but current_bit can't be 2
                pass  # impossible
        
        # Process possible transitions from previous carry_in 1
        if carry1 != float('inf'):
            s = current_bit + 1
            if s == 0:
                # No action needed, carry_out 0
                if carry1 < new_carry0:
                    new_carry0 = min(new_carry0, carry1)
            elif s == 1:
                # Subtract 1: carry_out 0, steps +1
                if carry1 + 1 < new_carry0:
                    new_carry0 = carry1 + 1
                # Add 1: carry_out 1, steps +1
                if carry1 + 1 < new_carry1:
                    new_carry1 = carry1 + 1
            elif s == 2:
                # Subtract 2: steps +1, carry_out 0
                if carry1 + 1 < new_carry0:
                    new_carry0 = carry1 + 1
                # Do nothing, carry_out remains 1, steps same
                if carry1 < new_carry1:
                    new_carry1 = carry1
        
        carry0, carry1 = new_carry0, new_carry1
    
    # After processing all bits, handle any remaining carry
    answer = min(carry0, carry1 + 1)
    print(answer)

if __name__ == "__main__":
    main()
0