プログラマーの国際大会であるロシアコードカップ2016の次の予選ラウンドが終わりました 。 そして、確立された伝統に従って、最後のラウンドで出場者に提供された問題の解決策を知ることを勧めます。 今回は6つのタスクがありましたが、それらを解決するためにまだ2時間が割り当てられていました。 604人が次のラウンドのために戦った 。 RCCは、英語を話す参加者を含む初めて開催されます。 結果はすぐに現れました-ロシア語を話すプログラマーは深刻な競争に直面するでしょう。 50人が決勝戦に進み、そのうち19人はロシア語圏の参加者ではありません。 ファイナリストの中には、ロシア、ウクライナ、ベラルーシ、リトアニア、スロバキア、アルメニア、ポーランド、スイス、フィンランド、日本、中国、韓国の代表者がいます。

1. テスト作業
2. ヤスデ
3. 二分木
4. 試験管と試薬
5. 両替
6. タスクf

タスクA.試験

状態

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

すぐに、コリヤは重要なコントロールを作成する必要があるため、慎重に準備することにしました。 彼は、コントロールにn個のオプションがあり、そのうちi番目が1からm _iまでの番号が付けられたm _i個のタスクで構成されることを発見しました。 各オプションのタスクごとに、Kolyaは時間t _ij分を推定しました。

制御中、彼はタスクをバージョン内にある順序で厳密に解決することを計画しています。 作業はt分間続くコントロールの終了までに引き渡さなければなりません。 もちろん、Kolyaはコントロールを無効にすることもできますが、彼はこれがあまり正確ではないと考えています。 したがって、私はたった1つのタスクを片付ける準備ができています。 彼は、 t ₀分を割り当ての取り消しに費やします。

今、彼はこのすべての情報を知っており、このオプションに出くわした場合に解決する時間があるタスクの数を各オプションごとに見つけたいと考えています。

入力形式

最初の行には、3つの整数n 、 t 、およびt ₀ （1≤n≤100、1≤t≤10000、1≤t 0≤100）が含まれています-オプションの数、コントロールの期間、およびKolyaがタスクの書き込みに費やす時間です。

次のn行には、オプションの説明が含まれています。 最初の数m _i （1≤m i≤100）は、オプションiのジョブの数です。 次のm _iはt _ijに番号を付けます（1≤t ij≤100）-Kolyaがi番目のオプションのj番目のタスクの解決に費やす時間。

出力形式

各オプションについて、1行の整数-Kolyaがこのオプションに遭遇した場合に解決する時間があるタスクの数を新しい行に出力します。

例

入力データ
4 45 5
5 10 10 10 10 10
4 30 10 10 10
3 40 40 5
1,100

インプリント
5
4
2
1

解決策

Kolyaが解決するタスクのプレフィックスについて説明します。 すべてのタスクを自分で解決する場合に費やす時間と、この場合の1つのタスクに費やす最大時間を見つけます。 彼が償却する場合、彼が行うものの中で最も長いタスクを償却する必要があることは明らかです。 そして、コリヤが費やす時間はS -max（0、 M - t ₀ ）です。 ここで、今回がtを超えない最大のプレフィックスを見つけます。

問題B.ヤスデ

状態

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

子供の頃、小さなヤスデが少年フィリと一緒に家に住んでいました。 合計で、ヤスデには脚がn本あり、そのうちのいくつかは右足で、一部は左足でした。 毎日、ヤスデは足の一部のみを使用しましたが、常に少なくとも1本の左足と少なくとも1本の右足を使用していました。

毎日、フィルはノートに2つの数字を書き留めました。その日にヤスデが使用した左足と右足の数です。

フィリアは、メモからムカデの左足の数と右足の数を理解したいと考えています。 残念ながら、フィルは完璧ではなく、いくつかのエントリで間違いを犯した可能性があります。 Filyaは、ヤスデに少なくともl _iの左脚と少なくともr _iの右脚がある場合、エントリl _i 、 r _iが正しいと見なします。

可能な限り多くのエントリが正しいように、何本のムカデが左足と右足を持っている可能性があるかを彼に理解させてください。

入力形式

入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤10,000）が含まれています。
各テストの説明は次のとおりです。テストの説明の最初の行には数字n （2≤n≤10 ⁹ ）-ヤスデの足の合計数が含まれ、2番目の行には数字m （1≤m≤10 ⁵ ）-レコードの数が含まれます。

次のm行には、2つの数値l _iおよびr _i （ 1≤l _i 、 r i≤n）-フィリの記録によると、それぞれi日目にヤスデが使用する左右の足の数が含まれます。

すべてのテストのレコードの総数は10 ^5を超えません。

出力形式

テストごとに、別々の行に、その答え-ヤスデの左右の足の数を印刷します。これにより、可能な限り多くのレコードが正しいことがわかります。

例

入力データ
3
4
3
1 2
1 3
1 4
2
2
2 2
1 2
5
4
1 4
2 3
3 2
4 1

インプリント
1 3
1 1
1 4

解決策

この問題を解決するには、すべてのレコードを左脚の数で並べ替えます。 次に、左脚の数を昇順で並べ替えます。 左脚がl _iの場合、最初のiエントリは潜在的にtrueになり、後続のエントリはすべて正しくない可能性があります（ l _iに等しい脚の数を除く）。

次に、最初のiからいくつのレコードが正しいかを調べる必要があります。 r j≤n-l _iの場合、数値j≤iのレコードは真です。 このようなr _jをすべて見つけることは標準的なタスクであり、たとえばセグメントのツリーによって解決されます。

また、答えの数値の合計がnに等しくなるように注意し、すべてのエントリが正しくない場合を正しく処理する必要がありました。

問題C.バイナリツリー

状態

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

Vasyaの場合、生徒は完全な二分木を成長させる必要があり、そのすべての葉の根までの距離は同じです。

中断されたツリーは、頂点の1つがルートであるサイクルのない接続された無向グラフであることを思い出してください。 頂点の親は、ルートに最も近い隣接ノードであり、ルートには親がありません。 ピークの残りの隣人は彼女の息子と呼ばれます。 息子のいない山頂は葉と呼ばれます。 完全な二分木とは、各頂点が葉ではなく、ちょうど2人の息子を持つ中断ツリーです。

残念ながら、学期中、Vasyaはプログラミング競技に多くの時間を費やし、ツリーの成長を実際に監視しませんでした。 テストの数日前に、Vasyaは自分が木を育てたことに気付きましたが、おそらくそれは間違っていて、根さえ持っていませんでした。 Vasya自身は、ツリーのルートによってツリーの任意の頂点を選択し、頂点を追加することにより、そこから必要な完全なバイナリツリーを取得しようとします。 ある日、Vasyaはツリーに新しいピークを追加し、既存のピークの1つの息子にすることができます。

Vasyaは、タスクを完了することができるかどうか、ルートを選択する必要がある頂点、およびタスクに費やす最小日数を調べたいと考えています。 ルートによって選択可能な頂点がいくつかあり、完全なバイナリツリーを取得できる場合、そのすべての葉は最短日数でルートまでの距離が同じであるため、最小数の頂点が必要です。

必要な日数を表示するとき、Vasyaはこの数を10 ⁹ + 7で割った残りだけを見たいと思っています。Vasyaは、残りの分ではなく、ツリーの形成を完了することができる日数を最小限にしなければならないことに注意してください10 ⁹ + 7では、残りは撤退の直前に服用しなければなりません。

入力形式

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

次のtテストのそれぞれは、次のように説明されます。テストの説明の最初の行には、単一の整数n （2≤n≤2•10 ⁵ ）-ツリー内の頂点の数が含まれます。 テスト記述の次のn -1行は、数値のペアu _i 、 v _i （ 1≤u _i 、 v i≤n） _-i番目のエッジで接続された頂点の数を与えます。 リブがツリーを形成することが保証されます。

すべてのテストでの数値nの合計が2•10 ^5を超えないことが保証されています。

出力形式

各テストの回答を個別の行に印刷します。

頂点をルートとして選択できず、その後、一定の日数後に完全なバイナリツリーが得られ、そのすべての葉がルートまでの距離が同じ場合、-1を出力します。

それ以外の場合は、2つの整数を印刷します-ルートとして選択する頂点の数と、Vasyaが必要とする日数を10 ⁹ + 7で割った余りです。最短時間でタスクを完了できる頂点が複数ある場合は、最小数で頂点を印刷します。

例

入力データ
3
3
1 3
3 2
4
4 2
3 2
3 1
5
1 2
1 3
1 4
1 5

インプリント
3 0
2 3
-1

解決策

Vasyaが費やす必要のある日数を最小化するには、結果のバイナリツリーの高さを最小化する必要があります-最終ツリーのリーフの深さがhの場合、Vasyaは必要な頂点数を一時停止するために2 ^h -1- n日を費やします。

ツリー内に3を超える次数の頂点がある場合、タスクを完了できないことに注意してください。完全なバイナリツリーでは、すべての頂点に3つ以下の近傍しかありません。 答えのルートには正確に2人の息子がいることに注意してください。

したがって、問題を解決するには、ルート（次数が2以下の頂点）を整理し、それから他のすべてまでの距離の最大値が最小になるように頂点を選択する必要があります。 これは、結果のツリーの高さになります。

タスクD.試験管と試薬

状態

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

今日、化学の先生はペティアに非常に重要な仕事を与えました-試験管に試薬を入れること。 彼は、 n本のチューブとm個の試薬を与えられました。 各チューブについて、 min _iおよびmax _iが既知です-それぞれに入れることができるミリリットル単位の液体の最小および最大総量、ならびに試薬番号c _iおよび番号p _iです。 各試薬について、数v _iも知られています-プチには何ミリリットルありますか。 教師は、Petyaにすべての試薬を注いで、 i番目の試験管内のすべての液体の少なくともp _iパーセントが試薬c _iで占められ、各試験管でmin _iおよびmax _iの制限を満たすように要求します。 すべての試薬を完全にこぼす必要があります。 化学反応や試薬量の変化は発生しないと想定しています。

Petyaが教師のタスクを完了するのを手伝うか、彼がどのようにしようとしても、彼はそれをできないと言う。

たとえば、例の最初のテストケースでは、次の答えが機能します。

• 最初の試験管に3ミリリットルの最初の試薬と2ミリリットルの2番目の試薬を注ぎます。
• 4ミリリットルの3番目の試薬と1ミリリットルの2番目の試薬を2番目の試験管に注ぎます。
• 4番目の試薬3ミリリットルと2番目の試薬1ミリリットルを最後の試験管に注ぎます。

この場合、 min _iおよびmax _iのすべての制限、および試験管内の試薬の割合の制限が満たされます。最初の試験管では3/5 =最初の試薬の60％、2番目の試験管では4/5 = 3番目の試薬の80％ in vitro 3/4 = 75％≥4番目の試薬の70％。 また、すべての試薬が完全にこぼれているため、教師から与えられたすべての要件が満たされ、答えは正しいです。

入力形式

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

次のtテストのそれぞれは、次のように説明されています。テストの説明の最初の行には、それぞれ2つの数値n 、 m （1≤n、m≤10 ⁵ ）-チューブと試薬の数が含まれます。

次のn行のi番目には、4つの整数min _i 、 max _i 、 c _i 、 p _i （ 1≤min i≤max i≤10 5、1≤c i≤m、1≤p i≤100）が含まれます。 i番目のチューブに注ぐことができる液体のミリリットルの最小および最大総数、それぞれチューブ内の試薬数およびその最小割合。

テストの説明の最後の行には、 m個の整数v _i （1≤v i≤10 ⁵ ）-Petyaのi番目の試薬のミリリットル数が含まれています。

すべてのテストでnの合計とmの合計が10 ^5を超えないことが保証されています。

出力形式

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

答えが存在する場合、最初の行にYESを印刷し、次のn行のi番目に最初に番号k - i番目の試験管内の異なる試薬の数、次にk組の正の数id 、 v-試験管内の試薬の数とその量を印刷します。 複数の回答がある場合は、どれでも印刷できます。

テストへの回答が存在しない場合は、1行にNOを出力します。

問題に記載されているすべての条件が満たされ、相対誤差または絶対誤差が10 ^-6を超えない場合、答えは正しいとみなされます。

例

入力データ
2
3 4
5 8 1 60
4 6 3 80
3 4 4 70
3 4 4 3
3 4
6 8 1 60
4 6 3 80
3 4 4 70
3 4 4 3

インプリント
はい
2 1 3.0000000000 2 2.0000000000
2 2 1.0000000000 3 4.0000000000
2 2 1.0000000000 4 3.0000000000
いや

解決策

いくつかの段階で建設的なアルゴリズムを提示します。

• sum（min _i ）> sum（v _i ）の場合-答えはノーです。
• sum（max _i ）<sum（v _i ）の場合-答えはノーです。
• min _i • p _i / 100 mlの試薬c _iを各チューブに注ぎます。
• その後、各試薬iについて、 c _j = iのチューブを昇順p _jでソートし、残りの試薬番号iを順番に注ぎます。
• 各チューブに注入します（最大_j-最小_j ） p _j / 100ミリリットルのi番目の試薬、またはそれがなくなった場合はそれ以下。
• 残りの試薬を任意の方法でチューブに注ぎます_。i番目のチューブでは、要約_i •100 / p _iを超えない量の液体を追加できます（要約_iは現時点での液体の合計量です）。
• 流出が失敗し、液体が残っている場合、答えはノーです。
• 残っている唯一の問題は、一部の試験管では液体が₁ミリリットル未満であることです。
• これを修正するには、試験管iで、最初にc _j以外のすべての試験管j試薬からi番目の試験管に移し、少なくとも_jの試験管_に液体_jが残るようにします。
• これで十分でない場合は、残りの試験管_jから液体数c _jを移します（これで、パーセンテージの条件が損なわれることはありません）。

これらのアクションの後、試薬のチューブへの分離は、常に問題のすべての条件を満たします。
最後に、この問題では、正確性に問題がある可能性があることに注意してください。 sense審員のテストはこの意味で非常に人道的に構築されましたが、ラウンド後、Pyotr Mitrichev（予選ラウンドでの勝利を祝福します）は、精度の大幅な低下が発生するテストを示しました。 将来的には、実数の問題における正確性の微妙さを回避しようとします。

タスクE.両替

状態

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

彼の長年にわたって、ボルヤはn個のコインのコレクションを組み立ててきました。 彼はこれらのコインをすべて一列に並べました。 この場合、行のi番目のコインの額面額はa _iです。

ボルヤは別の旅行に出かけますが、トレーニングキャンプの時間はほとんどありません。 そのため、彼はコインの一部を一列に並べたいと思っており、コインが十分にあることを望んでいます。

Boryaはいくつかの質問に答えたいと思っています。 Boryaは、各要求で、 _i番目からr番目までのすべてのコインを受け取った場合に、変更せずに支払うことができない最低金額を知りたいと考えています。 より正式には、彼はl _iからr _iまでの数のコインのサブセットを選択することが不可能な最小の正の整数zを見つけたいと考えています。

入力形式

最初の行には、2つの整数nおよびm （1≤n、m≤150 000）-Boriが持っているコインの数とリクエストの数が含まれています。 次の行にはn個の数字a _i （1≤a i≤10 ⁹ ） _-i番目のコインの名目値が含まれています。

次のm行には、2つの数値l _iおよびr _i （1≤l i≤r i≤n ）-クエリの説明が含まれます。

出力形式

m個のリクエストのそれぞれについて、 l _i番目からr _i番目までのコインを使用して、変更なしで支払うことのできない最小額を印刷します。

例

入力データ
5 5
2 1 5 3 1
1 5
1 3
1 1
2 4
2 5

インプリント
13
4
1
2
11

解決策

コインの特定のセットで与えることができない最小の金額を見つける方法を検討してください。 繰り返し答えを見つけます。 最初は、金額がゼロであるとしか想像できず、コインを使用しませんでした。

次のステップで、値がXを超えないすべてのコインを調べ、 Yまでの金額を支払うことができるとします。 それぞれがXを超えるがY + 1を超えないコストのコインの合計値を合計に等しくします。 合計= 0の場合、 Y + 1の場合、このセットの使用は想像できません。 それ以外の場合は、値がY + 1以下のすべてのコインが考慮されるという条件に移りましょう。Y + sumまでの金額を想像できます。

調べた最大コインの値は、少なくともフィボナッチ数と同じくらい速く成長することに注意してください。 したがって、このプロセスはO（log Answer）の繰り返しで終了します。

元の問題を解決するには、セグメント上のXより小さい数の合計を見つける方法を学ぶ必要があります。 O（log n）でこれを行うと、 O（m log n log Answer）で合計で問題を解決できます 。

このタスクは標準です。 線形のメモリ量を必要とする方法を検討してください。 これを行うには、元の配列内のすべての数値を並べ替え、すべての要求に並行して応答します。 次の反復では、各リクエストについて、現在受け取ることができる最大金額がわかります。 すべてのリクエストをソートします。 次に、元の配列の番号を昇順でフェンウィックツリーに追加し、次の要求に適切なタイミングで境界線を更新します。

タスクf

状態

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

Gnome PashaはGnome Math Cupの予選ラウンドを書きます。 問題Fとして以下が提案されています。

n個の自然数a ₁ 、 a ₂ 、...、 a _nおよび自然数dが与えられた場合、 a ₁ x ₁ + aであるような非ゼロ整数x ₁ 、 x ₂ 、...、 x _nのセットを見つける必要があります。 ₂ x ₂ + ... + a _n x _n = d ノームの乗算と加算は不十分であるため、すべての数値d 、 a _iは10 ^6を超えず、数値x _iは-10 6〜10 ^6でなければなりませんが、0に等しくない必要があります。

Pashaが問題の条件を満たす少なくとも1つのセットx _iを見つけるのを手伝うか、主催者が貧弱なテストを行い、答えがないことを彼に知らせます。

入力形式

入力の最初の行には、テストの数であるtが含まれています。 各テストは2行で与えられます。 最初の行には2つの数値nとdが含まれています（1≤n≤10 5、1≤d≤10 ⁶ ）。 2行目には、 n個の数値a _i （1≤a i≤10 ⁶ ）が含まれます。 すべてのテストのnの合計は10 ^5を超えません。

出力形式

各テストの回答を印刷します。 必要なセットx _iが存在する場合、1行目にYESを印刷し、2行目に適切なセットを印刷します。 それ以外の場合は、テストプリントへの回答の1行でNO。

例

入力データ
2
2 1
2 3
3 3
2 3 1000

インプリント
はい
2 -1
はい
503 -1 -1

解決策

答えNOは、 dがすべての数a _iの最大除数で割り切れない場合の1つの場合のみです。 それ以外の場合、答えは常に存在します。 まず、すべてのa _iとdをgcd（ a ₁ 、...、 a _n ）で除算した後、値を制限せずに少なくともいくつかの答えを得る方法を学びます。 n = 1の場合、 x ₁ = d / a ₁です。 他の場合、各接頭辞[1、 p ]に対してx _i、pを選択し、 a ₁ x _1、p + ... + a _p x _p、p = gcd（ a ₁ 、...、 a _p ） これは帰納法によって行われます。 x _1、1 =1。すでにx _i、pを見つけ、 x _i、p + 1を見つけたいとします。拡張ユークリッドアルゴリズムを使用して、 sとtを見つけます。s•gcd（ a ₁ 、...、 a _p ） + t • a _{p + 1} = gcd（gcd（ a ₁ 、...、 a _p ）、 a _{p + 1} ）= gcd（ a ₁ 、...、 a _{p + 1} ）。 次に、 i≤p x _{iの場合、p + 1} = s x _i、pおよびx _{p + 1、p + 1} = tです。 x _i、nを受け取っ_たら、 x _i = d / gcd（ a ₁ 、...、 a _n ） x _i、n = dx _i、nを計算します。 このソリューションはO（n ² ）で機能しますが、制限に適合しません。 作業時間を短縮するために、最大共通因子がセット全体と同じであり、削減できないようなサブセットを_iから選択します。 これを行うために、異なる素数の数を減らす場合、 ₁から_nまで反復し、サブセット内の数を取ります。 したがって、10 ⁶以下の数の素数の最大数は7であるため、選択したサブセットには7個以下の要素が含まれます。サブセットの数については、説明したアルゴリズムを実行し、セットに含まれていない数については、単にxを設定します_i = 0。

現在、アルゴリズムはO（n）に対して機能しますが、 x _iモジュロが10 ⁶を超えないという条件は満たされず、それらの間にゼロがあってはなりません。 これを行うために、正規化手順を説明します。 まず、 x _iの最初の条件を満たします。 まず、 i > 1のすべてのx _iを非負でa ₁未満にします。 これは、同等の変更の単純な操作によって行われます。x1 ka _iから減算し、 x _i ka _1に追加します。ここで、 k = （x _i mod a ₁ - x _i ）/ a ₁です。 x ₁モジュロは|を超えることができないため、演算の結果は64ビットデータ型に適合することに注意してください。 d-a ₂ x ₂ -...- a _n x _n | <10 ⁶ •10 ⁶ •10 ⁵ 。 ここで、2番目から最後まですべてのx _iを調べ 、それぞれで操作を順番に実行します： x _iから₁を引き、 x _1に a _iを追加します。 x ₁ 、...、 x _iに操作を適用した後、0≥x 1≥–10 ^6になる iが存在することに注意してください。 そのようなiが存在しないとすると、すべてのx _iは負になり、これは起こり得ません。a1 x ₁ + ... a _n x _nはd 、つまり正の数を与えるからです。 取得方法を学んだ後| x _i | ≤10 ^6の場合、それらをゼロ以外のままにします。 おそらく1つを除くすべてのゼロをペアに分割します。 各ペアiとjで 、 x _i = a _jとx _j = –a _iを割り当てます。 x _p = 0のインデックスpのみが残っている場合があります。いくつかのケースを検討します。

• モジュロがa _pに等しくないx _jが存在する場合、次の演算を使用します： x _jからsign （x _j ）a _pを減算し、 x _pにsign （x _j ）a _jを追加します。
• そのようなx _jが存在しないが、p≤5•10 ^5の場合、演算は任意のx _jに適用できます。符号（x _j ）a _pをx _jに追加し、 x _pから符号（x _j ）a _pを減算します。
• それ以外の場合、 a _q ≠a _pであるような_qがなければなりません。 これが存在しない場合、すべてのa _i = a ₁であり、したがって、最大公約数a _i = a ₁ = 1への正規化により、2番目のケースが満たされるはずです。 x _qから符号（x _j ）a _pを減算し、 x _pに符号（x _j ）a _qを追加します。 その後、 x _qはゼロになります。 しかし、現在、 n > 2の場合、最初のケースがqに当てはまり 、 n = 2の場合、 d = a _q a p≤10 ⁶なので2番目のケースがqに当てはまります。

番号が64ビットのデータ型に適合するように、最初の段落で説明したアルゴリズムの各プレフィックスに対して正規化操作を実行する必要があることに注意してください。 詳細については、テストで掲示されるju審決定コードを参照できます。

***
ロシアコードカップチャンピオンシップは、ロシアのIT産業の発展を目的としたMail.Ruグループの取り組みの1つであり、 IT.Mail.Ruリソースによって統合されています。 IT.Mail.Ruプラットフォームは、ITに興味があり、この分野で専門的に開発しようと努力している人々のために作成されました。 このプロジェクトは、テクノパークMSTUでの教育プロジェクトであるロシアAIカップ、ロシアコードカップ、ロシアディベロッパーズカップのチャンピオンシップを組み合わせたものです。 バウマン、モスクワ州立大学テクノスフィア MIPTのM.V. LomonosovとTechnotrek さらに、IT.Mail.Ruでは、人気のあるプログラミング言語の知識をテストしたり、ITの世界から重要なニュースを学んだり、関連するイベントやITトピックに関する講義の放送を見たり見たりするためにテストを使用できます。