Clever Geek Handbook

オリンピック趣味。 ウォームアップ

趣味として、オリンピアードのプログラミングの問題を解決します。 これは、毎日の問題から気を散らすのに役立ち、あなた自身のアストラルプレーンで世界をあと1時間残すことができます。 私の脳は、この趣味のおかげで、常に運動状態にあります。



私は、アルゴリズム、考え、結果を共有し、問題を解決する私の方法に対する質の高い批判を得ることができればいいと思いました。

私たちはタスクを引き受け、それを部分的に分解し、分析し、さまざまなソリューションを発明し、最適なソリューションを選択して、「優れた裁判官」を裁判所に持ち込みます。 多くの人にとって、私の意見では、そのような時間のアンロードは非常に便利ですが、誰かが競争して自分のアルゴリズムを考え出すことに興味があるだけです。



サイトhttp://uva.onlinejudge.org/からタスクを取得します。このサイトでは、あらゆる好みに合わせてかなり大量のタスクが収集されており、ソリューションを確認できます。 ランダムに選択し、開始したものを常に最終決定に持ち込みます。最終決定には、「Accepted」マーク（Accepted）が付けられます。 これらの問題を解決するには、プログラミング言語の1つ、c、c ++、java、pascalの知識だけでなく、英語の忍耐力、論理、および基本的な知識も必要です。 タスクの条件を英語で取得します。



そのため、「初心者向け」セットの簡単なタスクから始めて、能力をテストするためのウォームアップを行います。



問題の状態を簡単に翻訳してください（無料翻訳）：

政府は、監視できるようにすべての人々にタグを付けることにしました。 これを行うには、小さなコンピューターを各人の左手首に埋め込みます。 このコンピューターには、あらゆる種類の個人情報と、動きを制御する送信機があります。

各コンピューターには、小文字の英字（26文字）から作成された50文字以下の一意の識別コードが含まれています。 コードの文字セットは非体系的に選択されます。

文字セットとして3文字の「a」、2文字の「b」、1文字の「c」が選択されたとします。 これらの条件下で、60種類の識別コードを作成できます。



abaabc

abaacb

アババク



これらは、上記の条件に基づいて3つの可能なコードであり、アルファベット順にリストされています。

これらの識別コードの生成に役立つプログラムを作成する必要があります。 プログラムは、一連の文字（繰り返し可能な50文字以下の小文字）を受け入れ、次の識別コードが存在する場合はアルファベット順に印刷する必要があります。 特定のコードが特定の文字セットの最後（アルファベット順）である場合、「No Successor」を出力します。

入力には一連の行が含まれ、各行は識別コードを表します。 記号「＃」は入力の終わりを示します

出力には、入力コードごとに次のコードが1つ含まれている必要があります。


abaacbが入力に供給されると、プログラムはababacに応答するはずです。



この場所では、興味のある方は記事をまとめて、自分で問題を解決してください。 「受諾済み」を受け取ったとき、あなたは軽い精神的なリフトを感じ、活力を高めることを保証します。



明らかに、これは「順列」の分野からの問題です。 ababacは、 abaacbに続く次の辞書式再配置です 。 私の意見では、このアルゴリズムはここで非常によく説明されているので、特に分析しません。 アルゴリズムの主なステップを自分で書きましょう。

  1. プログラムの最初のステップで、配列の末尾から移動し、隣接する要素を比較します。前の（配列内の位置による）要素が次の要素よりも大きい場合は、次に進み、小さい場合は停止してその数（m）を記憶し、この要素が変更されます。
  2. m番目の左側の要素は変更できません。 右側の要素の中から、要素（k）を選択する必要があります。これは、m番目の場所になります。 これは、m番目よりも大きい要素の中で最小の要素です。
  3. m番目とk番目の要素を変更します。
  4. 新しいm番目の要素の右側にある要素を昇順でソートすることは変わりませんが、 それらは降順で並べられており、ラップするだけです。


考慮に入れる必要がある主なことは、次の順列が見つからなかった場合、「後継者なし」を返す必要があるということです。



3秒の制限時間を超えないように、最悪の条件下でプログラムがどれだけ長く動作するかを評価するだけです。 Nが入力シーケンスの文字数であるとします。 最悪の条件下では、最初のステップで、プログラムはN個の比較を実行する必要があります（すべての要素は昇順で配置されます）。 2番目のステップで、最小値の検索が実行されます-これはN回の比較です。 3番目と4番目の手順では、N個の要素を交換します。これには、配列に対するN回の読み取り/書き込み操作が必要になります。 その結果、2N回の比較とN回の書き換えが得られます。 Nが50（問題の状態）以下であれば、アルゴリズムの操作には数ミリ秒かかります。



さて、 それを取りに行きましょう。 私のC ++ソリューションはここからダウンロードできます 。



承認済み（0.008）。 あなたにも幸運を！


More articles:


All Articles