ロシアコードカップ2013-2回目の予選ラウンドのタスクの分析

したがって、ロシアコードカップの2回目の予選ラウンドが通過しました。 5月の休日、多くはどこかに行きました...しかし、資格を得るために、第2予選の参加者は競争しなければなりませんでした。
前のラウンドと同様に、ソリューションを送信した登録者よりも多くの登録者がいました。 したがって、参加者の中で、少なくとも1つの決定を送信した者のみが反映されます。
2時間で熱と5つのタスクを解決できます：

• 問題A.分子
• タスクB.海戦
• タスクC.渋滞
• タスクD.テーブル
• タスクE.宇宙遠征

条件と解決策-カットの下。

2番目の資格の結果に関する統計。
ラウンド中に735人が承認されました。 これらのうち、少なくとも1つのソリューションが536人から送信されました。
合計2707のソリューションが送信されました。
問題の正しい解決策を最初に送信した参加者のニックネームは次のとおりです（括弧内は、ラウンド開始後の時間（分と秒）です）。

• タスクA：レイブラスト（2:56）
• 問題B：ミラン（14:58）
• タスクC： KAN（20:27）
• タスクD： XopEka（51:58）
• タスクE： maria.sharapova（18:45）

このラウンドの参加者の領土分布は次のとおりでした。
ロシア=> 343
ウクライナ=> 78
ベラルーシ=> 29
米国=> 22
カザフスタン=> 16
アルメニア=> 8
ポーランド=> 5
アゼルバイジャン=> 4
ウズベキスタン=> 4
アイルランド=> 3
ジョージア=> 3
キルギスタン=> 3
スウェーデン=> 2
英国=> 2
ドイツ=> 2
モルドバ=> 2
アイスランド=> 1
ベルギー=> 1
パキスタン=> 1
ラトビア=> 1
韓国=> 1
スペイン=> 1
中国=> 1
チェコ=> 1
スイス=> 1
カナダ=> 1
予選では、前回と同様、201人が参加しました。

1. ミハイル・コルパエフ
2. エフゲニー・ソボレフ
3. アンドレイ・グリネンコ
4. エフゲニー・カプン
5. デニス・タンニング
6. アレクセイ・サフロノフ
7. ヴラディスラフ・シモーネンコ
8. アンドリー・パブリスコ
9. エゴール・スヴォーロフ
10. パベル・マブリン

次に、タスクの分析を検討します（分析は、 ロシアコードカップの Webサイトでも入手できます）。
最後の第3予選ラウンドが残ったことを思い出してください。 決勝に参加したい場合は、急いで最終予選を通過し、予選ラウンドに参加できるようにします。

問題A.分子
アイデア： Vitaly Aksenov
条件：アンナマロバ
実装：アンドレイ・コマロフ
分析：アンナマロバ

タスク条件
2秒の制限時間
256 MBのメモリ制限
極秘研究所での最近の研究の結果、新しい物質が発見されました。 この物質の各分子は、2種類の原子で構成されるサイクルを表しています。これを任意に黒と白と呼びます（原子の本名は厳密に守られています）。 トップシークレット反応を実行するには、分子を不安定な状態に移行させて、それぞれが1種類の原子のみで構成される2つの独立した分子に分解できるようにする必要があります。
研究により、各色のすべての原子が連続したブロックを形成すると、分子が分裂することが示されています。
科学者は分子を再配置するために、次の操作を実行できます。原子の連続シーケンスがサイクルから切り取られ、別の場所に挿入されます。 分子の再配置の例を図に示します。

現在、科学者は、記載されている操作の最小数が分子を不安定な状態にする可能性があることを見つけようとしています。 彼らがそれを理解するのを助けてください。

入力形式	入力ファイルの最初の行には、自然数n-調査する必要のある分子の数が含まれています。 次のn行のそれぞれには、1つの分子の説明が次の形式で含まれています。少なくとも3つの文字wとbで構成される行で、それぞれ白と黒の原子を表します。 各文字が各分子に少なくとも1回出現することが保証されています。 すべての分子の全長は200,000を超えません。
出力形式	n行を印刷します。 i番目の行には、i番目の分子が不安定な状態になるために実行する必要がある操作の最小数を出力します。
例	入力データ インプリント 3 wbbw wbbwb wbwbwb 0 1 2

解析

分子内の同じ色のブロックの数をmで示します。 mは偶数であり、黒と白のブロックの数は同じであることに注意してください。 ピースには2つの端があり、2つのブロックに触れるという明らかな事実から、分子の再構成ごとに、各色のブロックの数は1つだけ減少することになります。 次のように、各色のブロック数を正確に1つ減らすことができます。1つのブロックを切り取り、同じ色の別のブロックの中央に埋め込みます。 したがって、科学者は合計でm / 2-1の操作が必要になります。
実行時間O（分子長）。

タスクB.海戦
アイデア： Vitaly Aksyonov
実装： Boris Minaev
分析：ボリス・ミナエフ

タスク条件
2秒の制限時間
256 MBのメモリ制限
PetyaとVasyaは、わずかに修正されたルールで海戦を行います。 Vasyaはすでに10試合連続で負けており、再び負けるつもりはありません。 彼はPetyaの戦闘戦術を分析し、重大な欠陥を発見しました（少なくとも彼はそれを望んでいます）。 フィールドには、AからBセルの長方形の領域があり、ペティアはこれまで10回すべてのゲームで撃ったことはありませんでした。 そのため、Vasyaは3つの最大の船をこの長方形に配置することにしました。
もちろん、Vasyaの計画は広範囲に及びますが、彼は最初にいくつかの小さな問題に対処する必要があります。 たとえば、彼は3隻の船が与えられた長方形に完全に収まるように配置できるかどうかを調べる必要があります。 ルールによれば、船は長方形であり、フィールドの側面に平行に配置する必要があります。 船は90度回転できます。 船は互いに触れることができますが、共通のフィールドセルを持たないようにする必要があります。

入力形式	最初の行には、整数t（1≤t≤105）-テストの数が含まれています。 各テストの説明は4行で構成されています。 最初の要素には、2つの整数AとB（1≤A、B≤109）が含まれます。これは、船舶を配置する必要がある長方形の寸法です。 次の3行には、2つの整数aiとbi（1≤ai、bi≤109）-i番目の船の寸法が含まれています。
出力形式	入力からのテスト回答であるt行を印刷する必要があります。 各テスト出力について、船を配置できる場合は「はい」、そうでない場合は「いいえ」。
例	入力データ インプリント 2 7 7 6 3 6 1 3 3 4 4 5 1 1 1 1 2 はい いや

解析

条件を満たす長方形の配置を見つけたとします。 次に、大きな長方形の一方の側に平行な線があり、小さな長方形の一方が完全に一方の側にあり、他の2つが他方の側に完全にあります。 この事実の証拠を演習として残しましょう。
この事実を利用します。 長方形のすべての可能な回転（大きなものを含む）を調べます。16個しかありません。正しい配置があれば、長方形を分離する水平線（少なくとも1つの回転）があります。 この線の下の長方形をソートし、大きな長方形を水平線で2つの部分に分割します。 選択した長方形の幅が大きく収まるようにし、他の2つを上部に配置できるようにします。
少なくとも1つのケースで長方形を配置できた場合、答えは「はい」です。それ以外の場合-いいえ。

問題C.コーク
アイデア： Vitaly Aksenov
実現：ニコライ・ヴェデルニコフ
分析：ニコライ・ヴェデルニコフ

タスク条件
2秒の制限時間
256 MBのメモリ制限
2050年には、道路の安全性を向上させるために、すべての道路で追い越しが禁止されました。 さらに、Lメートルよりも近い前方の車両に近づくことは禁止されています。 ルールの遵守は、すべての道路に設置されたカメラによって監視されます。 残念ながら、これらの措置は交通渋滞との戦いに完全には役立ちませんでした。
スウィンキン教授は毎朝自宅で仕事をしています。 彼が移動する道路は直線です。 メートルに等しい単位でその上に座標系を導入し、このライン上のセグメントとしてマシンを表し、座標が増加する方向に移動します。
当初、教授の車は道路の始点に位置しているため、その前部は原点にあります。 教授の最高速度は1秒あたりVメートルです。
教授の車に加えて、道路上を移動する車がn台あります。 運転中、各マシンは最大速度で移動しようとします。 車Aが前の車Bに追いつき、前の点Aが後の点Bから正確にLになると、車Aは即座に速度を速度Bに下げ、その後、速度Bのすべての変更を繰り返します。
スウィンキン教授が仕事に就くまでにかかる時間を見つけてください。 これは、彼の車のフロントポイントが座標Sのポイントにあった場合に発生したと考えられています。

入力形式	タスクへの入力には、いくつかのテストスイートが含まれます。 各セットの説明は、複数の行で構成されています。 説明の最初の行には、n、L、S、Vの4つの整数が含まれています（1≤n≤10000、1≤L≤1000、1≤S≤109、1≤V≤100）-教授の前の車の数、マシン間の最小距離メートル単位、家から教授の職場までの距離、メートル/秒単位の教授の車の最高速度。 次のn行には、3つの整数xi、li、vi（1≤xi≤109、1≤li≤10、1≤vi≤100）が含まれます-最初の時点でのi番目のマシンのフロントポイントの座標、長さ、および最大メートル/秒の速度。 マシンは教授のマシンの取り外し順に設定され、最初の瞬間の2つの隣接するマシン間の距離はLメートル以上であることが保証されています。 テストの最後の行には4つのゼロが含まれています。 すべてのテストでの車の総数が10,000を超えない
出力形式	テスト要求ごとに、教授が仕事を始めるまでの時間を秒単位で別々の行に印刷します。 答えは、10-5以下の絶対誤差または相対誤差で推定する必要があります。
例	入力データ インプリント 1 1 10 2 3 1 1 1 1 10 1 3 2 1 1 1 10 2 3 1 2 2 3 15 3 4 1 2 10 3 1 1 3 500 93 123 3 2 0 0 0 0 9.0000000000 10.0000000000 5.0000000000 15.0000000000 191.5000000000

解析
タスクは、教授が自分の仕事に何分かかるかを調べることでした。 ある車が別の車に追いつくと、同じ速度で追いかけます。 次に、最初のマシンの長さはlen _first + L + len _secondで 、 _2番目のマシンはそうではないと想定できます。 i番目のマシンが（i + 1）番目に追いつく時点を考えてみてください。追いつかない場合、この瞬間は無限に発生すると仮定します。 また、教授の車がフィニッシュラインに到達する時点も考慮します。 最初に発生するイベントを選択します。 それが起こる時間を答えに追加します。 このイベントがフィニッシュラインに教授の車が到着した場合、問題は解決します。 それ以外の場合は、上記のルールに従ってマシンを組み合わせて、低次元の問題を解決します。 このフェーズはO（n）で実行されます。 このようなフェーズは合計でnを超えません。
合計稼働時間O（n ² ）。 さまざまなデータ構造を使用して、このソリューションをO（n log n）、さらにはO（n）まで加速できます。

タスクD.テーブル
アイデア： Vitaly Aksyonov
実現： Vitaliy Aksyonov
分析：ヴィタリー・アクショノフ

タスク条件
2秒の制限時間
256 MBのメモリ制限
n×m個のセルで構成される長方形のテーブルを考えます。 各セルは黒または白に塗ることができます。 テーブルの辺に平行な辺を持つ非縮退矩形の角に中心が位置する同じ色のセルが4つない場合、カラーリングは正しいと呼ばれます。
長方形のさまざまな正しい色の数を計算する必要があります。 この数は大きくなる可能性があるため、特定のモジュールrを法として導出する必要があります。
たとえば、2×2の長方形の場合、このような色の数は14です。4つのセルすべてが同じ色で塗られている場合を除き、すべての色が適切です。

入力形式	入力ファイルの最初の行には、自然数t-テスト数（1≤t≤150）が含まれています。 次のt行にはそれぞれ3つの整数が含まれます。n、m、rは、回答を表示するテーブルとモジュールのサイズです。 （1≤n、m、r≤1018）
出力形式	テスト要求ごとに、個別の行に回答を印刷します。
例	入力データ インプリント 2 1 1 2 2 2 1,000,000 0 14

解析
長方形の最小辺nと最大辺mを示します。 テーブルの長辺を水平に配置し、それに応じて短い行を列と呼びます。
考慮すべき3つのケースがあります。
•n =1。すると、答えは2 ^mになります。
•n =2。黒と白の2つの単色カラムしか使用できません。 他のすべての列は2色にする必要があります。つまり、それぞれに2つのオプションがあります。 したがって、答えはC _m ² •2 ^m-1 + C _m ¹ •2 ^m + 2 ^mです。
•n> 2. m> 6の場合、単一の適切なカラーリングがないことに注意できます。 実際、最初の列の色付けと2番目の列の色付けは、2箇所でしか一致しません。 同様に、1番目と3番目のカラーリングも。 また、m> 6の場合、2番目と3番目の色は少なくとも3箇所で一致します。 そして、これは良い着色がないことを意味します。 テーブルのサイズを制限した後、残りの部分では検索をうまく処理できることを理解するのは簡単です。

タスクE.宇宙遠征
アイデア： Vitaly Aksenov
実現：パベル・クロトコフ
分析：パベル・クロトコフ

タスク条件
2秒の制限時間
256 MBのメモリ制限
2345年、人類は最初の宇宙遠征を遠方の惑星ナッペンに送る機会がありました。 それへの道は長く、危険に満ちているので、さまざまな種類の宇宙船をすぐにそれに送ることにしました。
各船は、2種類の燃料のいずれかで動作できます。 船が異なるため、燃料消費量も異なります。 同時に、飛行中、船は2種類の燃料のうち1つだけを使用する必要があります。宇宙で一方から他方に切り替えることは不可能です。
船番号iについて、彼は惑星Nutpenへの道路でaiキロトンの第1タイプの燃料または2キロトンの第2タイプの燃料を費やすことが知られています。 船の設計上の特徴により、それらのいずれについても等式ai + bi = 4kが成り立ち、数kはすべての船で同じです。
遠征隊の命令で、正確にk（n + 1）キロトンの第1タイプの燃料と同量の第2タイプの燃料のキロトンがあります。 ここで、各船が惑星Nutpenに飛ぶ燃料の種類を決定する必要があります。

入力形式	最初の行には、単一の整数t-テストの入力データのセットの数が含まれています。 以下は、入力データセット自体の説明です。 入力データの次のセットの説明の最初の行には、整数n（1≤n≤105）-惑星Noutpenに飛ぶ船の数が含まれています。 次のn行には、2つの非負整数aiおよびbiが含まれます。これは、対応する船で必要な第1および第2タイプの燃料の量です。 aiとbiの合計がすべての船で同じで、4の倍数であり、108を超えないことが保証されています。 1つのテストのすべてのセットのnの合計は、500,000を超えません。
出力形式	入力データの各セットに対して、n個の文字で構成される単一行を出力します。ここで、船番号iが最初のタイプの燃料を使用してNutpenに飛行する場合は記号番号iは記号「1」、燃料を使用する必要がある場合は記号「2」 2番目のタイプ。 各タイプの必要な燃料の量は、k（n + 1）を超えてはなりません。 可能な答えがいくつかある場合は、それらのいずれかを印刷します。 答えが常に存在することが保証されます。
例	入力データ インプリント 2 5 1 3 3 1 2 2 4 0 0 4 1 4 4 12221 2

解析
必要な最初のタイプの燃料の量ですべての船を整理します。 次に、最初のt船の合計aiがk（n + 1）を超えないように、最大​​tを選択します。 これらのt船は最初のタイプの燃料を使用し、残りはすべて2番目のタイプの燃料を使用します。

このアルゴリズムが問題で設定された条件の下で常に答えを見つけることを証明しましょう。 和∑ _{i = 1} ^{t + 1} a _i > n•（k + 1）であることに注意してください。 したがって、任意のi> tに対して、a _i >（n + 1）/（t + 1）が成り立ちます。 したがって、i> tの場合、b _i <4k-（n + 1）/（t + 1）であることがわかります。 2番目の量が指定された表現を超えないことを証明するために残っています。 ∑ _{i = t + 1 ⁿ} b _i <（n-（t + 1）+ 1）•（4k-（n + 1）/（t + 1））≤（n + 1）k。 括弧を開いた後の最後の不等式は、不等式「算術平均マイナス幾何平均」に変わります。 これは、上記のアルゴリズムが常に解決策を見つけることを意味します。

最後の3回目の予選ラウンドが残ったことを思い出してください。 ファイナルに参加したい場合は、予選ラウンドに参加できるように、最後の資格に登録することを急いでください。