オリンピック趣味。 廃棄物処理タスク

こんにちは オリンピック趣味があります。 ここで、olympiadプログラミングタスクを選択し、分析し、可能なソリューションを開発し、計画を実施し、裁判所に送ります。 問題の状態を理解するためには、c、c ++、java、pascal、忍耐、器用さ、および英語の基本知識のいずれかのプログラミング言語の知識が必要になりますが、最後の点はオプションですが、私はロシア語で状態を自由に言い直します。

自分を伸ばすのを忘れましたか？ 忘れてしまった場合は、すぐにウォームアップして、戻ってきてください。

サイトhttp://uva.onlinejudge.orgからタスクを取得することを思い出してください。今日では、ランダムな選択がタスク番号154 （廃棄物処理の問題）に当てはまりました。

問題条件の簡単な翻訳（無料翻訳）：

Kerbsideガベージコレクションテクノロジーがニュージーランドに到着しました。 異なる色の5つのごみ箱：赤（赤）、オレンジ（オレンジ）、黄色（黄色）、緑（緑）、青（青）、5種類の廃棄物を識別：プラスチック廃棄物（プラスチック）、ガラス（ガラス）、アルミニウム（アルミニウム）、スチール（スチール）、紙（新聞）。 残念ながら、都市間の調整は行われなかったため、各都市はカラーバスケットに任意の種類の廃棄物を割り当てました。 政府は、重要ではないすべてのタスク（医療、社会保障、教育の再編成など）を解決できたため、他の問題に取り組むことにしました。 環境保護大臣は、廃棄物の種類の色付きバスケットへの適合を規制する文書を議会に提出しましたが、このため、彼は色ごとに廃棄物の独自の分布を選択する必要があります。 民主主義の支持者である彼は、ケルプサイドを使用するすべての都市を探索しました。 彼は、廃棄物の種類を色付きのバスケットに一致させるスキーム（全国共通）を使用して、変化が最も少ない都市を選択したいと考えています。 民主主義によれば、都市の大きさは重要ではありません：1都市-1票。

各都市の色ごとの廃棄物の種類の分布に関するデータを考慮し、どのスキームを選択すべきかを決定するプログラムを作成する必要があります。 常に明確なリーダーがいることに留意してください。

入力データ ：一連のブロック。 各ブロックには、色ごとに廃棄物の種類の分布を表す複数の行が含まれ、各都市に1行が含まれます。 最大100の都市があり、各ブロックは文字「e」で始まる行で終わります。 入力の終わりには、1文字の文字列「＃」が付いています。

出力 ：着信ブロックごとに、配布スキームを参照として選択する都市のシリアル番号を表示する必要があります。

:
r/P,o/G,y/S,g/A,b/N
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
e
r/G,o/P,y/S,g/A,b/N
r/P,y/S,o/G,g/N,b/A
r/P,o/S,y/A,g/G,b/N
r/P,o/G,y/S,g/A,b/N
ecclesiastical
#

:
1
4

自分の能力をテストしたい人のために、この場所で中断して問題に対する独自のソリューションを作成し、戻って自分の考えと私たちの考えを比較することをお勧めします。

この問題に対する最初の（間違った）解決策は、ほとんど瞬時に思い浮かびましたが、これは次のとおりです。

1. 各色について、最大数の都市でこの色で表される廃棄物の種類を選択します
2. 段落1で選択された種類の廃棄物のカラーマッチングスキームを作成します。
3. 色ごとの廃棄物の種類の分配スキームがパラグラフ2からのスキームにできるだけ類似している都市を選択してください

残念ながら、参照スキーム（パラグラフ2で選択）と同じ類似性を持つ都市が見つかる場合があるため、この決定は間違っていることが判明しました。 これは反例です：

r / P、o / G、y / S、g / A、b / N
r / P、o / S、y / A、g / N、b / G
r / S、o / G、y / P、g / N、b / G
r / A、o / S、y / P、g / N、b / G
r / G、o / S、y / P、g / A、b / N

パラグラフ2による参照図：
r / Po / S、y / P、g / N、b / G

2番目と4番目の都市は、開発されたスキームと同様に似ています。トピックは、4番目の都市を選択した場合、他の都市の変更数は2番目の都市を選択した場合より少なくなります。

2番目のオプション ：すべての都市が順番に標準として選択された場合に必要な変更の数を計算することにしました。 つまり 各都市について、他のすべての都市との合計差を計算しました。

最初は、そのような解決策は最適ではなく、制限時間を確実に超えると思われました。 しかし、各都市と他のすべての都市との間の差異の数のこの計算にかかる時間を推定してみましょう。

各都市は他のすべての都市と比較する必要があり、各色について5つの比較があります。 各都市の5（n-1）比較。nは都市の数です。 合計すると、すべての都市で5n（n-1）回の比較があります。 100を超える都市がないという事実を考慮すると、比較の数は5 * 100 * 99 = 49500を超えません。 比較操作には、各都市のカウンターの差を増やすための操作も伴います。 しかし、たとえ最悪の条件下でも、合計で49,500回の比較と49,500回の操作による単位の追加を超えることはありません。 最も複雑なテストであっても、アルゴリズムが非常に短時間で実行されることが明らかになります。

例の1つと、ソリューション1に対する前の反例の差の数を計算してみましょう。

スキーム	他の都市との違いの数
r / P、o / G、y / S、g / A、b / N r / G、o / P、y / S、g / A、b / N r / P、y / S、o / G、g / N、b / A r / P、o / S、y / A、g / G、b / N	1 + 2 + 1 + 2 + 1 = 7 <-最適なオプション 3 + 3 + 1 + 2 + 1 = 10 1 + 2 + 1 + 3 + 3 = 10 1 + 3 + 3 + 3 + 1 = 11
r / P、o / G、y / S、g / A、b / N r / P、o / S、y / A、g / N、b / G r / S、o / G、y / P、g / N、b / G r / A、o / S、y / P、g / N、b / G r / G、o / S、y / P、g / A、b / N	3 + 3 + 4 + 3 + 3 = 16 3 + 2 + 4 + 2 + 2 = 13 4 + 3 + 2 + 2 + 2 = 13 4 + 2 + 2 + 2 + 2 = 12 <-最適なオプション 4 + 2 + 2 + 3 + 3 = 14

実際には、計画を実行し、 裁判官にそれをもたらすことは残っています。 そして、C ++での私のソリューションです。

受け入れられました（0.012）。 頑張って