AtCoder Beginner Contest 033

C - 数式の書き換え


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

次のような制約を満たす数式 S が与えられます。

  • 演算子は + (加算) と * (乗算) のみからなる。乗算を優先して計算する。
  • 括弧は存在しない。
  • それぞれの項は、 1 桁の整数である。

例えば、1+3*4*01+2+3+4+5 などの数式はこの条件を満たしますが、12+3+54*6*7-3(3+4)*5+2 のような数式は 条件を満たさないため、入力として与えられません。

あなたは、この数式のうち数字の部分をいくつか選んで 0 に書き換えることで、この式の値を 0 にしたいです。式の値を 0 にするために 0 に書き換えなければならない数字の個数の最小値を求めてください。


入力

入力は以下の形式で標準入力から与えられる。

S
  • 1 行目には、問題文の条件を満たす数式 S (S の長さは 1 以上 100,000 以下)が与えられる。

出力

0 に書き換えなければならない数字の個数の最小値を 1 行に出力せよ。

出力の末尾にも改行を入れること。


入力例 1

0+0+2*0

出力例 1

0

すでに与えられた数式は、 0 + 0 + 2 * 0 = 0 であるので、数字を書き換える必要はありません。


入力例 2

3*1+1*2

出力例 2

2

たとえば、入力の 1 文字目と 5 文字目を 0 に書き換えることで、 0 * 1 + 0 * 2 = 0 となり、値が 0 になります。


入力例 3

3*1*4+0+2*0+5*2+9*8*6+1+3

出力例 3

5

Submit提出する