結果
問題 |
No.884 Eat and Add
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()