前回の2ラウンドと同様、参加者は2時間以内に5つの問題を解決しなければなりませんでした。 決定の正確さと速度の両方が考慮されました。 3回目の予選ラウンドでは、4379人が次の決勝に到達するために戦いました。 しかし、チャンピオンシップで勝利に近づく機会を勝ち取ったのはわずか200人でした。 そして今、確立された伝統に従って、我々はラウンドのタスクを分析します。
問題A.長方形と正方形
状態
制限時間 2秒
256 MBのメモリ制限
イリヤは彼の友人フィルに行って、驚くほど美しい側面AとBを持つ長方形を見ました。 イリヤは、彼が一生このような領域の長方形を夢見ていたことに気付きました。
家に着くと、彼は家全体がC × Cの正方形で満たされているのを見ました。 Philが見た長方形の面積ができるだけ小さいC × Cの正方形から長方形を組み立てるのを手伝ってください。 すなわち、彼はフィル長方形と組み立てられた長方形の面積の差のモジュラスをできるだけ小さくしたい。
正方形は、ギャップやオーバーレイなしで、座標軸に平行に積み重ねることができます。 明らかに、イリヤは少なくとも1つの広場を取るでしょう。
たとえば、フィルのサイズが4×5の長方形で、イリヤの正方形が3×3の場合、イリヤが収集できるフィルの長方形に最も近い面積の長方形は3×6です。
入力形式
入力には、いくつかのテストスイートが含まれます。 最初の行には、テスト数t （1≤t≤10,000）が含まれています。
各テストケースは、3つの整数A 、 BおよびC （1≤A、 B 、C≤10 9 ）を含む1行で記述されます。
出力形式
各テストについて、別々の行に、それに対する答えを印刷します-CからCの正方形からIlyaによって収集された長方形の領域。Philが見たものとは可能な限り異なる領域です。
複数の回答がある場合は、それらのいずれかを印刷します。
例
入力データ
3
4 5 3
2 3 1
6 4 5
インプリント
18
6
25
解決策
この問題を解決するには、元の長方形と組み立てられた長方形の面積の違いのみが重要であり、形状は任意であることに注意する必要があります。 そして、辺CとnC （ nは自然数）を持つ長方形が答えとして適切であることは明らかです。
数値nは簡単に計算できます。 これは、商A•BおよびC 2に等しく、切り上げまたは切り捨てられます。 これらの回答の中で最も有利なものを選択し、少なくとも1つのC × C正方形を使用する必要があることを忘れないでください。
問題B.ゼロと単位
状態
制限時間 2秒
256 MBのメモリ制限
今日、Petyaはコンピューターサイエンスに関する宿題をしなかったため、罰として役員会に召喚されました。 教師は黒板に0と1からなる同じ長さの2行を書き、1回の操作のみでそれらを等しくするように依頼しました：任意の行の2つの隣接する文字を取得し、反転すると、文字0が1と1-0になります。
また、タスクを複雑にし、Petyaをさらに罰するために、先生はこの操作の最小数のアプリケーションでこれを行うように頼みました。
ペティアは混乱し、助けを求め、助けてください。
たとえば、教師が黒板に行0101および1111を書き込むようにします。次に、それらを等しくする最良の方法の1つは、次のとおりです。最初に、最初の行の2つの中心文字を反転し、行0011および1111を取得します。 2つのステップで同じ行を実現する他の方法があることに注意してください。
入力形式
入力には、いくつかのテストスイートが含まれます。 最初の行には、テストの数t （1≤t≤100）が含まれています。
以下のtテストのそれぞれは、次のように説明されます。テストの説明の最初の行には、数n （1≤n≤10 5 ）-教師が書いた行の長さが含まれます。 テストの説明の2行目と3行目には、教師が書いた行が含まれています-長さnが0と1の2行です。
すべてのテストの数値nの合計が10 5を超えないことが保証されています。
出力形式
テストケースごとに、個別の行にその答えを出力します-行を等しくすることができる操作の最小アプリケーション数、またはこれが不可能な場合は-1。
例
入力データ
2
4
0101
1111
3
011
111
インプリント
2
-1
解決策
反転操作は1行のみに適用するのが理にかなっていることがわかります。反転を適用した後、最初の行と2番目の行が一致する場合、2番目の行の操作をキャンセルして最初の行に適用できますが、その後は行が同じになります。 また、操作は任意の順序で適用できることに注意してください。
この事実から、シンプルな欲張りアルゴリズムが続きます。最初の行を左から右に進み、現在の状態を維持します。 i番目の文字s 1 [ i ]≠ s 2 [ i ]の場合、反転は最初の行の文字i 、 i + 1に適用する必要があります。 最後にs 1 [ n ]≠ s 2 [ n ]の場合、目的の反転シーケンスは存在せず、答えは-1です。
問題C.新しいルート
状態
制限時間 2秒
256 MBのメモリ制限
トラックデザイナーのゲルキルケは、新しいフォーミュラYトラックの注文を受けました。 Gerは、お気に入りの方法でトラックを作成する予定です。 彼は、ルートが配置される平面、 X軸が左から右に向けられ、 Y軸が下から上に向けられる座標系に導入し、次の制限付きでルートを構築したいと考えています。
- ルートは、座標軸に平行なn個のセグメントの開いた折れ線でなければなりません。
- 破線の端の1つは開始点で、もう1つは終了点です。それらは異なるポイントにある必要があります。
- 破線セグメントの端は、3000を超えない整数の正の座標を持つポイントにある必要があります。
- すべてのセグメントの長さはゼロ以外でなければなりません。
- 開始から終了まで破線に沿って移動する場合、2つの連続するセグメントの方向間の角度は時計回りに90度でなければなりません。
- ポリラインの前と次を除き、セグメントの終わりを別のセグメントにすることはできません。 特に、ポリラインで隣接していないセグメントは、長さがゼロでない共通のフラグメントを持つことはできません。
Gerは、正確にk個の自己交差点を持つように、 n個のセグメントの新しいルートを作成します。 数学者は、これは0≤k≤n 2 （ n 2-1 ）/ 2の場合に可能であると説明しました。ここで、 n 2はn / 2に切り捨てられます。 もちろん、Gerはまさにこのkの値を選択しました。 Heraが新しいトラックを設計するのに役立ちます。
入力形式
入力には、いくつかのテストケースが含まれます。 ファイルの最初の行には、1つの自然数t-テストの数が含まれています。
tに続く各行には2つの自然数が含まれます： nおよびk （1≤n≤1000、0≤k≤n 2 （ n 2-1 ）/ 2、 n 2はn / 2、切り捨て）-セグメントの数破線と自己交差の数。
同じ入力データのすべてのテストの合計nは10 4を超えません。
出力形式
出力ファイルには、各tテストの回答が含まれている必要があります。
各回答にはn + 1行が含まれている必要があり、そのi番目にはポリラインのi番目の頂点の座標が含まれます。 頂点は、ポリラインを最初から最後までバイパスする順序で表示する必要があります。 座標は3000を超えない正の整数でなければなりません。
指定された制限の下で、必要な破線が存在することが保証されます。
例
入力データ
2
4 1
3 0
インプリント
1 3
3 3
3 1
2 1
2 5
3 9
3 1
1 1
1 4
解決策
これは、サンプルを作成するタスクです。
最初にkの最大値を持つ例を作成する方法を示します。 水平セグメントから開始し、次に次の各垂直セグメントで、その直前にあるセグメントを除いて、それに垂直な前のセグメントをすべて交差させます。 14個のセグメントの例を図に示します。
正確にkを取得するには、 l （ l -1）≥2 k >（ l -1）（ l -2）となるように2 l個のセグメントを取得し、最大の例を構築する必要がありますが、最後のセグメントを事前に完成させることは可能です。 残りのn -2 lセグメントをルートの先頭に追加し、らせん状に配置します。 n = 17およびk = 9の例を図に示します。
kの制限は、理由のために取られます。 これは、固定nの交差の最大数です。 希望する人はこれを自分で証明することができます、ヒント：セグメントのペアnとn -1とペアn -3とn -4、 n -5とn -6、...、2と1（またはセグメント1 nは偶数）。
タスクD.ツリー
状態
制限時間 2秒
256 MBのメモリ制限
Kolyaの誕生日に、彼らはn個の頂点のぶら下がった木を提示しました。
中断されたツリーは、頂点の1つがルートであるサイクルのない接続された無向グラフであることを思い出してください。 頂点の親は、ルートに最も近い隣接ノードであり、ルートには親がありません。 ピークの残りの隣人は彼女の子供と呼ばれます。 Kolyaに提示されるツリーの頂点には1からnまでの番号が付けられ、番号1の頂点がそのルートになります。
Kolyaは彼のツリーで遊ぶことにしました。 彼はいくつかの頂点uを選択し、それを削除して、すべての子を元の親uからハングアップします。 Kolyaはルートを削除しません。 しかし、頂点を削除するだけでは面白くないので、現在のグラフで頂点間の距離を時々見つけるように頼まれました。 陰湿なコリヤのすべての質問に答えてください。
入力形式
最初の行には、単一の整数n （1≤n≤100 000）-ソースツリーの頂点の数が含まれます。 2行目には、 n -1個の整数p i （1≤p i≤n ）-最初は頂点2、3、...、 nの親である頂点の番号が含まれます。
3行目には、単一の整数q （1≤q≤100 000）-クエリの数が含まれます。 次のq行には、クエリの説明が含まれています。 各クエリは、1または2の整数で始まります。クエリの最初の数値が1の場合、2つの数値aおよびb （1≤a 、 b≤n）が続きます-2つの頂点、検索する必要がある距離。 それ以外の場合、単一の数値v （1≤v≤n）が続きます-削除される頂点の番号。
ソースツリーが正しく設定され、クエリの頂点が以前に削除されていないことが保証され、ルートが削除されることはありません。
出力形式
新しい行の2番目のタイプのクエリごとに、頂点間の距離を出力します。
例
入力データ
8
1 5 2 1 2 5 5
7
2 4
1 7 6
2 5
1 3 8
1 8 6
2 2
1 8 6
インプリント
4
2
3
2
解決策
ツリーに重みを付け、最初にすべてのエッジ1の重みを設定しましょう。頂点を削除する代わりに、その頂点から親に向かうエッジの重みを0に変更すると、距離の検索リクエストに対する応答は、重み付きリクエストからの頂点間の距離に等しくなりますソースツリーのエッジ。
新しい問題を解決するには、ツリーのエッジの重みを変更し、頂点間の距離を見つける必要があります。 まず、ソースツリーでルートからすべての頂点までの距離を見つけ、DFSがツリーを横断する順序で配列にこれらの距離を書き込みます。 rib骨の重量が変化するたびに、これらの距離を適切に保ちます。 一部のエッジの重みが変化すると距離が変化するすべての頂点は、配列内の連続したセグメントに対応することに注意してください。 したがって、要求を処理するには、この配列のセグメントに定数を追加する必要があります。 この目的のために、たとえば、この配列にセグメントのツリーを構築できます。
次に、頂点間の距離は次のように見つけることができます： d ab = d a + d b -2 d lca 、ここでlcaは最小の共通の祖先aおよびbであり、 d vはルートからvまでの距離です。
問題E.バーバラ
状態
4秒の制限時間
256 MBのメモリ制限
島での生活は、時にはあまり快適ではないことが判明しています！ 最近、野bar人は領土がn個の島で構成されている国を攻撃しました。 この国の島は、2つの島の間に島を2回通過しない単一のパスが存在するように、橋で接続されていました。
野bar人は、橋がこの状態の弱点であることを理解しました。 したがって、彼らはそれらを一つずつ破壊し始めました！ 住民の不満はどんどん大きくなりました。 当初、島iの住民の不満はa iに等しかった。
次の橋が破壊された後、ある島の住民の不満がどのように変化するかを考えてみましょう。 住民xが橋の破壊の前に到達できる島の数を、 aとして、破壊の後に-bで示します。 その後、不満はa - b + 1倍に増加しました 。
あなたは、住民の現在の不満を判断するシステムを開発するように招待されています。 プログラムは、 uとvのペアの形式で要求を受け取ります。 このような要求は、都市u + resとv + res （ resは最後の要求に対する回答）を接続するブリッジが破壊されたことを意味します。 この場合、最初に最後の要求に対する答えが0であると仮定する必要があります。
次の橋が破壊された後、島iの住民の不満はb iに等しく、すべてのb iの合計を10 9 + 7で割った余りにresを等しくする必要があると仮定します。
入力および出力データ形式の理解を深めるために、この例で何が起こるか考えてください。
最初は、住民の苦情は等しい
1 2 3 4 5
島1と3の間の橋を撤去した後、島1と2の住民の不満は4倍に増加し、他の都市の住民の不満は3倍に増加しました。 つまり、橋の破壊が不平等になった後の不満
4 8 9 12 15
そして、すべての不満は48です。その後、–47 + 48 = 1と–46 + 48 = 2の間の橋が破壊されました。
8 16 9 12 15
そして、不満の合計は60です。その後、島3と5を結ぶ橋が破壊されました。
8 16 18 24 45
最後の橋が破壊された後、不満は平等になりました。
8 16 36 48 45
153になります。
入力形式
最初の行には、整数n （2≤n≤2•10 5 ）-島の数が含まれています。
次の行には、 n個の数値ai（1≤a i≤10 9 + 6）が含まれています-住民の最初の不満。
次のn -1行には、数値u i 、 v i （ 1≤u i 、 v i≤n）のペアが含まれています。 このようなペアは、島u iとv iがブリッジで接続されていることを意味します。 すべての島から他のすべての島まで、正確に1つの方法で橋に到達できることが保証されています。
次のn -1行のそれぞれには、条件に記述されている形式の要求が含まれています。 よりよく理解するには、条件の例の説明を参照してください。 破壊時に橋が存在していたことが保証されます。
出力形式
各要求に対する回答を個別の行に印刷します。
例
入力データ
5
1 2 3 4 5
1 2
1 3
3 4
3 5
3 1
-47 -46
-57 -55
-108-107
インプリント
48
60
111
153
解決策
接続性の1つのコンポーネントである島の住民の不満は、最初の不満に、これらのすべての島に共通する一定の量を掛けたものに等しいことに注意してください。 すべてのコンポーネントについてこれらの値を維持します。
小さいコンポーネントのサイズに比例した時間でエッジ除去を処理する方法を学習します。 アルゴリズムの合計実行時間はO （ n log n ）になります。 これは次のように証明できます。 一部の頂点について、それが配置されているコンポーネントのサイズを考慮します。 その後、考慮されるたびに、このコンポーネントのサイズは少なくとも2倍に縮小されます。 各頂点はO （log n ）回検査されることに注意してください。
エッジを削除するときに、どのコンポーネントが小さいかがわかる場合、すべての頂点をバイパスし、それらを別のコンポーネントに移動できます（必要なすべての合計をカウントします）。 小さいコンポーネントを見つけるには、2つのコンポーネントで同時に2つの幅のトラバーサルを実行します。 そして、そのうちの1人が彼のコンポーネントのすべての頂点を訪問するとき、幅2番目のラウンドの作業を続行しません。 このようなアルゴリズムは、小さい方のコンポーネントのサイズに比例した時間で機能します。
***
ロシアコードカップチャンピオンシップは、ロシアのIT産業の発展を目的としたMail.Ruグループの取り組みの1つであり、 IT.Mail.Ruリソースによって統合されています。 IT.Mail.Ruプラットフォームは、ITに興味があり、この分野で専門的に開発しようと努力している人々のために作成されました。 このプロジェクトは、テクノパークMSTUでの教育プロジェクトであるロシアのAiカップ、ロシアのコードカップ、ロシアのデベロッパーカップのチャンピオンシップを組み合わせたものです。 バウマン、モスクワ州立大学テクノスフィア MIPTのM.V. LomonosovとTechnotrek さらに、IT.Mail.Ruでは、人気のあるプログラミング言語の知識をテストしたり、ITの世界から重要なニュースを学んだり、関連するイベントやITトピックに関する講義の放送を見たり見たりするためにテストを使用できます。