ロシアコードカップ-予選ラウンドをきっかけに

5月14日、 ロシアコードカップ2017の予選ラウンドが開催されました 。 伝統的に、タスクの分析を投稿して要約します。

A. 小さい数字
B. 新しいキーボード
C. 折りたたみ
D. 鋭い三角形
E. 配列の結合
F. 2つのサブツリー

603人がラウンドに参加しました。各資格ラウンドから最高200人のプログラマーが参加しました。 予選ラウンドの結果によると、55名の参加者が決勝に進みました。

どの参加者も予選ラウンドの6つの問題をすべて解決できませんでした。 15人が5つのタスクを完了しました。 4人、さらに55人の参加者。

3つのベスト：

1. そもそも追跡者からかなりの差をつけて（15分間）コストロマのミハイル・イパトフがいた。
2. 2位はモスクワのミハイル・ティホミロフが撮影した。
3. 3位-サンクトペテルブルクのIgor Pyshkin。

さらに、トップ10ヒット：

1. Mitrichev Peter、チューリッヒ、スイス
2. Gennady Korotkevich、サンクトペテルブルク、ロシア
3. アレクサンダーオスタニン、ドルゴプルドニ、ロシア
4. ロシア、サンクトペテルブルク、エルショフ・スタニスラフ
5. ジョッキ・ニコラ
6. Danilyuk Alexey、オジンツォボ、ロシア
7. Du Yuhao、北京、中国

すべての参加者とラウンドランキングテーブルはここで見つけることができます 。

2017年9月に開催される決勝戦に合格したすべての人におめでとうございます。 さて、今-タスクの分析。

A.小さい数字

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

Boy Vladには2つのお気に入りの数字aとbがあります。 最近、彼は学校で除算と乗算を教えるようになり、すぐに走って好きな数を除算と乗算しました。

最初に、彼はノートに数字aとbを書き、その後、3つの操作のいずれかを順番に実行することを決めました。

• 共通の除数のいずれかで両方の数値を除算します。
• aをその約数gの 1つで割り、 bを g倍します。
• bをその約数gの 1つで除算し、 aをgで乗算します。

各操作の後、彼は古い番号を消去し、2つの結果の番号をノートブックに書き戻し、それらを使用して操作を続行できます。

Vladはまだ小さいので、小さい数字が好きなので、ノートに書かれた数字の合計を最小化しようとします。 彼自身は対処できません。 Vladがこのような操作で取得できる最小数を決定し、最終的に判明する可能性のある数字のペアの例を提供するのを助けてください。

入力形式

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

各テストの説明は次のとおりです。テストの説明の1行には、 aとbの 2つの数字（1≤a 、 b≤10 ⁹ ）-Vladのお気に入りの数字が含まれています。

出力形式

各テストについて、個別の行にそれに対する答えを印刷します-条件から操作を適用することによって取得できる最小量のペア。

複数の回答がある場合は、それらのいずれかを印刷できます。

例

入力データ
2
4 5
4 6

インプリント
1 5
2 3

B.新しいキーボード

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

Petyaは新しいキーボードを購入しました。 n個のレイアウトをサポートします。 各レイアウトで、ラテンアルファベットの小文字のサブセットを入力できます。 レイアウトに1からnまでの番号を付けます。

Petyaは、ラテンアルファベットのm個の小文字で構成されるメッセージを入力したいと考えています。 最初のレイアウトは最初はアクティブです。 Petyaは次のことができます。

• レイアウトを切り替えます。 次に、現在のレイアウトの番号がiである場合、新しいレイアウトの番号はi mod n + 1になります。modは剰余剰余演算です。 Petyaが前のアクションによってレイアウトも切り替えた場合、このアクションにはbミリ秒かかります。それ以外の場合、このアクションには1ミリ秒かかります。
• 文字をダイヤルします。 Petyaは、現在のメッセージの最後に、現在のレイアウトの任意の文字を追加できます。 彼はこのアクションにcミリ秒費やします 。

Petyaがメッセージを入力するのに必要な最小時間を決定するのを手伝うか、メッセージを入力することが不可能であることを見つけてください。 メッセージを入力した後に残るレイアウトは任意です。

入力形式

最初の行には、4つの整数n 、 a 、 b 、およびc-キーボードレイアウトの数、およびレイアウトと文字セットの切り替えに必要なミリ秒数が含まれています（1≤n≤2,000、1≤b≤a≤10 9、1 ≤c≤10 ⁹ ）。

次のn行には、レイアウトの説明が含まれています。 各レイアウトは、ラテンアルファベットの各小文字がこのレイアウトで入力できる文字のサブセットである、空でない文字列で記述されます。 この行の文字はアルファベット順にソートされています。

最後の行には、行s -Petyaが入力したいメッセージ（行の長さsは 1〜2,000）が含まれています。 文字列sは、小文字のラテン文字で構成されます。

出力形式

単一の整数-メッセージの入力に必要な最小ミリ秒数を出力します。 印刷-メッセージを入力できない場合は1。

例

入力データ
5 3 2 1
abc
d
e
f
def
abcdef

インプリント
15

入力データ
1 1 1 1
a
z

インプリント
-1

C.折りたたみ

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

いつものように、Petyaは数学の授業で退屈したので、ノートのセルを塗りつぶし始めました。 これにうんざりしたとき、彼はkセルの一貫したセルラー図を取得していることに気付きました.2つの塗りつぶされたセルの間には、他の塗りつぶされたセルに沿ったパスがあり、このように隣接するセルには共通の側面があります。

ノートから慎重に切り取り、市松模様のグリッド線（水平または垂直-覚えていない）に沿って半分に折り、ノートの折り畳まれた図のコピーを描きました。 無駄ではありません！ ペティアは彼の姿を失い、彼に残されたのは、ノートに描かれた折り畳まれた姿のコピーだけでした。 今、彼は元の形状を復元したいと考えています。

元の図を明確に復元することは常に可能というわけではありませんが、ペティアは、彼が折り畳まれた図を得るために半分に折りたたむことができるkセルの少なくともいくつかの図を描画することで十分だと判断しました。 彼を助けてください-この条件を満たすkセルの初期接続図を見つけてください。

条件からの2番目のテスト例を検討してください。 その中で、折り畳まれた図は文字「P」を表し、元の図は12個のセルで構成されています。 元の図に可能なオプションの1つが図に示されています（曲げは直線y = 3で発生します）。

入力形式

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

次のtテストのそれぞれは、次のように説明されています：テストの説明の最初の行には、2つの整数n 、 k-折り畳まれたVasya図形を構成する塗りつぶされたセルの数と元の図形のセルの数が含まれます（1≤n <k≤10 ⁵ ）。

次のn行のそれぞれには、2つの数値x _i 、 y _iが含まれます_-i番目の塗りつぶされたセルの左下隅の座標（-10 10≤x _i 、 y i≤10 ⁸ ）。 すべての塗りつぶされたセルが異なり、一貫した図を形成することが保証されます。

同じ入力データのすべてのテストの合計kが10 ^5を超えないことが保証されています。

出力形式

各テストについて、その答えを印刷します。 入力ファイルから図を取得するには、図の説明とそれを曲げる方法を導き出す必要があります。

最初の行に折り畳み線を印刷し、次のk行に2つの整数（ x ' _i 、 y' _i ）-接続された図形のセルの座標。入力された図形を取得するために派生した折り畳み線に沿って半分に折り畳むことができます。

折り線は、4つの方法のいずれかで描画する必要があります。

• L num-折り畳みは直線x = numで行われ、左側の部分が右側の上部に重ねられます。
• R num-折り目は直線x = numで作成され、右側が左側の上に重ねられます。
• U num-曲げは直線y = numで行われ、上部が下部の上に重ねられます。
• D num-曲げは直線y = numで行われ、下部は上部の上部に重ねられます。

すべてのx ' _i 、 y' _i 、および折り目の座標は、絶対値で10 ⁹を超えてはなりません。 そのような図が存在することが保証されます。 適切な回答が複数ある場合は、それらのいずれかを印刷できます。

例

入力データ
2
7 14
0 0
0 1
0 2
1 2
2 2
2 1
2 0
7 12
0 0
0 1
0 2
1 2
2 2
2 1
2 0

インプリント
L 0
0 0
0 1
0 2
1 2
2 0
2 1
2 2
-1 0
-1 1
-1 2
-2 2
-3 2
-3 1
-3 0
U 3
0 0
0 1
0 2
1 2
2 2
2 1
2 0
0 3
1 3
2 3
0 4
2 4

D.鋭い三角形

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

最近では、モスクワの10年生のDmitry Zakharovがd次元空間に点の集合を構築する際に全員を追い抜いて、これらの点に頂点を持つすべての三角形が鋭角になっています。

ターニャはドミトリーで彼女の強さを測定することにしました。 もちろん、彼女はコンピューターを使用する予定です。 まず、彼女は次の問題を解決したいと考えています。 平面上のn個の点を考えると、これらの点に頂点を持つ鋭角三角形の数を見つける必要があります。 すべての角度が厳密に90度未満の場合、三角形は鋭角と呼ばれます。

入力形式

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

各テストの説明は次のとおりです。テストの説明の最初の行には、数n （3≤n≤2000）-ポイント数が含まれています。

次のn行には、2つの数値x _i 、 y _i （-10 9≤x、y≤10 ⁹ ）-点の座標が含まれます。 1つのテストのすべてのポイントが異なることが保証されています。

同じ入力データのすべてのテストのポイントの総数は2000を超えません。

出力形式

各テストについて、個別の行にそれに対する答えを印刷します-与えられた点に頂点を持つ鋭角三角形の数。

例

入力データ
2
5
1 1
2 2
3 3
4 1
6 4
5
0 0
3 1
5 1
5 -1
1 3

インプリント
3
4

E.配列の結合

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

自然数の2つの配列A = [ a ₁ 、 a ₂ 、...、 a _n ]およびB = [ b ₁ 、 b ₂ 、...、 b _m ]を考えます。 それらを長さkの辞書式に最小の数Rの配列のk和集合と呼びます。これは2つの空でないサブシーケンスに分割されます。最初のサブシーケンスは配列Aのサブシーケンスで、2番目は配列Bのサブシーケンスです

正式には、辞書の最小配列R = [ r ₁ 、 r ₂ 、...、 r _k ]を見つける必要があります。この配列には、空でないインデックスセット1≤i _1、1 < i _1、2 <... < i _1、元の配列のt≤nおよび1 < j _1、1 < j _1、2 <... < j _{1、 k -} t≤m、およびインデックスセット1≤i 2、1 < i _2、2 <.. 。< i _2、 t≤kおよび1≤j 2、1 < j 2、1 <... < j _{2、 k -} t≤k。

• 1≤p≤t、 1≤q≤k - t 、 i _{2、 p} ≠ j _{2、 qの場合} 、
• 1≤p≤tの場合、 a _{i 1、 p} = r _{i 1、 p} ;
• 1≤p≤k- t 、 b _{j 1、 p} = r _{j 1、 pの場合}

たとえば、 A = [1、2、1、3、1、2、1]、 B = [1、2、3、1]、 k = 9の場合、 kの統合はR = [1、1 、1、1、2、1、2、3、1]（最初の配列のサブシーケンスは[1、1、1、2、2、1]、2番目の配列のサブシーケンスは[1、2、3、1]）。

与えられた2つの配列AとB 、および数kから 、それらのk統一Rを見つけます。

入力形式

入力の最初の行には、数n-配列Aのサイズ（1≤n≤3000）が含まれます。

2行目には、 n個の数値a _i-配列A （1≤a i≤3000）が含まれます。

3行目には、数値m-配列Bのサイズ（1≤m≤3000）が含まれます。

4行目には、 m個の数値b _i - Bの配列（1≤b i≤3000）が含まれます。

最後の行には数値k （2≤k≤n + m ）が含まれています。

出力形式

入力ファイルで指定された配列のk和集合を出力します。

例

入力データ
7
1 2 1 3 1 2 1
4
1 2 3 1
9

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

F. 2つのサブツリー

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

中断されたツリーを検討してください。 vから距離kにある少なくとも1つの頂点をサブツリーに持つ頂点vを考えます。 vからの距離がkより大きいすべての頂点を削除することにより 、頂点vのkサブツリーを頂点vのサブツリーから取得したツリーと呼びます。 たとえば、次の図では、頂点3の2サブツリーが赤でマークされています。

最初の頂点に番号を付け直して2番目のツリーを取得できる場合、2つのツリーを同じと呼びますが、頂点での子の順序を変更することはできません。 たとえば、次の2つのツリーは同じではありません。

中断された木を考える。 根が異なる2つの同一のkツリーを持つように、最大​​のkを決定する必要があります。 これらのサブツリーは交差する場合があります。

図は、例のツリーを示しています。

最初の例では、同一の1サブツリーのルートは頂点2と3です。

2番目の例では、同一の3サブツリーのルートは頂点1と4です。

3番目の例では、同じ0サブツリーのルートは頂点1と2です。

入力形式

最初の行には、数t-テストの数（1≤t≤10 ⁴ ）が含まれます。

各tテストは次のように説明されます。最初の行には、数値n-頂点の数（2≤n≤10 ⁵ ）が含まれます。

これにn行が続きます。 それらのi番目には、番号cnt _i-頂点iの子の数、そしてcnt _i番号-頂点iの子の数が含まれます。 頂点には1から番号が付けられます。 ツリーのルートは頂点1です。指定されたグラフがルート1のツリーであることが保証されます。

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

出力形式

各テストケースについて、異なるルートを持つ2つの同一のkサブツリーが存在するように、最大kを個別の行に出力します。

例

入力データ
3
5
2 2 3
1 4
1 5
0
0
8
1 2
2 3 4
0
1 5
2 6 7
0
1 8
0
2
1 2
0

インプリント
1
3
0

今後の計画

最終ラウンドは9月に行われることを忘れないでください。 その後、タスクの条件とその分析もレイアウトします。 あなたはファイナリストの立場に自分自身を感じ、筋金入りの問題を解決できます。

そして最後に、アイデアの1つを共有します。おそらく来年、「言語のベスト」のような特別なノミネートを行います。 次に、たとえば、最高のC ++ソリューションの所有者が別の賞を受賞します。 何て言うの？