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