日曜日、ロシアコードカップのトレーニングウォームアップラウンドが行われました。 最初の場所は、ペルミのミハイル「mmaxio」マヨロフによって撮影されました。 第二-モスクワからイゴール「kraskevich」Kraskevich。 第三-モスクワのバレンタイン「ValenKof」コフマン。 受賞者の皆さん、おめでとうございます！
チャンピオンシップの予選ラウンドを控えています。 最初の予選ラウンドは3月28日18:00モスクワ時間に開催され、選手権への登録は3回目の予選ラウンドが始まる前にサイトhttp://www.russiancodecup.ru/で行われます。
ロシア語コードカップは、ロシア語を話す世界中のプログラマーがスキルをテストし、さまざまな複雑さの元の問題を解決することで習熟度を実証する機会であると同時に、専門のITコミュニティに表明する機会でもあります。 オリンピアードは3段階で行われます：予選ラウンド、予選ラウンド、決勝-それぞれ4から8つの多様なタスクがオリンピアードの参加者に提供されます。 コンテストのタスクと技術部分は、ロシアコードカップの共同主催者であるMail.Ru Groupの専門家とITMO大学の専門家によって提供されます。
次に、ウォームアップラウンドの問題の解決策を説明します。
問題A. バルーン
配列内の異なる数の数を見つけます。 それがk以上の場合、答えでk個の異なる色をダイヤルできます。 kより小さい場合、各色のボールを1つ取り、不足しているボールを勝手に取ります。 並べ替えることで、配列内のすべての異なる番号を見つけることができます。
タスクB. テスト購入
タスクでは、条件に記述されているプロセスをシミュレートする必要がありました。 ボックスを複製します。たとえば、2つの支払い方法を持つ1つのボックスではなく、異なるコストの2つのボックスがあり、そのうち1つしか購入できません。 タイムイベントで並べ替え：現金領収書とボックス。 さらに、最も近い領収書とボックスの時刻が同じ場合、領収書を優先します。 入金イベントごとに、受け取った金額を現在の金額に追加するだけです。 まだ購入していない箱の外観のイベントごとに、十分なお金があるかどうかを確認し、ある場合は箱を購入します。
タスクC. 厳emなパレード
k> n 2または最大10 7までの素数がkより小さい場合、解はありません。他の場合には解があります。
n = p1 s1 ×p2 s2 ×...×pk skの約数の数が（s 1 +1）×（s 2 +1）×...×（s k +1）であるという事実を使用します。
各行と各列で素数のべきのセットが等しくなるように、つまり、それらの数がp1 s1 ×p2 s2 ×...×pk skという形式になるように行列を生成します。ここで、 piはいくつかの素数です。各行と列、およびs iは、すべての行と列の固定数です。
k> nの場合、次のようにn 2- （k-n）マトリックスセルを埋めます。最初のnプライムのi番目の巡回シフトでマトリックスのi番目の行を埋め、残りのk-nプライムでマトリックスの残りのk-nセルを埋めます。 したがって、各行と各列には正確にn個の異なる素数があり、それらの除数の数は同じになります。
k≤nの場合、マトリックスのa [i] [j]番目のセルに（i + j）mod k番目の素数を入れます（ゼロからインデックス付けする場合）。 この充填が目的の結果をもたらすことを確認できます。
タスクD. 手下は楽しい
条件を次のように再定式化します。無向グラフで、最小エッジと最大エッジの重みの合計が最大になるサイクルを見つける必要があります。 まず、関数\ emph {≥xの問題に対する答えが単調であることは事実ですか？に注意してください。 そのため、バイナリ検索を実行できます。 問題に対する答えが≥xであることを確認する方法は？
すべてのエッジからx / 2を引きます。 ここで、最小エッジと最大エッジの合計が0より大きいサイクルの存在を確認する必要があります。非負の重みを持つ最小エッジを取り、その重みをw 1とします。 データ構造\ emph {非結合セットのシステム}に 、重みが-w 1を超えないすべてのエッジを追加します。 その後、エッジw 1を追加します。 追加するときに、エッジの端が同じ接続コンポーネント内にある場合、必要なサイクルが見つかりました。そうでない場合は、まだ存在していません。
この後、アルゴリズムを続行します-重みw 2で次の非負のエッジを取得し、重み-w 2 .. -w 1 -1ですべてのエッジを追加し、エッジw 2自体を追加します。 追加するときに、エッジの端が同じコンポーネントにあった場合、サイクルが見つかりますが、そうでない場合はまだありません。 すべての非負のエッジに対してアルゴリズムを実行し続けます。
タスクE. 宝くじ
すべてのx iが異なる場合、最初に問題を解決します。 リクエストを昇順x iでソートします。 あらゆる瞬間に、配列のどの要素が既にある数で占められているかを知りたい。 最初は、配列の単一の要素がビジーではありません。
配列ができました。いくつかの要素がその中にあります。 応答がx iであるリクエストを処理します。 x j <x iがすでに処理されているすべてのx jに対する要求。 セグメントl i ..r iの占有されていない要素の数を計算します。 cntにします 。 次に、これらのすべての要素に数値を入れて、答えにx icnt- （x i -1）を掛けると言います。cntはcnt番号の順序セットの数で、少なくとも1つの数値はx iに等しくなります。 これらの要素にx iより大きい数を入れることはできません（この場合のリクエストへの応答はx iと等しくなりません）。 したがって、配列は失われませんでした。
すべてのリクエストを処理した後、配列の空の要素に任意の数字を入れることができます。 したがって、答えにk cntを掛けます 。
完全なソリューション：前のケースと同じ方法で問題を解決します。 これでx iを同じにすることができます。 答えがxであるクエリの問題を解決します。 他のセグメントを含むすべてのセグメントを考慮から削除します。 残りの部分では、ダイナミクスをカウントします。dp [i] -長さiのプレフィックスに番号を配置して、番号xが最後になるようにする方法の数。 次に、最後に番号xが検出された位置を反復処理する必要があり、それを位置j （ jとiの間の残りのセルでは厳密にxより小さい）にしますが、セグメントを見逃さないようにする必要があります。 つまり、そのようなセグメント（ l、r ）が存在せず、答えがxであり、 j <l≤r <iであるということです。 この場合、 xは表示されません。
したがって、 dp [i] = sum（j = k..i-1：dp [j]（x-1） i-j-1 、ここでkはセグメントの左境界で、その右境界は位置iとその左にあります最後は位置iに最も近く、そのようなダイナミクスはO（nm）に対して全体的に機能します。
位置iの k値は、位置i-1に何らかのセグメントの終わりがあった場合にのみ、位置i-1と比較して変化することに注意してください。 位置i-1にセグメントの正しいグラジツァがなかった場合、 dp [i] = dp [i-1]×（x-1）+ dp [i-1] = dp [i-1]×x したがって、2つの隣接する右境界線間のダイナミクスの値をx cntとして考慮することにより、漸近性の乗数nを取り除くことができます 。ここで、 cntは何かを置くことができる場所の数です。
結果のソリューションはO（m log n + n）で機能します。