RCC 2014の3回目の予選ラウンドは5月24日土曜日に行われました。このラウンドには5483人が登録し、1500人以上が参加し、そのうち少なくとも1つの決定が893人の参加者によって送られました。
プリシュチェンコボグダン（レブロン）、リヴィウ国立大学の学生。 Ivan Franko、問題A（三角形）を解決するための2:25分で最初。 4分44秒の問題B（折り紙）は最初にユルダシェフマート（雪だるま）によって解決され、タスクC（ミティアとカウント）は10:34分にマキシムアーメドフ（Zlobober）によって最初に解決されました。 Sergey Kopeliovich（Burunduk1）によって送信され、最後のタスクE（暗号化キー）は、54：38にPavel Ponomarev（pperm）によって最も迅速に解決されました。
3回目の予選ラウンドの結果によれば、不正行為に対する失格はなく、200人の最高のスポーツプログラマーが予選ラウンドに参加しました。
前回の3回の予選ラウンドで予選を通過しなかった参加者は、モスクワ時間6月1日13:00に開催される4回目の予選ラウンドに参加することで、まだラウンドの予選を受けることができます。
ロシアコードカップに参加するには、サイトで登録する必要があります（登録は最終予選ラウンドの開始前に開始されます）。
すでに第3ラウンドの前夜に、RCCで使用されているほぼすべてのプログラミング言語のコンパイラバージョンを更新しました。 彼らは、GNU C ++（Visual C ++ 2013はすでにC ++ 11をサポートしています）の下でC ++ 11にソリューションを送信する機能を追加し、Java 8（Java 7も今のところ残っています）を追加しました。 チャンピオンシップルールページ< www.russiancodecup.ru/rules >で、コンパイラとコンパイルラインの現在のバージョンを確認できます。
問題A. 三角形 。
アイデア：アンドレイ・スタンケビッチ。
実装：アンナマロバ。
分析：アンナマロバ。
この問題では、各タイプの三角形の数を決定する必要があり、これは4つのセグメントで構成できます。
考えられるすべてのトリプルのセグメントを調べます。 三角形の不等式が成り立つ場合、つまり、任意の2つの辺の合計が3番目の辺の長さよりも大きい場合、三角形は3つのセグメントで構成されます。
長さの昇順でセグメントa、b、cを検討します。 等式c2 = a2 + b2が成り立つ場合、三角形は長方形で、c2 <a2 + b2が鋭角で、c2> a2 + b2が鈍角の場合
問題B. 折り紙
アイデア：ジョージコルネエフ。
実装：ニコライヴェデルニコフ。
分析：ニコライ・ヴェデルニコフ。
この問題では、b上の長方形aに、辺が元の面と平行な領域Sのサブ長方形が存在するかどうかを確認する必要があります。
これを行うには、数値Sのすべてのx除数を並べ替え、x≤aおよびS ⁄ x≤bかどうかを確認します。 制約を満たすxとS ⁄ xのペアが少なくとも1つ存在する場合、解が存在します。
1つのテストケースOの動作時間（sqrt（S））。
問題C. ミティアとカウント 。
アイデア：審査員。
実装：Vitalik Aksyonov。
分析：ヴィタリク・アクショノフ。
最初の観察結果は次のとおりです。グラフはエッジサボテンでなければなりません。 それがそのようにうまくいかなかった場合、間違いなく均等なサイクルがあります。 これはサボテンなので、サイクル数はm-（n-1）です。 また、各サイクルには少なくとも3つの頂点が含まれるため、3・（m-（n-1））≤mです。 したがって、エッジの最大数は3・（n-1）/ 2です。
奇数nの場合、これはミル、つまり1つの頂点に沿って交差する長さ3のサイクルのセットであり、奇数nの場合、ほぼ同じですが、別の垂れ下がった頂点はエッジによって他と接続されます。
タスクD. 賞品 。
アイデア：Vitalik Aksyonov。
実装：Vitalik Aksyonov。
分析：ヴィタリク・アクショノフ。
参加者に与えられるキャンディーの数は、グループ番号に応じて減少する必要があることを知っています。 お菓子の満足のいくパーティションが次のように表現できることを確認するのは簡単です：
最初のグループでは、子供たちはn個のキャンディーを受け取り、2番目のグループでは、n-1個のキャンディー、...、最後の1個のキャンディーを受け取ります 次に、グループプレフィックスのすべての子にキャンディを1つ追加できます。 これは、数pを選択し、i≤pに対してaiを1増やすことができることを意味します。
初期分布を選択したため、キャンディーの総数からn・a1 + ... + 1・anをすぐに差し引くことができます。 分布演算がbp = a1 + ... + apを減算することは簡単にわかります。 つまり、ある合計b1、...、bnの形式でdを表現できるかどうかを確認する必要があります。これは標準的なバックパックの問題です。
ランタイムO（nd）。
問題E. 暗号化キー 。
アイデア：Vitaliy Demyaniuk。
実現：Vitaliy Demyanjuk。
分析：Vitaliy Demyanjuk。
一連の数値a1、a2、...、anが与えられます。 彼は、NCDとNOCの運営に関して閉鎖されました。 与えられた数vが閉集合Sに属するかどうかを調べる必要があります。
vを形式p1q1p2q2 ... pkqk、qi> 0で表します。ここで、p1、p2、...、pkは素数です。 vがSに属するためには、すべてのi（1≤i≤k）に対して、piqi andajおよびpiqi + 1∤ajのようなj（1≤j≤n）が存在する必要があります。 この事実は、NOC（GCD（...）、GCD（...）、...、GCD（...））の形式で任意の数を表すことができるという事実に基づいています。min（a、max（ b、c））= max（最小（a、b）、min（a、c））およびmax（a、最小（b、c））= min（最大（a、b）、最大（a、c） ） ciを、piqi ∣ajとなるような数ajの最大公約数に等しく設定します。 すべてのciがvを分割する場合、vはSに属します。これは、すべてのciの最小公倍数として取得できます。 それ以外の場合、vはSに属しません（これは、GCDおよびLCLの操作のプロパティに基づきます）。
動作時間O（nk + sqrt（v））、ここでkはvの素数の数です。