C - Slot Strategy Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 個のリールからなるスロットがあります。
i 番目のリールの配列は文字列 S_i によって表されます。 ここで、S_i は 0, 1, \ldots, 9 がちょうど 1 回ずつ現れる長さ 10 の文字列です。

それぞれのリールには対応するボタンがついており、高橋君は各非負整数 t について、 スロットが回り始めてからちょうど t 秒後にボタンを 1 つ選んで押す（または何もしない）ことができます。
スロットが回り始めてから t 秒後に i 番目のリールに対応するボタンを押すと、 i 番目のリールは S_i の (t\bmod{10})+1 文字目を表示して止まります。
ただし、t\bmod{10} で t を 10 で割ったあまりを表します。

高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。

制約

  • 2\leq N\leq 100
  • N は整数
  • S_i は 0, 1, \ldots, 9 がちょうど 1 回ずつ現れる長さ 10 の文字列

入力

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

N
S_1
S_2
\vdots
S_N

出力

高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを出力せよ。

入力例 1

3
1937458062
8124690357
2385760149

出力例 1

6

高橋君は次のようにそれぞれのリールを止めることでスロットが回り始めてから 6 秒後にリールに表示される文字を 8 で揃えることができます。

  • スロットの回転開始から 0 秒後に 2 番目のリールに対応するボタンを押します。2 番目のリールは S_2 の (0\bmod{10})+1=1 文字目である 8 を表示して止まります。
  • スロットの回転開始から 2 秒後に 3 番目のリールに対応するボタンを押します。3 番目のリールは S_3 の (2\bmod{10})+1=3 文字目である 8 を表示して止まります。
  • スロットの回転開始から 6 秒後に 1 番目のリールに対応するボタンを押します。1 番目のリールは S_1 の (6\bmod{10})+1=7 文字目である 8 を表示して止まります。

5 秒以下で全てのリールに表示されている文字を揃える方法はないため、6 を出力します。

入力例 2

5
0123456789
0123456789
0123456789
0123456789
0123456789

出力例 2

40

全てのリールを止めた上で、表示されている文字を揃える必要がある事に注意してください。

Score : 300 points

Problem Statement

There is a slot machine with N reels.
The placement of symbols on the i-th reel is represented by a string S_i of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Each reel has a corresponding button. For each non-negative integer t, Takahashi can press one of the buttons of his choice (or do nothing) t seconds after the reels start spinning.
If the button for the i-th reel is pressed t seconds after the start of the spin, the i-th reel will stop to display the ((t\bmod{10})+1)-th character of S_i.
Here, t\bmod{10} denotes the remainder when t is divided by 10.

Takahashi wants to stop all reels to make them display the same character.
Find the minimum number of seconds needed to achieve his objective after the start of the spin.

Constraints

  • 2\leq N\leq 100
  • N is an integer.
  • S_i is a string of length 10 containing each of 0, 1, \ldots, 9 exactly once.

Input

Input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print the minimum number of seconds needed to achieve Takahashi's objective after the start of the spin.

Sample Input 1

3
1937458062
8124690357
2385760149

Sample Output 1

6

Takahashi can make all reels display 8 in 6 seconds after the start of the spin by stopping them as follows.

  • 0 seconds after the start of the spin, press the button for the 2-nd reel, making it stop to display the ((0\bmod{10})+1=1)-st character of S_2, 8.
  • 2 seconds after the start of the spin, press the button for the 3-rd reel, making it stop to display the ((2\bmod{10})+1=3)-rd character of S_3, 8.
  • 6 seconds after the start of the spin, press the button for the 1-st reel, making it stop to display the ((6\bmod{10})+1=7)-th character of S_1, 8.

There is no way to make all reels display the same character in five seconds or less, so the answer is 6.

Sample Input 2

5
0123456789
0123456789
0123456789
0123456789
0123456789

Sample Output 2

40

Note that he must stop all reels to make them display the same character.