ロシアコードカップ2017の第1ラウンドの結果

Mischeviouslittleelfによる真夜中の剣

4月2日、 ロシアコードカップ2017の最初の予選ラウンドが開催され 、過去3年間の参加記録が破られました。 ラウンドのタスクの数と分析を提供します。

A. 火星のバレーボール
B. 壁画
C. 魔法のアーティファクト
D. メモリマネージャー
E. フォックス

ラウンドに参加した4552人の参加者のうち、1001人は今年だけRCCを発見した新人です。 今回は2015年と2016年の2倍のアクティブな参加者がいました！ 合計で6586個のソリューションが送信されました。 いつものように、最も人気のあるものはさまざまなバリエーションのC ++です（2346ソリューション-11番目のバージョンのプラスのC ++ 14、1425と、それぞれGNU C ++ 6.2およびVisual C ++ 2013を備えた約500のソリューション）。 Java 8.0（649）で人気が2位、Python（PyPy 2.4.0でPython 3.5 + 60ソリューションで402）で3位。 スポーツプログラミングで最も不人気なのは、Perl、D、およびHaskellであることが判明しました（最後に、彼らはラウンド全体で1つのソリューションを正確に作成しました）。 サポートされているすべての言語のリストは、 ここにあります 。

ラウンドの結果によると、200名の参加者が5月14日に開催される予選ラウンドに参加しました。 しかし、5つすべての問題を解決したのはそのうちの8つだけでした。 ここで一般的な結果を見ることができます。累積ペナルティ時間に応じて、トップの残りから真剣に離脱した5人をリストします。

1. エフゲニー・カプン、サンクトペテルブルク
2. スタニスラフ・エルショフ、サンクトペテルブルク
3. ピーター・ミトリチェフ、チューリッヒ、スイス
4. So島誠、東京、日本
5. マキシム・フィニュティン、トリアッティ

資格をお持ちのすべての人を祝福します。 今週の4月16日日曜日、モスクワ時間12:00から14:00に開催される第2予選で、他の皆さんに幸運を祈ります。

A.火星のバレーボール

2秒の制限時間
256 MBのメモリ制限

火星でのバレーボールの試合は、 kポイントまでの2つのチームによって行われますが、勝つためには、ギャップは少なくとも2ポイントでなければなりません。 各ボールについて、チームの1つが正確に1ポイントを獲得します。

現在、最初のチームのスコアはxで、2番目のチームのスコアはyです。 試合終了までにプレーするゴールの最小数は？

入力データ

入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤5000）が含まれています。

各テストケースは、スペースで区切られた3つの整数、 k 、 x 、 y （1≤k≤100; 0≤x、y≤100）を含む1行で記述されます。

正しい未完のゲームで得点が得られることが保証されています。

インプリント

テストごとに、個別の行に答えを印刷します-試合の終了前にプレーされるゴールの最小数。

B.壁画

2秒の制限時間
256 MBのメモリ制限

少女マーシャは彼女の部屋の壁を見ています。 壁には正方形のタイルが並んでいますが、一部ではなくランプが取り付けられています。 したがって、壁は、サイズがn × mの市松模様の長方形で、一部のセルにはランプがあると想像できます。

マーシャには、 k種類の色の塗料があります。 Mashaは、壁のすべてのタイルをペイントして、壁の端または両端のランプで囲まれたタイルの垂直または水平セグメントで、色が繰り返されないようにします。 この場合、Mashaはもちろんペイントしません。 マーシャはすべての色を使用する必要はありません。

マーシャは、壁の塗り方を理解するように頼みます。

入力データ

入力には、いくつかのテストスイートが含まれます。 最初の行には、テストの数tが含まれています。

各テストの説明は次のとおりです：テストの説明の最初の行には、3つの数値n 、 m 、 k （1≤n、 m≤100、1≤k≤max （ n 、 m ））が含まれています-壁の寸法とMashaが持っているさまざまな色の数。

次のn行には、それぞれa _ijの m個の数字が含まれています。

• ランプが位置（ i 、 j ）にある場合、 a _ij = 0。
• タイルが位置（ i 、 j ）にある場合、 a _ij = 1。

すべてのテストのタイルとランプの総数は10 ^5を超えません。

インプリント

個別の行の各テストについて、最初にその答えを印刷します。

• いいえ、マーシャが望むように壁をペイントする方法がない場合。
• はい、再描画する方法がある場合。 この場合、次のn行でm番号b _ij-位置（ i 、 j ）のタイルの色、またはこの位置にランプがある場合は0を印刷します。 適切な色が複数ある場合は、それらのいずれかを印刷します。

C.魔法のアーティファクト

2秒の制限時間
256 MBのメモリ制限

マキシムはコンピューターゲームをプレイしています。 1からnまでの番号が付けられたnレベルで構成されます。 これらは、マキシムが_i秒を費やすi番目のレベルで、任意の順序で完了することができます。

さらに、マキシムはキャラクターを強化する魔法のアーティファクトを見つけることができます。 ゲームにはアーティファクトが1つだけあり、その場所は正確にはわかりません_-i番目のレベルでは、確率p _iで配置されます。 アーティファクトを受け取った後、プレイがはるかに簡単になります-マキシムは、 i番目のレベルをb _i秒で渡します（ b i≤a _i ）。 マキシムが見つけたレベルではアーティファクトが機能しないことに注意してください。

マキシムは、ゲーム時間の数学的期待を最小限に抑えるために、この順序でレベルを完了することを望んでいます。 合格レベルの特定の順序を選択することで、彼が達成できる最小数学的期待値を計算するのを手伝います。 マキシムは事前にレベルの順序を選択しますが、この順序はアーティファクトのレベルに依存するものではありません。

確率変数の数学的期待値は、この結果の確率と量の値の積のすべての可能な結果の合計です。 この場合、結果はアーティファクトのレベルに対応し、数量の値は、アーティファクトがこのレベルにある場合の通過時間であり、マキシムは選択された順序でレベルを渡します。

入力データ

入力には、いくつかのテストケースが含まれます。 最初の行には1つの数値t-テストの数（1≤t≤1000）が含まれます。

各テストの説明は次のとおりです。最初の行には、数値n-レベル数（1≤n≤10 ⁵ ）が含まれます。

次のn行はレベルを示します。 それらのそれぞれは、3つの整数で与えられます： a _i 、 b _i 、 x _i-アーティファクトを見つける前後のレベルの経過時間、およびこのレベルでアーティファクトを見つける確率の計算に役立つ値。 確率は式p _i = x _i / 10 ⁷ （1≤b i≤a i≤10 ⁵ ; 0≤x i≤10 ⁷ ;すべてのx _iの合計は10 ^7に等しい）によって計算されます。

すべてのテストの合計nは5・10 ^5を超えません。

インプリント

テストごとに1つの数字を印刷します。合格レベルの順序を最適に選択して、ゲーム時間の数学的予想を印刷します。 絶対誤差または相対誤差が10-6を超えない場合、答えは正しいと見なされます。

D.メモリマネージャー

制限時間-3秒
256 MBのメモリ制限

Petyaは、磁気7Dブロックに基づくストレージ用に独自のMEM 2.0メモリマネージャーを積極的に開発しています。 ただし、ストレージからユーザーへのデータの最適な出力という問題に直面しました。

合計で、Petitのマネージャーは1からnまでの番号が付けられたn個のブロックを格納し、1つ以上のデータを発行するためのq要求があります。 要求は、到着した順に処理する必要があります。

Petyaにはデータ出力用のk個のポインターがあり、各ポインターはブロックの1つを指します。 最初、Petyaは任意のブロックセットにポインターを置くことができます。

Petinマネージャーは、少なくとも1つのポインターが各ブロックを指している場合、任意の数のブロックから即座にデータを返すことができます。 そうでない場合、マネージャーは最初に条件が満たされるようにポインターを再配置し、次にデータを提供します_。i番目の要求に対するこの操作の実行時間はs _iミリ秒です。任意の数のポインターを再配置できます。

Petyaは、すべてのユーザー要求への合計応答時間が最小限になるように、マネージャーにポインターの順列を実装したいと考えています。 リクエストは到着順に処理する必要があり、リクエストを交換することはできません。 彼を助けてください。

例に示されているテストを検討してください。

最初のテストでは、Petyaは最初にブロック1、2、および4にポインターを置くことができます。その後、最初の2つのクエリが即座に実行されます。 s ₃ = 1ミリ秒の₃番目の要求の前に、ブロック2、3および5へのポインターを置くことができ、 s ₄ = 1ミリ秒の₄番目の要求の前に、ブロック1、3および5にポインターを置くことができます。すべての要求の合計時間はs ₃ + s ₄ = 2ミリ秒。

2番目のテストでは、Peteは最初の2つのクエリを（ブロック1、2、4へのポインターを最初に配置することで）すぐに実行することは有益ではありません。 したがって、Petitの最適な戦略は、 s ₂ = 1ミリ秒のブロック1、3、4への2番目の要求の前、 s _4のブロック1、3、5へのポインターの最後の要求の前に、最初にブロック1、2および3へのポインターを置くことです= 3ミリ秒。 リクエストの合計応答時間s ₂ + s ₄ = 4ミリ秒。

入力データ

入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤1000）が含まれています。

以下のtテストのそれぞれは、次のように説明されています。テストの説明の最初の行には、3つの数値n 、 k 、 q-マネージャー内のブロック数、ポインターの数、ユーザークエリの数がそれぞれ含まれています（ 1≤k≤n≤10 5、1≤q≤10 ⁶ ）。

次の行には、 q個の整数s _i - i番目の要求に応答するときにポインターを再配置するのに必要な時間（ 1≤s i≤10 ⁴ ）が含まれます。

次のq行にはユーザー要求の説明が含まれ、 i番目の要求は1行で記述されます。最初の数字c _iはユーザーが受信したいデータブロックの数を表し（1≤c i≤k ）、次のc _i番号はこれらのブロックの数b昇順の_i 、 j （1≤b _i 、j≤n）。

同じ入力データのすべてのテストの合計nが10 ^5を超えないこと、および同じ入力データのすべてのテストの合計c _iが10 ^6を超えないことが保証されます。

インプリント

テストごとに、その回答（すべてのユーザーリクエストに対する最小合計応答時間）を出力します。

E.フォックス

制限時間-3秒
256 MBのメモリ制限

Ilyaは、文字列アルゴリズム研究研究所（FOX）で働いています。 今、彼はそのような問題を解決しようとしています。

文字列の配列s ₁ 、 s ₂ 、...、 s _nおよびqクエリを指定します。 各クエリは、2つの整数l _iおよびr _i （1≤l i≤r i≤n）で特徴付けられます。 要求に応答するには、次の手順を実行します。 次のように取得できる場合、表現可能な文字列を呼び出します.2つの文字列s _xおよびs _yを選択します。ここで、 l i≤x、y≤r _i 、文字列s _xの空でないプレフィックスを選択し、文字列s _yの空でないサフィックスを選択し、それらの連結を取得します。 クエリへの応答は、指定されたl _iおよびr _iの異なる表現可能な文字列の数です。

たとえば、 s = [ abc 、 ab 、 ac 、 bcac ]とし、 l _i = 2、 r _i = 3を選択します。次の行が表示可能です。

x = 2、 y = 2： ab = a + b、 aab = a + ab 、 abb = ab + b 、 abab = ab + ab *。

x = 2、 y = 3： ac = a + c 、 aac = a + ac 、 abc = ab + c 、 abac = ab + ac 。

x = 3、 y = 2： ab = a + b 、 aab = a + ab 、 acb = ac + b 、 acab = ac + ab 。

x = 3、 y = 3： ac = a + c 、 aac = a + ac 、 acc = ac + c 、 acac = ac + ac 。

合計12の異なる表現可能な文字列。

イリヤが十分に迅速に問題を解決するのに役立ちます。

入力データ

最初の行には、それぞれ2つの整数nとq-単語とクエリの数が含まれます（1≤n、 q≤10 ⁵ ）。

次のn行のそれぞれには、小文字のラテン文字で構成される空でない単語s _iが含まれます。 すべての単語の合計長は10 ^5を超えません。

次のq行には、数値l _i 、 r _i （ 1≤l i≤r i≤n ）のペアが含まれます-それぞれi番目のクエリの左右の境界線。

インプリント

q行を印刷します。それらのi番目には、 i番目の要求に対する答えである単一の整数が含まれている必要があります。

第2ラウンドのすべて！

お知らせします。第2ラウンドは、この日曜日、モスクワ時間の12:00からです。 この記事の執筆時点では、4,600人以上の参加者がすでに登録していますが、興味深いものになります。 今すぐ参加しよう ！

さらに、RCCとスポーツプログラミング全般に特化した電報のグループを開くことを決定しました。 ようこそ！