G - おおきなかずを作った (I made a huge number) Editorial /

Time Limit: 1 sec / Memory Limit: 256 MB

問題文

joishinoお姉ちゃんは、のどかな田舎にある小さな分校にやってきた。
どうやら、この学校では特殊な遊びが流行っているようである。

遊びのルールは以下の通りである。

  • この遊びは、二人で行われる。
  • まず一人が、いくつかの互いに異なる自然数を選び、それらを小さい順に右から左へと並べていき、連結して新たな数を作る。
  • ここでいう自然数とは、1以上の整数で、先頭に来る数字が0でないものとする。つまり、01や0099などは認められない。
    • （例えば、選んだ自然数が、5 18 48 52 ならば、5248185 という数ができる。）
  • そして作った数を、相手に見せる。
  • 見せられた人は、その数を作ることのできる、もともとの数の組をひとつ予想する。
  • 予想した数の組の中で最大の数が、作られる時に使われた数の組の中で最大の数以下ならば、予想した側の勝ち、そうでなければ、数を作った側の勝ちとなる。

    • joisinoお姉ちゃんは、ある小学生とこの遊びをすることになった。
    この小学生は、連休中にやる気を出して、大きな数を作ってきたようである。
    予想する側になったjoisinoお姉ちゃんは、自身のプライドにかけてこの遊びに勝利したいと思った。
    そしてjoisinoお姉ちゃんは、予想する側が最善を尽くすことで必ず勝利できると気づいた。
    そこで優秀なプログラマーであるjoisinoお姉ちゃんは、与えられた数を元に、その数を作ることのできる数字の組のうち、最大の数がとりうる最小の桁数を計算するプログラムを作成することにした。

    入力

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

    . 
    N
S
    • 1行目には、与えられる数の桁数N(1≦N≦10^6)が書かれている
    • 2行目には、N桁の数が書かれている。（この数の先頭の数字が0でないことが保障されている）

    配点

    この問題には部分点が設定されている。

  • データセット1は、N(1≦N≦10^4)を満たし、正解すると15点が得られる。
  • データセット2では追加の制約はなく、正解すると125点が得られる。

    • 出力

    与えられた数を作ることのできる数の組の中で、最大の数の桁数が最も小さくなる場合の、その桁数を1行で出力せよ。
    また、出力の末尾には改行を入れること。

    入力例1

    7
5248185

    出力例1

    2
    • 52 48 18 5 という数の組にしたとき、最大の数(52)の桁数が最小(2桁)になる

    入力例2

    9
123456789

    出力例2

    4
    • 1234 567 89 という数の組にしたとき、最大の数(1234)の桁数が最小(4桁)になる。

    入力例3

    20
49260520598009034978

    出力例3

    8