ダイヤル式の南京錠がある。この南京錠には、5つのダイヤルと、決定ボタンが用意されている。
5つあるダイヤルを回転させて16進数で5ケタの整数を作り、決定ボタンを押して入力すると、入力した値とパスワードが一致していれば開く仕組みになっている。5つのダイヤルそれぞれには
0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,0,1,2, ...
の順で文字が現れるように書かれている。
持ち主はパスワードを忘れてしまった。しかし、パスワードの5ケタのうち、1つのケタだけが偶数で残り4つは奇数であったことは覚えている。 ただし、偶数とは0,2,4,6,8,a,c,eであり、奇数とは1,3,5,7,9,b,d,fである。
またこの鍵は不良品で、以下の条件でパスワードと異なる数字を入力しても開いてしまうことが分かっている。本来、入力した整数とパスワードが5つのケタすべてについて一致していなければ鍵は開かない。しかし、パスワードの偶数となっているケタがiケタ目だった場合、iケタ目の一致判定を行うとき、その偶数の前後にある奇数が入力されていた場合でもiケタ目は一致していると誤判定されてしまうのだ。
例えば、パスワードが"57677"の南京錠ならば、'6'の前後には'5'と'7'の奇数があるため"57677"のほかに、"57577"や"57777"を入力したときでも開いてしまう。 同様に、パスワードが"130bd"の南京錠ならば、'0'の前後には'1'と'f'の奇数があるため"130bd"のほかに、"13fbd"や"131bd"を入力したときでも開いてしまう。
今、パスワードの候補がN個あり、それらのうちどれか1つが正解のパスワードであることが分かっている。しかたがないので持ち主は、鍵が開くまで何度も整数を入力して試し続けることにした。持ち主はできるだけ決定ボタンを押す回数を少なくしたい。
持ち主が最適な戦略をとったとき、最大で何回決定ボタンを押さなければならないだろうか? その回数を出力せよ。 また、実際に最大となるときに入力する整数の集合を昇順に出力せよ。 答えが一意に定まらない場合は、辞書順で最小となるものを出力せよ。
入力は以下の形式で与えられる。
N password1 password2 ... passwordN
1行目にNが与えられる。
2行目からN+1行目のi行目には、パスワードの候補を表す5ケタの16進数を表す文字列passwordiが与えられる。
鍵が開くまでに最適な戦略をとったときの決定ボタンを押す回数の最大値を1行に出力せよ。 続いて、最大となるときに入力する整数の集合を昇順に出力せよ。 もし、答えが一意に定まらない場合は、辞書順で最小となるものを出力せよ。
1 0111f
1 0111f
3 57567 57587 0d351
2 0d351 57577
6 1811b 1a11b f3b1e f3b1c b0df3 bedf3
3 1911b bfdf3 f3b1d