RCC 2016の最終ラウンドのタスクの分析

9月18日、2016 ロシアコードカップスポーツプログラミングチャンピオンシップの最後の最終ステージが開催されました。 苦闘の最初の場所はGennady Korotkevich 、2位と3位-それぞれVladislav EpifanovとNikolai Kalinin でした。

最終順位はこちらで確認できます。今年の賞金プールは、評価の最初の25か所に初めて分配されます。 これが唯一の革新ではありません。RCCで初めて、英語を話すプログラマーが参加する機会があり、そのうち4.5万人の参加者のうち1000人以上が参加しました。 競争の伝統的なCIS諸国に加えて、ドイツ、フィンランド、日本、スイス、中国、韓国の代表が最終ラウンドで戦いました。 さらに、今回はCodeforcesでミラーラウンドが開催されました-メインコンペティションの決勝直後に、全員が第1部門の特別に編成されたコンペティションで決勝の問題を解決する機会があり、200人を超えるプログラマーが参加しました。

従来、最終タスクの分析を提供しています（テストはこちらからダウンロードできます ）。

A.閉会式
B.サボテン恐怖症
C.宿題
D.スラローム
E.暗号
F.アレイカバレッジ

A.閉会式

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

状態

Squanch Code Cupの閉会式は、 n × m人の大ホールで開催されます。 ホール自体はn列で構成され、各列にはmの椅子があります。 各椅子には2つの座標があります：（ x 、 y ）（1≤x≤n、1≤y≤m）。

ホールの入り口には2つの線がありました。k人は座標（0、0）のポイントにあり、 n・m - k人は座標（0、 m + 1）のポイントにあります。 各人は特定の場所へのチケットを持っている必要があります。 人が初期座標（ x 、 y ）を持つ_p 、場所へのチケット（ x _p 、 y _p ）を持っている場合、|を通過する必要があります。 x - x _p | + | y - y _p |。

誰もが自分のスタミナ、つまり、彼がどのくらいの距離を移動できるかを知っています。 あなたの仕事は、すべてのチケットを配布して、全員が自分の場所に到達できるかどうかを調べることです。

入力形式

入力の最初の行には、2つの自然数nとm （1≤n・m≤10 ⁴ ）-ホールの寸法が含まれています。

2行目には、負でない整数がいくつか含まれています。 最初の数k （0≤k≤n・m ）は、初期座標（0、0）を持つ人の数を示します。 これらの人々のスタミナを示すk個の数字が続きます。

3行目には、負でない整数がいくつか含まれています。 最初の数字l （ l = n・m - k ）は、初期座標（0、 m + 1）を持つ人の数を示し、その後にこれらの人のスタミナを示すlの数字が続きます。

耐久性は、 n + mを超えない自然数で与えられます。

出力形式

説明どおりにチケットを配布できる場合は、「YES」を印刷します。 それ以外の場合は、「NO」を出力します。

例

入力データ：
2 2
3 3 3 2
1 3
出力データ：
はい

入力データ：
2 2
3 2 3 3
1 2
出力データ：
いや

B.サボテン恐怖症

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

状態

ツリーは、循環のない接続された無向グラフです。 エッジサボテンは、ループと複数のエッジのない接続された無向グラフであり、各エッジは多くても1つの単純なサイクルにあります。

Vasyaにはrib骨サボテンがあり、各rib骨はある色で塗られています。 Vasyaは、サボテンから最小数のエッジを削除して、ツリーを取得したいと考えています。 同時に、彼は残りのdifferent骨の間の異なる色の数が最大であることを望んでいます。 彼がグラフにいくつの異なる色を残せるかを見つけるのを助けてください。

入力形式

最初の行には2つの整数n 、 m （2≤n≤10,000）が含まれています-それぞれVasyaグラフの頂点とエッジの数。

次のm行は、3つの整数u 、 v 、 c （ 1≤u 、v≤n、 u ≠ v 、1≤c≤m）-次のエッジを接続する頂点とその色を示します。 説明したグラフがエッジサボテンであることは保証されています。

出力形式

単一の整数-グラフに残せる異なる色の最大数を印刷します。

例

入力データ
4 4
1 2 4
2 3 1
3 4 2
4 2 3
インプリント
3

入力データ
7 9
1 2 1
2 3 4
3 1 5
1 4 5
4 5 2
5 1 6
1 6 4
6 7 6
7 1 3
インプリント
6

C.宿題

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

状態

今日、Petyaは数学の授業でひどく振る舞い、教師は彼に余分な宿題を与えることで彼を罰しました。 彼女は3つの数字n 、 m 、 kを彼に渡し、サイズn × mの長方形の市松模様のボードに1つ以上のセルをマークするように指示しました。 マークされたセルは、一貫した図を形成する必要があります。 この場合、3つのマークされたセルを選択して「コーナー」を形成するには、正確にk個の方法が必要です。選択された3つのセルはすべて2×2の正方形内にあります。

セルのセットは、接続された図を形成します。セットのセルから他のセルに到達できる場合、プロセス中にセルから側面に移動します。 Petyaはタスクが簡単ではないことを知っているので、プログラマーおよび親友として、このタスクで彼を助けるように頼みました。

入力形式

入力には、いくつかのテストスイートが含まれます。 最初の行には、テストの数t （1≤t≤100）が含まれています。 以下の各tテストは、3つの数値n 、 mおよびkの 1行で記述されます（3≤n、 m 、 n ×m≤10 5、0≤k≤10 ⁹ ）。 すべてのテストの合計n × mが10 ^5を超えないことが保証されています。

出力形式

各テストについて、その答えを印刷します。 答えが存在する場合、 m文字のn行を印刷します。「*」はマークされたセルを意味し、「。」 -マークなし。 答えが存在しない場合は、1行に-1を出力します。 各テストの後、最後を除いて、空の文字列を出力します。

例

入力データ
3
3 3 4
3 3 5
3 3 3
インプリント
**。
**。
...

***
**。
...

。**
**。
* ...

D.スラローム

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

状態

少女マーシャはウィンタースポーツが大好きで、今日はスキースラロームに行かなければなりません。 トラックは回路図のn × mチェックボックスです。 いくつかのセルを占める長方形の障害物がフィールドに配置されます。 Mashaは、座標（1、1）のセルからセル（ n 、 m ）に到達する必要があります。 この場合、各セルから、1つ上のセルまたは1つ右のセルに移動できます。 障害物があるセルでは、取得することは不可能です。

したがって、各障害物は2つの方法で回避できます。障害物は、高速道路に沿った移動軌跡の左側または右側のいずれかに残ります。 マーシャは多様性を愛しており、トラックに乗る方法はいくつあるのだろうと考えています。 ルートの通路は、マーシャの軌跡の左側のパスと右側のパスに障害物が少なくとも1つある場合、異なると見なされます。

あなたの仕事は、マーシャが軌道に乗るためのさまざまな方法を見つけるのを助けることです。 答えは大きく、Mashaは10 ⁹ + 7を法とする値に満足します。以下の図では、条件からのテストが分析されます。

入力形式

入力の最初の行には、3つの自然数n 、 m 、およびk （3≤n、m≤10 6、0≤k≤10 ⁵ ）-それぞれ経路の次元と障害物の数が含まれています。 次のk行には、4つの自然数x ₁ 、 y ₁ 、 x ₂ 、 y ₂ （1≤x 1≤x 2≤n 、1≤y 1≤y 2≤m）が含まれます-障害物の左下および右上隅の座標。 セル（1、1）および（ n 、 m ）には障害物がなく、すべての障害物に交差点がない（ただし、接触できる）ことが保証されています。

出力形式

出力ファイルに単一の数字を出力します。これは、トラックを通過するさまざまな方法の数を10 ⁹ + 7で割った余りです。

例

入力データ
3 3 0
インプリント
1

入力データ
4 5 1
2 2 3 4
インプリント
2

入力データ
5 5 3
2 2 2 3
4 2 5 2
4 4 4 4
インプリント
3

E.暗号

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

状態

最近、ボルヤは大きな電子スコアボードを見ました。 スコアボードでは数字が暗号化されています。 数字自体はn桁で構成され、各数字はラテン文字で書かれています。 ボードの横には、暗号化スキームを説明するプレートがあります。 したがって、各桁iおよび桁jについて 、エンコードされるシンボルcが既知です。 この場合、同じ文字を異なる数字に対応させることができます。 1秒ごとに、スコアボードにエンコードされている数値が1つ増えます。 そして、スコアボードで暗号化された数字のn桁すべてが9になった後、1秒でスコアボードが非常に大きな音を出します。

アンドレイは、スコアボードで最初に暗号化された番号を知っています。 彼は、Boryaがこの数値を正確に決定できる秒数を知りました。 Boryaが正確に時間を測定できること、およびスコアボード上の数値が初めてスコアボードを見た1秒後に正確に変化することを考慮してください。

入力形式

最初の行には、整数t （1≤t≤100）-テストケースの数が含まれています。 各テストの説明は、数字n （1≤n≤18）-暗号化された数字の文字数で始まります。 次の行には、スペースなしのn桁の数字（先行ゼロが含まれる場合があります）-暗号化された番号が含まれます。 次のn行には、それぞれ10文字が含まれています。 行iのj番目の文字がcに等しい場合、 i番目の桁j -1（上位ビットについては前に説明します）は文字cでエンコードされます 。

出力形式

各テストケースについて、先頭にゼロを付けない単一の整数（数値を復号化するのに必要な最小秒数）を個別の行に出力します。

例

入力データ
3
2
42
abcdefghij
ジフフェドクバ
2
42
aaaaaaaaaaa
aaaaaaaaaaa
1
2
abcdabcdff
インプリント
0
58
2

F.アレイカバレッジ

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

状態

Mishaにはn個の整数の配列があります。 彼は、配列の各要素に対して、それを含む少なくとも1つの選択されたセグメントが存在するように、 k個の異なるサブセグメントを選択したいと考えています。 同時に、ミーシャは、各セグメントの数値を合計し、結果の金額を合計すると、合計金額が最大になることを望んでいます。

入力形式

最初の行には2つの整数n 、 k （1≤n≤100 000、1≤k≤n・（ n + 1）/ 2）-配列内の要素の数と選択するセグメントの数が含まれます。

2行目には、 n個の整数a _i （-50 000≤a i≤50 000）-配列の要素が含まれます。

出力形式

単一の整数を印刷します-各要素が少なくとも1つのセグメントでカバーされるようにk個のセグメントを選択することで達成できるセグメント上の数値の合計の最大合計。

例

入力データ
5 4
6 -4 -10 -4 7
インプリント
11



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