1404 I-Keyboard

原文

時間制限:2000ミリ秒
メモリ制限:32768KB

問題

　あなたたちの大部分は、おそらく携帯電話のキーボードでSMSメッセージを打ったことがあるだろう。このキーボードは長いメッセージを打とうとしたときにとてもいらいらすることがある、なぜなら1文字を打つために1つのキーを何度も打たなければいけないことがあるからである。これはキーボードにおけるキーの数が少ないためである。典型的な携帯電話は12個のキー（とタイピングには使わない他のキー）のみからなり、しかも英語のアルファベットに使われる26文字を打つのには8つのキーしか使わない。標準的なキーとアルファベットは左の図に示す通りである。

　各キーについて3、4文字が割り当てられている。もしあなたが各グループの最初の文字を打ちたければ、キーを1回押す。2番目の文字を打ちたければ、キーを2回押す。他の文字を打つためには、キーを3か4回打たなければならない。このキーボードの作者はキーを押す回数を最小にするキー配置を目指さない代わりに、各キー同じくらいの文字を持つようにキー配置を考えている。しかし、あいにく、一部の文字は他の文字よりより多く打たれる。そのような文字のうちの一部は、標準的なキーボードでは3番目か4番目にあることがある。たとえば、"S"は英語のアルファベットの中ではとてもよく使われる文字だが、打つためには4回キーを押す必要がある。もしキーと文字の対応が次の図ようになれば、このキーボードは平均的な英語の文章を打つのにもっと便利になるだろう。

　ACM社は、新しい携帯電話に最適なキーボードを搭載することにした。今会社には、文字の打たれる頻度が与えられたときに最適なキー配列を見つけるプログラムが必要である。私たちは文字の順番はそのままにする必要がある、なぜなら文字の順番がばらばらだったらユーザーが困るからだ。しかし、私たちは1つのキーにいくつの文字を関連付けてもいい。

入力

　入力の1行目には、正の整数Tがある。Tは、このあとに続くテストケースの数を表している。各テストケースの始めの行には、2つの整数K, L (1 <= K <= L <= 90) が、半角スペースを区切りにして書かれている。Kはキーの数を、Lはキーに関連付けられる文字の数を表している。続く2行のうち、1行目には各キーの名前を表すちょうどK個の文字が、2行目には各文字の名前を表すちょうどL個の文字がある。キーと文字の名前は数字かアルファベット(大文字・小文字を区別する)か、記号文字(ASCIIコードで33～126の文字)で示される。どの2つのキーも同じ名前を持たず、どの2つの文字も同じ名前を持たない。しかし、文字で使われた名前がキーの名前に使われることはある。
　その2行のあとのL行には、各行1つずつ正の整数が書かれている(F1,F2, ..., FL)。 これらの数字が各文字の打たれる頻度を、1文字目から順番に表している。大きい数字は、よりよく使われる文字であることを意味する。どの数字も100000より大きくはない。

出力

　各データセットに対して、最適なキー配置を見つける。最適なキー配置とは、平均的な文章についてもっとも低い"price"を持つキー配置である。そのキー配置のpriceは各文字のpriceの和で示される。文字のpriceは、その文字の打たれる頻度(Fi)とそのキーの位置との積で表される。文字の順番を変えてはいけない。文字のグループ分けは与えられた順番で行う必要がある。
　もし最適なキー配置が複数存在するならば、その中で最後のキーに関連付けられた文字の数をできるだけ多くする。最後のキーも同じならその1つ前のキーをできるだけ多く…と続けていく。

　より形式的には、各文字の位置を表す数列 P1, P2, ..., PLを見つける、ということになる。この数列は次のような条件を満たしていなければならない。

• P1 = 1
• Pi = Pi-1 + 1 または 1 (i > 1)
• Pi = 1 を満たすような i が最大でK個
• 積の和 SP = F1*P1 + F2*P2 + ... + FL*PL が最小になっている
• これらの性質を満たし、なおかつ同じ「積の和」を持つ (SQ=SP) 他のすべての数列Qについて、M < J <= L を満たすすべてのJについてPJ=QJかつ、PM>QMとなるようなMが存在する。

　各テストケースの出力は、Keypad #I:という行で始まる。ここでIとは、1から順番につけていくテストケースの番号である。そのあとにはK行が、入力で与えられたキーの順序と同じ順番で続く。各行は1つのキーの名前と、コロンと、1つのスペースとそのキーに関連付けられた文字のリストから成る。文字のリストは互いに分けることはない。
　各テストケースの終わりには、最後のテストケースも含めて、1行の空行を出力する。

入力の例

1
8 26
23456789
ABCDEFGHIJKLMNOPQRSTUVWXYZ
3371
589
1575
1614
6212
971
773
1904
2989
123
209
1588
1513
2996
3269
1080
121
2726
3083
4368
1334
518
752
427
733
871

出力の例

Keypad #1:
2: ABCD
3: EFG
4: HIJK
5: LM
6: NOPQ
7: RS
8: TUV
9: WXYZ

出典

Central Europe 2000