AtCoder Beginner Contest 033 C - 数式の書き換え
C - 数式の書き換え
解説
解法としては貪欲で、逐次処理ができて空間計算量は$O(1)$。
桁数を決め打ちして答えを10進整数で持つ。
入力は1文字ずつ処理していく。
+
か\n
がきたらその左の項が$0$かそうでないかを見て答えをincrement。
項が$0$かどうかはその項を構成する文字の中に数字0
が含まれるかで判定できる。
掛け算の記号*
や0
以外の数字は処理の上で無視することになる。
実装
提出にはhttps://github.com/kmyk/wrap-brainfuckを用いた。
いたるところコピペなので実装はそう重くない。 10進固定精度整数はincrementしかしないのでトラック数2で実装してある。
>>>
++++++++++>> set zero
++++++++++>>
++++++++++>>
++++++++++>>
++++++++++>>
++++++++++>>
++++++++++>>
>+>+<[>> while flag
,[>+>+>+>+<<<<-]
++++++++++[>->---->---->----<<<<-]
+>[<->[-]]<[- if newline
<<->>
<[
<<<<- incr
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]< carry
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[>>]>>
-]>
]
+>>--[<<->>[-]]<<[- if mult
nop
]
+>>>---[<<<->>>[-]]<<<[- if add
<[
<<<<- incr
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]< carry
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[<+<<+>>>-]<[>+<-]+<<[>>-<<[-]]>>[<->>++++++++++<-]<
[>>]>>
-]>
<+>
]
+>>>>--------[<<<<->>>>[-]]<<<<[- if zero
<[-]>
]
<<]
<<<
[<+<<+>>>-]<[>+<-]<<----------[>>+<<[-]]> >+< is putc flag
[<+<<+>>>-]<[>+<-]<<----------[>>+<<[-]]>
[<+<<+>>>-]<[>+<-]<<----------[>>+<<[-]]>
[<+<<+>>>-]<[>+<-]<<----------[>>+<<[-]]>
[<+<<+>>>-]<[>+<-]<<----------[>>+<<[-]]>
[<+<<+>>>-]<[>+<-]<<----------[>>+<<[-]]>
[<+<<+>>>-]<[>+<-]<<----------[>>+<<[-]]>
>[<+>>>+<<-]<[[-]++++++++++[>++++++<-]>-->[<->-]<.[-]<]>>[-] putc
>[<+>>>+<<-]<[[-]++++++++++[>++++++<-]>-->[<->-]<.[-]<]>>[-]
>[<+>>>+<<-]<[[-]++++++++++[>++++++<-]>-->[<->-]<.[-]<]>>[-]
>[<+>>>+<<-]<[[-]++++++++++[>++++++<-]>-->[<->-]<.[-]<]>>[-]
>[<+>>>+<<-]<[[-]++++++++++[>++++++<-]>-->[<->-]<.[-]<]>>[-]
>[<+>>>+<<-]<[[-]++++++++++[>++++++<-]>-->[<->-]<.[-]<]>>[-]
>[<+>>>+<<-]<[[-]++++++++++[>++++++<-]>-->[<->-]<.[-]<]>>[-]
++++++++++. newline