MIPTおよびMSTUと連携したCompany Mail.Ru Group。 N.E.バウマンは、 テクノキューブ -8年生から11年生までの学生向けの最初のプログラミングオリンピアードを要約しました。 ロシアの20以上の都市の生徒とCISは、最も才能のある若いプログラマーの称号をめぐって戦いました。 合計で2132名の参加者がオリンピアードに登録し、113名がフルタイムの決勝戦に参加しました。これはMSTUの2つの会場で同時に行われました。 N. E.バウマンとMIPT。 この賞は、Mail.Ru Groupのオフィスで開催されました。 オリンピックはCodeforcesプラットフォームで開催されました。



連中は3つの問題を解決するために3時間を費やしました。これはロシアの主要な技術大学の教師と専門家でした。 最後の、最も困難なのは、参加者の一人、最終的には優勝したVladislav Makeevのみです。 合計で、オリンピアードの27人の参加者が勝者となり、I、II、III度の卒業証書をそれぞれに分けました。 受賞者（Iの学位）は入学のためにさらに8ポイント、IIおよびIIIの学位の保有者-それぞれ6ポイントを受け取りました。 1位はVladislav Makeev（モスクワ、11年生）、2位-Alexandra Drozdova（ニジニノヴゴロド、10年生）、3位-Grigory Reznikov（モスクワ、11年生）です。 受賞者の完全なリストはこちらから入手できます 。 この投稿では、フィナーレの目的とその解決策を理解することをお勧めします。

問題A.レベル80プログラマー

アイデアの著者：ミハイル・ミルザヤノフ、SSU
開発：アレクサンダー・フロロフ、SSU
トピック：モデリング

状態

kレベルのプログラマになることを夢見ています。 彼は計画を実行するためにn日を持っています-彼のレベルを1日からk日まで増加させます。 レベルxからレベルx + 1に進むには、レベルxを受け取った瞬間からx個の問題を解決する必要があります。

i日目には、 a _iのタスクが1つの有名なサイトで公開され、それらのすべては公開の日にのみ解決に使用できます。 毎日、Vasilyは次々に問題を順番に解決しますが、 i日目には_i個の問題しか解決できません。 最後のレベルxを受け取った瞬間からVasilyによって解決されたタスクの総数がxに等しくなるとすぐに、彼は停止し、その日はそれ以上の問題を解決しません。 この場合、1日の終わりに、彼は次のレベルx + 1に移行します。同時に、彼はVasilyがその日に解決できなかった問題を解決することはありません。

次のレベルに移動すると、解決された問題は蓄積されません。つまり、各xがレベルx + 1に移動するため、Vasilyはxの問題を解決する必要があります。

Vasilyは1からnまでいつでもクラスを開始できますが、彼はkレベルのプログラマーになる日と勉強を開始する日との差を最小限に抑えたいと考えています。



入力データ

入力の最初の行には、2つの整数nとk （1≤n≤500、2≤k≤n + 1）が含まれています-それぞれ、Vasilyが達成したい合計日数とレベル。

2番目の行には、 n個の整数a ₁ 、 a ₂ 、...、 a _n （1≤a i≤500）が含まれます。ここで、 _aiは、 i番目の日に解決できるタスクの数に等しくなります。

インプリント

単一の整数-Vasilyがプログラミングのk番目のレベルに到達できる最小日数を出力します。

Vasilyが目的を達成できない場合は、-1を印刷します。

解析

まず、問題を解決する過程で休憩を取ることは決して有益ではないことに注意してください。なぜなら、いつでも残っているタスクの余剰は単純に使用できないからです。

したがって、変更する意味があるのは、ポンピングが始まる日だけです。 初日に考えられるすべてのオプションを見ていきましょう。それぞれについて、プログラマーのビルドプロセスをシミュレートします。 このソリューションの複雑さはO（n ² ）です 。これは、開始日nおよび各日に対して可能なオプションであるため、シミュレーションはO（n）の間に行われます。

タスクB.手紙の交換

アイデアの著者：GLEB Evstropov（HSE）およびMikhail Mirzayanov（SSU）
開発：アレクサンダー・フロロフ、SSU
トピック：ハミング距離、カウント

状態

Ivanは新聞を読むのが大好きで、特に政治ニュースとスポーツニュースに興味があります。 また、Ivanにはお気に入りのstringがあります。

Ivanには自由な時間が多く、彼は非常にすばやく読みますが、1日に興味を持っている新聞はそれほど多くありません。 そのため、最近、別の新聞を読んだ後、イヴァンは新聞に書かれたテキストtでのお気に入りの文字列sの出現回数を部分文字列として検討し始めました。 ストリングxのサブストリングは、ストリングxの連続した文字のシーケンスです。

しかし、すぐにイヴァンは出現回数に非常に迅速に対応し始め、次の新聞を読んだ後、新聞tのテキストの変更された行sの出現回数を最大にするように、 k文字以下のお気に入りの行に置き換えることを決めました。

あなたの仕事は、Ivanが新聞tのテキストのk個以下の文字を置換した後、お気に入りの文字列sの最大出現回数を計算することを支援することです。 Ivanは正確にk個の文字を置き換える必要はありません。おそらく、1文字を置き換える必要さえありません。 文字列sの文字を他の文字に置き換えることができます。



入力データ

入力の最初の行には、3つの整数n 、 m 、およびkが含まれています（1≤n≤m≤250、0≤k≤n）-文字列sの長さ、文字列tの長さ、およびIvanがお気に入りの文字列で置き換えることができる文字数それに応じて。

入力の2行目には、空でない文字列sが含まれます。これは、英語のアルファベットのn個の小文字-Ivanのお気に入りの文字列です。

入力の3行目には、英語のアルファベットのm個の小文字で構成される空でない文字列tが含まれます-新聞に書かれたテキスト。 文字列sの長さが文字列tの長さを超えないことが保証されています。

インプリント

単一の整数-新聞tのテキストのk個以下の文字を置換した後のIvanのお気に入りの行sの最大出現数を出力します。

解析

ソース文字列sのすべてのバリエーションを通過し、それらの答えを読み取る単純なソリューションには、指数関数的な複雑さがあります。 ただし、少なくとも1つのオカレンスを持つ異なるバリアントは||より少なくなることに注意してください。 t | -| s | + 1、つまり、文字列sを文字列tに「アタッチ」する方法の数。

計算の順序を変更し、行sから行tへの適用のすべての可能な位置をソートし、それぞれについて、この位置にエントリを取得するために変更する必要がある位置と記号を正確に計算します（またはk個の変更に適合できないと判断します）。 必要な変更をエンコードするには何らかの方法が必要なので、後でアプリケーションの2つの異なる位置で同じ変更が必要かどうかを区別できます。 この問題では、文字列tとsの長さにわずかな制限があったため、ほぼすべての多項式解を使用できました。 たとえば、必要な変更は単に長さの配列として表すことができます| s |。

次に、同じ変更のグループを選択し、同じサイズのグループを見つけます。 これは、ソートやハッシュを使用するなど、さまざまな方法で実行できます。

問題C.賞金

アイデアと開発の著者：Alexey Dmitriev、MIPT
テーマ：数学

状態

HackerCookは、大規模な賞金プールで壮大なスポーツプログラミングチャンピオンシップを開催しましたが、賞金の分配はまだ発表されていません。 最終的な配布について知られている唯一のことは、上位の参加者が下位の参加者よりも少ない賞金を受け取ることです。

現在、HackerKookの従業員の1人は、友人ができるだけ多くのお金を受け取ることができるように賞金を配布したいと考えています。 従業員がお金を最適に分配する場合、各参加者が受け取る賞金の額を決定します。



入力データ

入力の最初の行には、2つの整数nおよびk （1≤k≤n≤1 000 000）-参加者の総数とHackerCook従業員の友人の数が含まれています。

2行目には、 k個の異なる整数a _i （1≤a i≤n ）が昇順で含まれています（-な開発者の友人が取った場所）。

インプリント

n個の非負整数b ₁ 、 b ₂ 、...、 b _n （ ）、つまり、 i番目の場所に参加した参加者は、 賞金プールの一部。

可能な答えが複数ある場合は、どれでも印刷できます。

出力形式で記述された条件を満たす最適な回答があることが保証されています。

解析

簡単に説明すると、最初の数人の参加者にすべてのお金を均等に分配するためのすべてのオプションを検討します。これらのオプションの少なくとも1つがベストアンサーになります。

それを証明するには？ 最適な答えを検討してください。 その中の2人の参加者AとBに異なる正の金額を受け取ってもらい、収益aとbを示します（その後0 < a < b ）。 少なくともbを受け取った人とb未満を受け取った人のために、すべての参加者を正の金額で分割します。 これらのグループには、それぞれXとYの参加者がおり、その中にそれぞれxとyの友人がいると仮定します（数字xとyの少なくとも1つは正です）。

数kを選択し、最初のグループの各参加者の収益をk / X増やし、2番目のグループでk / Y減らします（合計金額が保存されることに注意してください）。 次に、友人の収益はk（x / X-y / Y）だけ変化します。 正と負のkの両方を選択できるため、変更後に参加者が彼よりも多くのお金を受け取らず、すべての収益が負ではないことに注意してください。 私たちの答えは最適であるため、 x / X = y / Y （それ以外の場合は、目的の符号の数kを選択することで改善できます）。 kを選択して、2番目のグループで参加者の1人のお金が0になるようにします。 プラスの勝利を収めた参加者の数は減少しました。 正の賞金を獲得したすべての参加者が等しくなるまで、このプロセスを繰り返します。

技術的には、タスクは非常に簡単です。シーケンスのすべてのプレフィックスの中で、その中の友人のシェアが最大になるように選択する必要があります。 これは、単純な線形アプローチによって行われ、現在の応答をa / b分数として保存します。

問題D.花

アイデアと開発の著者：ミハイル・ミルザヤノフ、SSU
トピック：欲、イベント処理

状態

Vasyaは3月8日にマーシャに花束を贈りたいと考えています。 彼は街の外の森にある秘密の道を知っています。それに沿って、美しい、そして最も重要なことは、自由な花が咲きます。 パスは直線で表すことができ、Vasyaは最初にポイント0でパスに現れ、花を摘むのに時間を費やすことなく1の速度で移動すると考えることができます。

花番号iは座標x _iのパスのポイントで成長し、Vasyaがそれを拾った後、花はさらにt _i単位の時間生き続けます。 当然、Vasyaはブーケの中に奇数個の花を拾わなければならず、マーシャと会うために彼がそれらをポイント0に持ってきた瞬間にそれらはすべて生きていなければなりません（ i番目の花が摘まれてからt t単位の時間後に正確にもたらされた場合、生きているとは見なされません）。

Vasyaはまっすぐな人間であり、Mashaのためにさえ、彼は2回以上曲がる（つまり、パスに沿って移動方向を変える）準備ができていません。 彼が奇数サイズの最大の花束を集めるのを手伝ってください。



入力データ

入力の最初の行には、単一の整数n （1≤n≤200 000）-パスに沿って成長している花の数が含まれています。

次のn行のそれぞれには、2つの整数x _iおよびt _i （–10 9≤x i≤10 9、0≤t i≤10 ^9）が含まれます_-i番目の花の座標とその後に生存する時間彼はそれぞれ食い物にされます。 1つのポイントで複数の花が成長できます。

インプリント

単一の数字を印刷-花束に花の最大可能な数。 1つの花からも花束を収集できない場合は、0を印刷します。

解析

Vasyaが移動方向を2回以内に変更する準備ができているという条件は、答えの形式を明確に定義します：最初に停止する2つの側面の1つに行き、次に戻り、すべての花を集め、0を通過し、ある点まで反対に行きます、再び向きを変えて0に戻り、パス内のすべての花を再び収集します。 最後のターンの前にポイント0からどれだけ離れるかについては、一方では、戻る途中で収集できる花の数に依存し、他方では、最初のセクションで収集された花の数はすでにフェードします。

一般性を失うことなく、最初にポイント0から左（負の座標）に移動し、次に右に移動したと仮定します。 次に、「世界を回して」、対称問題を解決します。 もちろん、最大サイズの花束を選び、この最大値に最も近い奇数を見つけます。

対応するiについてx _i < t _iの場合、ポイント0の右側にある花はMashaに配信できます。 ポイント0から座標Rまで右に移動します。その後、ポイントiの左にある花iは 、 t _i + x _i -2 R > 0またはR <（ t _i + x _i ）/ 2.したがって、 n個のイベントが正の座標を持つ光線に沿って配置され、それぞれが新しい花を追加するか、削除します。 0から最大イベントの座標に進み、最大の正のバランスを見つけます。 1点および整数点の間にあるイベントを慎重に処理する必要があります（ここでは、すべての座標に2を掛けることで問題が解決されます）。

チャレンジE.バーランドホッケーリーグ

アイデアと開発の著者：Alexander Ostanin、MIPT
トピック：数学、グラフ

状態

バーランドホッケーリーグの選手権では、 nチームが参加しました。 トーナメントはラウンドロビン方式で開催されます。トーナメントには引き分けはありませんが、各チームはそれぞれ1試合のみを行います。 従来のトーナメントとは異なり、バーランドホッケーリーグでの賞金の分配は、チームの最終順位ではなく、勝利数に依存します。 つまり、賞品は、少なくともwゲームに勝ったすべてのチームに授与されます。 ホッケーの専門家ドン・ベリーは、このトーナメントの結果に基づいて、正確にk個のチームが賞品を受け取ることができるかどうか疑問に思っています。 そのようなトーナメントが存在する場合、各試合の勝者を撤回する必要があります。



入力データ

唯一の入力行には3つの数字n 、 w 、 k （2≤n≤1000、0≤w≤n、0≤k≤n）が含まれます-参加チームの数、賞品を受け取るための最小勝利数、および専門家によって予測されるトーナメントの勝者の数。

インプリント

そのようなプロパティを持つトーナメントが存在しない場合、出力の1行に「NO」（引用符なし）を印刷します。
それ以外の場合は、最初の行に「YES」と印刷します（引用符なし）。 次に、長さnの n行を印刷します。それらのi番目のj番目の文字は、チームiとjの間の一致に対応する必要があります。 i = jの場合、対応するキャラクターは0である必要があります。チームiがチームjを破った場合、このキャラクターは1です。それ以外の場合は0です。

解析

より難しい問題を解決します：最初のkチーム間の最小ポイントが可能な限り高く、最後のn-kチーム間の最大ポイントが可能な限り低いトーナメントを構築します（いくつかのトーナメントでは、これらの値の最適な値が同時に達成されると主張されています）。 このトーナメントが答えであるか、答えがありません。

明らかに、最適なトーナメントでは、最初のkチームのそれぞれが最後のn-kのそれぞれに対して勝つ必要があり、最初のすべてのチームがどのようにプレーするか、最後のすべてのチームがどのようにプレーするかを決定する必要があります。 最初のkチーム間のマイクロトーナメントの最小ポイントはできるだけ高く、最後のチーム間のトーナメントでは最大ポイントをできるだけ低くする必要があります。

mチームをトーナメントに参加させ、 mチームを奇数にしましょう。 次に、 m頂点の完全なグラフでは、頂点のすべての角度が偶数になります。これは、オイラーサイクルが含まれていることを意味します（時間O（m ² ）で構築できます）。 サイクルに沿ってエッジを方向付け、エッジが勝者チームから敗者につながると言うと、各チームが正確に（m-1）/ 2回勝ったトーナメントを獲得します。

mを偶数にします。 その場合、すべてのチームで同じポイント数のトーナメントを構築することは不可能であり、最後のチームのポイントは（m-2）/ 2ポイント以下です。 ただし、1つの頂点をスローし、前の段落のアルゴリズムを残りのm -1チームに適用し、残りの半分のチームに勝利チームを設定すると、このプロパティを持つトーナメントを構築できます。 結果のトーナメントでは、チームの半分（m-2）/ 2ポイント、および残りの半分-m / 2ポイント。

最も「偶数」のトーナメントを構築するこの方法は、最初のkチームと最後のn-kチームの両方に適しています。 最後に、それが本当に答えであることを確認します（つまり、最初のチームはすべて少なくともw回勝ち、残りはw回未満勝ちました）。

問題F.カールソン

アイデアと開発の著者：グレブエヴストロポフ、HSE、ミハイルミルザヤノフ、SSU
トピック：欲、動的プログラミング

状態

20年が経ちました。 カールソンは太っていて、もはや飛びません。 子供は仕事を得て、トップマネージャーになり、現在、 n階の巨大な家に住んでいます。

カールソンは子供を訪問することにしました。 もちろん、彼は徒歩で登るつもりはないので、1階でカールソンはエレベーターに入ります。

エレベータのボタンは下から上に配置されているため、高さhの人は1からhまでの階に対応するボタンに到達できます。 i - h _i , , . , i - , i . , .

, , , . i , , i .



入力データ

n h (2 ≤ n ≤ 10 ⁶ , 1 ≤ h ≤ 10 ⁹ ) — , , . h ₁ , h ₂ , ..., h _{n – 1} (1 ≤ h _i ≤ 10 ⁹ ), i - , i - .

インプリント

n – 1 ans ₁ , ans ₂ , ..., ans _{n – 1} , ans _i , , , i - . , i - , , -1 ans _i .

, . , , x , . , , . O(n) .

— , , . , , :

f _i — , , 1 i ;
g _i — , , 1 i ( , ).

a _i i , b _i — . f _i = f _ai + 1, g _i = g _bi + 1, a _i = a _bi , g _i = f _bi + 1 .

, . - , . , i k – 1 + g _i , k — .

G. , ,

: ,

«, , ». n . : , . , ( , , ), . w , — d , — 0 . — .

, , n r , s p . r i - , i - , s — , p — .

, . , , , .



入力データ

n , w d (1 ≤ n ≤ 100 000, 0 ≤ d ≤ w ≤ 10 ₉ ) — , .

n , r, s, p , — .

インプリント

— , .

t . f(t) , ; f( ) . t n , f(t) = 0.

t n . , , r (), : f(t + p) ( — , ), d + f(t + r), w + f(t + s) . - (, t + p ), f(t) = ∞. ; , , f(t) .

. t , f(t) , — , — , . , . O(n ₂ ) .

— . , s , «» , ( ). O(|s|) ; , (, ).

. f , , w f . , f «» : L w ( L – 1).

. , f , , n . .

, Russian Code Cup 2016 !