新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
切手
問題 
切手収集(Philately)は遅く(lately)なったかい？
あなたは新しい郵便管理ソフトウェアを制作するために、ラリタニアン郵便サービス(RPS)に雇われている。そのソフトウェアは顧客の必要な額に応じて切手を組みあわせて、ストックとする。
ラリタニアには切手収集家が多い。彼らのためのサービスとして、RPSは切手の組みあわせを、できる限り多くの種類の切手から構成したい。実は、RPSは顧客を満足させるために、同じ額だが違う種類の切手を発行することで知られている。これらは価格は同じだが、違う種類と見なす。RPSが発行する切手の種類は多くても25種類である。
お金を節約するため、RPSは可能な限り切手の発行数を少なくしたい(切手の種類を最大化するという制約のもとで)。それと、RPSは同時に4つより多くの切手を売ることはない。
入力
あなたのプログラムに与えられる入力は2つ行からなる2つの正整数列であり、これがファイルの終わりまで繰り返す。最初の数列は発行可能な切手の価格であり、2番目の数列はそれぞれの顧客が必要としている額である。例:
1 2 3 0 ; 3つの異なる種類の切手。 7 4 0 ; 2人の顧客。 1 1 0 ; また別の切手。2つの同じ額の切手。 6 2 3 0 ; それに対応する3人の顧客。
注意: この例におけるコメントはデータファイルの一部ではない。データファイルは整数のみを含む。
出力
それぞれの顧客について、最大4つの切手で顧客のニーズにちょうど一致するような「最良の」組みあわせを出力すること。もしそのような組みあわせが存在しなければ、「none」と出力すること。
「最良の」組みあわせとは、使用する切手の種類を最大化する組みあわせとして定義される。もし使用する切手の種類を最大にする組みあわせが複数ある場合は、その中で切手の総数が最少であるものが良い。そのようなものが複数ある場合は、より高額な切手を含むほうが良い。その条件ですら同じになるようであれば、「tie」と出力せよ。
例えば、さきのサンプル入力に対しては、出力は次のようになる:
7 (3): 1 1 2 3 4 (2): 1 3 6 ---- none 2 (2): 1 1 3 (2): tie
つまり、あなたはまず顧客の要求を出力し、次に売った切手の種類を出力し、その後に実際に売った切手の額を出力すること。条件を満たす切手の組みあわせが存在しない場合は、例にあるように4つのハイフンを出力すること。条件を最大化する組みあわせが複数ある場合は、売れる切手の種類は出力し、切手の組みあわせは出力しないこと(同様に例を参照)。各行の最後には余計な空白を出力しないこと。
入力例
1 2 3 0 7 4 0 1 1 0 6 2 3 0
出力例
7 (3): 1 1 2 3 4 (2): 1 3 6 ---- none 2 (2): 1 1 3 (2): tie
出典
Pacific Northwest 1998
