外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

O - Collatz conjecture, but there is cat

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 425 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

わりとねこくんは、黒板に 22 進数表記で書かれた NN 個の正整数 S1,S2,…,SNS_1, S_2, \dots, S_N を見つけました。
わりとねこくんは、これらの整数が気に入らないので、これらをすべて 11 にしたいと考えています。

正整数 XX に対して、Xが11でない限り以下の操作を行うことができます。

  • XX が偶数ならば、XX を 22 で割る(X←X/2X \leftarrow X / 2)。
  • XX が奇数ならば、XX に 11 を足す(X←X+1X \leftarrow X + 1)。

各整数 SiS_i について、この操作を繰り返してちょうど 11 にするまでに必要な操作回数を求め、その合計値を出力してください。

制約

  • 1≤N≤1051 \le N \le 10^5
  • SiS_i は 0 と 1 のみからなる文字列
  • SiS_i の先頭の文字は必ず 1 である
  • ∑i=1N∣Si∣≤106\sum_{i=1}^N |S_i| \le 10^6
  • NN は整数

入力

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

NN S1S_1 S2S_2 ⋮\vdots SNS_N

出力

すべての整数をそれぞれ 11 にするまでに必要な操作回数の合計値を 11 行に出力してください。

サンプル 1

入力

1
11

出力

3

S1=11(2)S_1 = 11_{(2)} は 10 進法表記で 33 です。
33 に対して操作を行うと、値は以下のように変化します。

  • 33 は奇数なので、11 を加えて 44 になる。
  • 44 は偶数なので、22 で割って 22 になる。
  • 22 は偶数なので、22 で割って 11 になる。

合計 33 回の操作で 11 にすることができるため、33 を出力します。

サンプル 2

入力

2
1010
1111

出力

11

参加受付は終了しました。