Clever Geek Handbook

ロシアコードカップ2012：写真、ビデオ、例での決勝のタスクの詳細な分析

2012年9月10日に、ロシアコードカップ2012のプログラミングチャンピオンシップは終了し、すべてがどのように起こったかについての詳細なストーリーが以前に公開されました。 それらはたった6つしかなく、それぞれが個別の興味深いストーリーです。





これらの問題を解決するために3時間が割り当てられました。 6つの問題のうち5つを解決したのは、ロシアコードカップ2012 Vladislav Epifanovの勝者だけでした 。 ファイナリストの半数未満がそれぞれ4つのタスクを完了しました。 最初の3つのタスクはほとんどすべてを行いました。 1組のEvgeny Kapunだけが、カードのデッキに関する問題を正しく解決しました。 トーナメントで2位になったのはNatalia Bondarenkoで 、彼は4つの問題を他の問題よりも速く、少ない試行で解決しました。







怒っている鳥



Mail.Ru Search Developer Divisionの責任者であるAndrey KALININが 、問題のステートメントについて説明します。







タスクは「Angry Birds」と呼ばれます。 その本質はシンプルです。 鳥がいる有限の長さのワイヤーがあります。 一部の鳥は右に行き、一部の鳥は左に行きます。 彼らが会うとき-彼らは方向を変える。 彼らはワイヤーの端に到達すると、離陸します。 これらの各鳥がいつ飛ぶかを決定する必要があります。 問題の状況に応じて、各方向に最大10万羽の鳥がいる可能性があるため、合計で200,000羽を超えることはありません。







問題の詳細な声明
ご存知のように、鳥はワイヤーの上に座るのが大好きです。 郡町Kには、彼が特に気に入った長いワイヤーが1つあります。 ある時点で、数羽の鳥がその上に座っていました。 すべてがうまくいきますが、ワイヤーの下を走っているブタだけが鳥を非常に怒らせたほどのほこりの雲を上げました。



怒った鳥は、このワイヤーに沿ってさまざまな方向に走り始めました-左の誰か、右の誰か。 この場合、すべての鳥は毎分1メートルに等しい同じ速度で走り始めました。 互いに向かって移動する2羽の鳥が出会うと、すぐに向きを変え、反対方向に同じ速度で走り始めます。



このプロセスは無期限に続きますが、ワイヤーだけが最終的なものであることが判明し、鳥の1匹がワイヤーの終わりに達するとすぐに離陸し、これに驚いた他のすべての鳥は向きを変えて反対方向に走り始めます。 2羽の鳥が同時に端まで走った場合、2ターンが発生します。または、同じことをしても何も起こりません。



ワイヤの長さ、走っている鳥の初期位置と方向に応じて、ワイヤから飛び出す時点で各鳥を見つけるプログラムを書く必要があります。



入力形式



最初の行には、単一の整数L（1≤L≤109）-メートル単位のワイヤの長さが含まれます。



2行目には、番号n（0≤n≤100 000）-右に走っている鳥の数が含まれています。 3行目には、n個の異なる整数a i （0 <a i <L）が含まれます。これは、ワイヤの左端から右に走る鳥までのメートル単位の距離です。



4行目には、数値m（0≤m≤100 000）-左に走っている鳥の数が含まれています。 5行目には、m個の異なる整数b i （0 <b i <L）が含まれます。これは、ワイヤの左端から左に走っている鳥までのメートル単位の距離です。

もともと同じ場所にいる鳥は2匹もいません。 少なくとも1羽の鳥が電線の上に座っていることが保証されています。



出力形式



最初の行にn個の整数t iを出力します -入力された説明の右に飛んでいるi番目の鳥が何分後に説明の順に飛んでいきます。 2行目では、m個の整数u iを出力します。これは、入力の説明の順序で左に飛ぶi番目の鳥が何分後に飛ぶかを示します。



2秒の制限時間



256 MBのメモリ制限







問題の例が示されました。 その定式化と解決策を明確にするために、この例では鳥の動きを毎分追跡することが有用です。 次の入力データを提供します。2羽の鳥は8メートルと9メートルにあり、右に進み、さらに3羽の鳥は2メートル、5メートル、7メートルにあり、左に行きます。 ワイヤーの長さは10メートルです。 これが初期状態です。 鳥が飛ぶ時期を計算する必要があります。







ご覧のとおり、1分目と5分目に鳥は右端から飛び出し、10枚目には2羽の鳥が同時に飛び、13枚目には最後の鳥が飛びます。



ここで、鳥の順序は決して変わらないことに注意することが重要です。 また、鳥が示すジグザグにもかかわらず、左または右に移動する鳥の数はその衝突に依存せず、移動座標の変化の性質は常に線形のままです。 これは、3回の衝突があった1分から5分までの間にはっきりと見えます。



右の2列に鳥の位置を示しました。 ワイヤからの最初の離陸の瞬間を予測できることがすぐに明らかになります-端の1つに最も近い鳥からワイヤの端までの分数（=メートルの数）。



また、離陸後、右への移動に関連付けられているすべての座標が左への移動に関連付けられている座標になり、その逆も同様であることがわかります。



その結果、この問題の解決策は、2つのデッキ、つまり、最初または最後の要素の削除がO（1）で実行される「両端キュー」タイプのデータ構造の保守に限定されます。 鳥が離陸すると、極端な要素がデッキから削除され、デッキ自体が交換されます。 ペアの保持<12月; 数字にどれだけ追加する必要があるか> O（1）で、次の鳥がどのくらいの長さでどの方向に飛ぶかを確認できます。 鳥の順序は変わらないので、鳥の元の場所の座標のソートされた配列を追加で保存して、どの鳥がワイヤを離れたかを判断する必要があります。



最も美しいソリューションは、Python3のソリューションです。 



from collections import deque length = int(input()) n = int(input()) right = deque(sorted(map(int, input().split()))) m = int(input()) left = deque(sorted(map(int, input().split()))) addLeft, addRight = 0, 0 INF = 2*10**9 ans = 0 while right or left: L = left[0] + addLeft if left else INF R = length - (right[-1] + addRight) if right else INF m = min(L, R) ans += m addLeft -= m addRight += m if L < R: left.popleft() left, addLeft, right, addRight = right, addRight, left, addLeft elif L == R: left.popleft() right.pop() else: right.pop() left, addLeft, right, addRight = right, addRight, left, addLeft print (ans)




鳥とのタスクは、 ミハイル・ケバーがラウンド開始から22分までに最初に作成しました。 数秒後、 Vasil BILETSKYはタスクに合格しました。



合計で、40人がタスクに対処し、11人がそれを解決し始めました。 解決にかかる平均時間は30分です。 これらのうち、解決に要する最大時間は44分です（ソリューションがまったく送信されなかった状況はカウントされません）。 最初のタスクを最初に解決した11人すべてが、少なくとも2つ以上を解決しました。 11のうち2つのケースを除き、全員がタスクBに進み、次にタスクCに行きました。つまり、アルファベット順にタスクを完了しました。 このタスクは、コンテストが開始されたすべてのタスクの中で3位です。



トリソリアン



Allods OnlineのテクニカルディレクターであるIlya VAYSMANは、Trisoliansのタスクについて次のように語っています。







問題の条件により、惑星トリソルの一部の住民は、私たち人間のような単一の整数としてではなく、k個の整数のベクトルとして年齢を指定します。 新生児のトリソリアンでは、年齢ベクトルは1つのゼロで構成されていますが、成長する年ごとに、年齢ベクトルの各要素に特定の正の数が追加されます。 トリソリアンのライフストーリーは、彼が生涯を通じて持っていたすべての年齢のベクトルのセットです。 同じ物語を持つトリソリアンが存在しないことはよく知られています。 科学者は、要素の合計がnであるベクトルでライフストーリーが終了するTrisolianの最大数に興味があります。 この値を素数を法として計算するプログラムを書く必要があります7340033 = 7 * 2 ^ 20 + 1。



たとえば、k = 2の場合、ライフストーリーは合計5のベクトルで終わる8つのトリソリアンが存在する可能性があります。



1.（0、0）-（1、1）-（2、3）;

2.（0、0）-（1、1）-（3、2）;

3.（0、0）-（1、2）-（2、3）;

4.（0、0）-（1、4）;

5.（0、0）-（2、1）-（3、2）;

6.（0、0）-（2、3）;

7.（0、0）-（3、2）;

8.（0、0）-（4、1）。



問題の詳細な声明
最近、惑星トリソルの住民は、私たち人間のような単一の整数としてではなく、k個の整数のベクトルとして年齢を示していることが知られています。 新生児のトリソリアンでは、彼の年齢のベクトルはk個のゼロで構成されていると考えられています。 年をとるにつれて、年齢ベクトルの各要素に正の数が毎年追加されます。



トリソリアンのライフストーリーは、彼が彼の人生の間に持っていた彼の年齢のすべてのベクトルのセットです。 地球科学者たちは、同じ物語を持つ二人のトリソリアンがいないことを確立しました。



科学者は、ライフストーリーが要素の合計がnであるベクトルで終わるトリソリアンの最大数に興味を持っています。 この値を素数7340033 = 7・220 + 1を法として計算するプログラムを作成します。



入力形式



最初の行には、2つの整数nおよびk-最後の年齢ベクトルの要素の合計、およびベクトルの要素数（1≤n≤4239、1≤k≤10 9 ）が含まれます。



出力形式



ライフストーリーが要素の合計がnであるベクトルで終わる可能性のあるTrisolianの最大数を出力します。 答えは、7340033 = 7・2 20 + 1を法として推定する必要があります。





少し歴史的背景がなければ、問題の解決はおそらく不可能です。 トリソリアンは、ホラー銀河の禁断地帯の奥深くに位置する惑星トリソルの居住者です。 それらは100％液体です。 形状を簡単に変更できます。 通常の居住者は平和的であり、支配エリートについては言えません。 時々、彼らはお互いを飲み、キャリアのはしごに沿ってこのように動きます。



すべての解決策は組み合わせ論に帰着するため、タスクは比較的単純です。 一方、kの可能な範囲（ベクトルの次元（1≤k≤10000000000））をよく見ると、すぐにそれほど単純ではなくなります。



N = 2 N = 3 N = 4 N = 5 N = 6
（0,0）-（1,1） （0,0）-（1,2）

（0,0）-（2,1） 		（0,0）-（1,1）-（2,2）

（0,0）-（2,2）

（0,0）-（3,1）

（0,0）-（1,3）

（0、0）-（1、1）-（2、3）;

（0、0）-（1、1）-（3、2）;

（0、0）-（1、2）-（2、3）;

（0、0）-（2、1）-（3、2）;

（0、0）-（2、3）;

（0、0）-（3、2）;

（0、0）-（4、1）。

（0、0）-（1、4）;

（0,0）-（1,1）-（2,2）-（3,3）

（0,0）-（1,1）-（4,2）

（0,0）-（1,1）-（2,4）

（0,0）-（1,1）-（3,3）

（0,0）-（1,2）-（3,3）

（0,0）-（1,2）-（2,4）

（0,0）-（2,1）-（3,3）

（0,0）-（2,1）-（4,2）

（0,0）-（2,2）-（3,3）

（0,0）-（3,1）-（4,2）

（0,0）-（1,3）-（2,4）

（0,0）-（5,1）

（0,0）-（1,5）

（0,0）-（4,2）

（0,0）-（2,4）

（0,0）-（3,3）

1つのオプション 2つのオプション 4つのオプション 8つのオプション 16オプション






解を理解するための重要なアイデアは、Nの大きな値の「ブッシュ」が部分的に低い値の解で構成されているため、再帰によって計算を整理できることです。



グラフィカルに、特殊なケースk = 2の場合、ライフストーリーは、ゼロマークと直線f（x）= nx上の軸上にある正の整数マークを接続するセグメントのセットとして表示できます。



N = 4の解は次のようになります。







N = 4ストーリー、8。



次に、このストーリーにベクトル（1,1）を追加し、取得します







ベクトル（1,1）で始まる各ストーリーは、N = 7のストーリーの一部になります。 ストーリーの別の部分は、ベクトル（1,2）などで始まる小さな「ブッシュ」です。



他のベクターと同様の物語。 N = 7の履歴要素の一部の始まりであるベクトル（1,3）の例を示します。 この場合、次のようになります。







つまり、トリソリアンの最初の誕生年に与えられたベクトルを取得し、トリソリアンの生活史のすべてのベクトルからそれを減算し、このベクトルを捨てた後、実際にトリソリアンのいくつかの生活史を取得します。最後のベクトルの要素の合計はn-スローされたベクトル要素）。



したがって、最後のベクトルの要素の合計がnであるすべてのストーリーは、一部のm <nに対して要素の合計がmである最後のベクトルを持つストーリーから取得でき、n-mに等しい合計を持つ正の要素のベクトルを追加できます人生の全物語。



合計がnmに等しいベクトルはいくつになりますか？ 最小ベクトルには各座標に1つが含まれるため、すべてのベクトル、kのすべてのコンポーネント、合計nmkが表示されます。 ここで、単位をk座標に与える必要があります。 これを行う方法の数は、繰り返しのある組み合わせの数です。 繰り返しのある組み合わせの数は、次のように計算されます。







そして、繰り返しのない組み合わせの数は次のように計算されます







これから、繰り返しaからbまでの組み合わせの数は、繰り返しなしの組み合わせa + b-1 by bの数に等しいと簡単に推測されます。



したがって、この場合、ウェイの数は、n-m-k + k-1

k、すなわち、kのn-m-1からのC







目的の値をans nとして示すと、次の繰り返し式が得られます。 ans 0 = 1と仮定します。アルゴリズムの実行時間はO（n2）です。











ここで、C（x、y）は最初の引数の2番目の引数の組み合わせの数で、x！として計算されます。 /（xy）！ / y！



トリソリアンの任務は、決勝戦に出席したほぼ全員によって行われました（2人を除く）。 問題を解決するのに約18分かかりました。 最初にそれを行ったのは11分でローマンリズバノフでしたが、わずかなマージンがありました-Evgeny KAPUN 。



CPU



CIO Mail.Ru GroupのAlexander GORNYがプロセッサの問題について説明します。







このタスクには、26種類の命令を実行できる特定のデュアルコアプロセッサが含まれます。 各命令は、英語のアルファベットの文字で象徴的に書かれています。 プログラムは一連の指示で構成されています。 アーキテクチャの特性上、2つのコアで同時に実行できるのは同じ命令のみであることがわかっている場合、プロセッサが指定された2nプログラム（特定の命令の指定されたシーケンスで構成される）を処理するのに必要な最小時間を計算する必要があり、n-そのようなプロセッサーの数。



プロセッサが2つのプログラムを同時に処理する方法の図：







問題は、n個のプロセッサーとそれぞれの2つのコアに2n個のプログラムを効率的に分散して、ステップ数を最小限にする方法に要約されます。



問題の詳細な声明
ご存知のように、現在製造されているプロセッサのほとんどはマルチコアです。つまり、複数の命令の同時実行をサポートしています。 Paraltelは、新しいタイプのデュアルコアプロセッサを開発しました。これにより、大文字のラテン文字で示される26種類の命令に従うことができます。 このような各命令の実行には、プロセッサの正確に1クロックサイクルが必要です。



このプロセッサのプログラムは一連の命令です。 プログラムの命令は、プログラムに従う順序で実行する必要があります。命令を交換することはできません。



2つのコアが存在するため、プロセッサは2つのプログラムを同時に実行できます（各コアに1つ）。 ただし、アーキテクチャ上の機能により、同じプロセッサの2つのコアで同時に実行できるのは同じ命令のみです。



2つのプログラムがプロセッサで実行されると、両方のプログラムの実行をできるだけ早く完了するように、特別な制御デバイスが実行を最適化します。 たとえば、ABBおよびABCプログラムは4サイクルでプロセッサ上で実行できます。最初に、異なるコアの両方のプログラムのAコマンドが同時に実行され、次にBコマンドが同時に実行され、次に最初のプログラムのBコマンド、秒から「C」。 同様に、「CAB」および「BAB」プログラムは4サイクルで実行されます。



最近、企業の専門家がn個のプロセッサからスーパーコンピューターを組み立てましたが、そのためには2n個のプログラムが必要です。 計算の構成は、各プロセッサがこのセットから正確に2つのプログラム（各コアに1つ）を実行する必要があるようなものです。



すべてのプログラムの完了時間が最小になるように、n個のプロセッサーで2n個のプログラムの実行を計画する必要があります。



入力形式



最初の行には、数n（1≤n≤10）-プロセッサーの数が含まれています。 次に、2n行で、実行するプログラムを指定します。 各プログラムには1〜100チームが含まれます。 各コマンドは大文字のラテン文字で示されています。



出力形式



単一の数値-すべてのプログラムを実行できる最小時間を印刷します。







タスクの例として、次のプログラムのセットが提供されます。ABBBAB CAB ABC

プロセッサが2つあるという情報。



2つのプロセッサでプログラムを実行するには、次の4つの手順が必要です。



CPU 1コア1 CPU 1コア2 CPU 2コア1 CPU 2コア2
[A] BB [A] BC [B] AB
A [B] B A [B] C [C] AB
AB [B] B [A] B C [A] B
AB [C] BA [B] CA [B]




問題の解決策を2つの段階に分け、それぞれを個別に検討します。



最初のステップは、グラフを作成することです。 その頂点は、実行する必要がある2n個のプログラムです。 グラフに重みが付けられ、2つのプログラム間のエッジの重みは、プロセッサが共同実行に費やす時間に等しくなります。 この値は、プログラムの長さの合計から、同時に実行されるコマンドを引いたものに等しくなります。 そして、そのようなコマンドはLCS（a、b）だけです。ここで、aとbはプログラムを記述する行であり、LCS（ Longest Common Subsequence 、最大共通サブシーケンス）は、2つのシーケンスの最大共通サブシーケンスを見つける関数です。



その結果、rib骨の重量を見つける機能は次のようになります。 



 int dist(String a, String b) { int[][] d = new int[a.length() + 1][b.length() + 1]; for (int[] ar : d) { Arrays.fill(ar, 1000000000); } d[0][0] = 0; for (int i = 0; i <= a.length(); ++i) { for (int j = 0; j <= b.length(); ++j) { if (i < a.length()) { d[i + 1][j] = Math.min(d[i + 1][j], d[i][j] + 1); } if (j < b.length()) { d[i][j + 1] = Math.min(d[i][j + 1], d[i][j] + 1); } if (i < a.length() && j < b.length() && a.charAt(i) == b.charAt(j)) { d[i + 1][j + 1] = Math.min(d[i + 1][j + 1], d[i][j] + 1); } } } return d[a.length()][b.length()]; }




解決策の2番目の段階は、このグラフで最大エッジの重みが最小化される完全な一致を見つけることです。 この問題を解決し、時間制限に適合する最も単純なアルゴリズムの1つは、動的プログラミングですが、すでにサブセットになっています。 サイズがk以下の頂点の各セットについて、答えを知っています。 この場合、そのようなすべてのセットを調べて、まだ含まれていない可能性のあるすべてのエッジに追加すると、k + 2以下のサイズのすべてのセットの答えを計算できます。 



  int[] d = new int[1 << (2 * n)]; Arrays.fill(d, 1000000000); d[0] = 0; for (int mask = 0; mask + 1 < 1 << (2 * n); ++mask) { if (d[mask] == 1000000000) { continue; } int i = 0; while ((mask & (1 << i)) != 0) { ++i; } for (int j = i + 1; j < 2 * n; ++j) { if ((mask & (1 << j)) == 0) { d[mask | (1 << i) | (1 << j)] = Math.min(d[mask | (1 << i) | (1 << j)], Math.max(d[mask], dist[i][j])); } } }




タスク「Processor」は、決勝戦に参加したほぼ全員によって行われました（2人を除く）。 この問題を解決するための平均時間は約18分です。 問題を最初に解決したのは、11分間のVladislav EPIFANOVでした。



包囲





タスク「包囲」については、NRU ITMOの学部の学生であるPavel KROTKOVに伝えます。







このタスクは、敵の大群が攻撃しようとしている素晴らしい都市、アルダースバーグについて語っています。 都市を維持するには、n個のアーティファクトの障壁を立て、[i]個の「マーリン」の魔法のエネルギーで各i番目のアーティファクトをアクティブにする必要があります。 その後、b [i]“ Merlins”を使用して、敵は遠くからこのアーティファクトを破壊できます。 街のディフェンダーは、敵の武器である魔法のエネルギーのマグリン、Bマーリンを持っています。 町の人々は、敵の魔術師による破壊の後、アーティファクトの最大数がアクティブのままになるように、アーティファクトをアクティブにすることにしました。 都市の防衛者が活性化するアーティファクトを選択できるようにする必要があります。



問題の詳細な声明
輝かしいアルダースベルクの街には困難が訪れています。 数分から数え切れないほどの敵の大群が攻撃を始めます。 魔法の壁だけが都市を維持するのに役立ちます。



市の防衛者の兵器庫には、障壁を立てるためにn個のアーティファクトがあります。 i番目のアーティファクトをアクティブにするには、 iマーリン（魔法のエネルギーの単位）が必要です。 その後、ビーマーリンを使用して、敵は遠くからアーティファクトを破壊できます。



街のディフェンダーは、敵のBマーリンの兵器庫に魔法のエネルギーのマグリンを持っています。 魔法のエネルギーは補充されません。 町の人々は、敵の魔術師による破壊の後、最大数がアクティブのままになるように、アーティファクトをアクティブにすることにしました。



アクティブにするアーティファクトを都市の防衛者が選択できるようにします。



入力形式



最初の行には、スペースで区切られた3つの整数A、B、およびn（0≤A、B≤105、0≤n≤1000）が含まれています。 次のn行には、数値aiとbiのペアが含まれています（1≤a i 、b i≤105）。



出力形式



最初の行に、競合の両側の最適なアクション中にアクティブのままになるアーティファクトの数を印刷します。 2行目には、都市の防御者がアクティブ化する必要があるアーティファクトの数と、これらのアーティファクトの数を印刷します。 1行の数字はスペースで区切ります。



アーティファクトには、入力で指定された順序で1から番号が付けられます。





少し歴史的な背景。 アルダースベルクは、世界の端に位置する4つの北王国の1つであるエーディルネで2番目に大きい都市です。 アルダースベルクの街は、エーディーンの国境を守る要塞の壁の周りに建てられました（ アンドジェ・サポコフスキー ）



街の防御者が多くのアーティファクトをアクティブにしたとします。 敵にとって最適な戦略は、b iが増加する順に敵を破壊することです。 実際、敵の目標はできるだけ多くのアーティファクトを破壊することです。 簡単なターゲットがある限り、不滅のアーティファクトに多くのエネルギーを費やすことは意味がありません。



アーティファクトの番号を非降順b iに付け直します。 敵が防御側の最適なアクションで破壊できない最初のアーティファクトが番号kであることを知ろう。 この仮定に基づいて、防御側の行動を説明します。 最初のk − 1アーティファクトから、破壊に費やされる合計エネルギーが少なくともB − b k +1マーリンであり、活性化エネルギーが最小になるように、いくつかを選択する必要があります。 k番目のアーティファクトをアクティブにします。 最後に、エネルギー消費の増加順に最後のn − kアーティファクトをアクティブ化します。



残念ながら、kは事前にはわかりません。 敵が破壊できない最初のアーティファクトの数を整理し、この仮定に最適な答えを構築します。



D ijを、i以下（1000まで）の数のアーティファクトをアクティブにするために必要な最小エネルギーとし、jの破壊のためにjのマーリンのエネルギー（10万まで）が必要になるようにします。 遷移：D i、j = min（D i − 1 、j、D i − 1 、j − b i + a i ）。 これらの2つのケースは、最適なD ijを実現するためにアーティファクト番号iをアクティブにする必要があるかどうかに対応します。



配列Dから、敵がk番目のアーティファクトを破壊できないために必要なエネルギーがわかります。 その後、私たちは熱心に残りを取り、活性化するのに十分なエネルギーがあります。 その結果、すべてのkを通過して、最適な答えが見つかります。



説明されているアプローチの実行時間はO（n（B + n））です。 完全なソリューションにするには、情報ストレージを追加して回答を復元する必要がありますが、これは漸近的な動作には影響しません。



ソリューションのボトルネックは、使用されるメモリである可能性があります。 D配列に保存できるのは最後の行のみであることに注意してください。 さらに、各ペア（i、j）について、最適なD ijを達成するためにアーチファクト番号iをアクティブにする必要があるかどうかを知るだけで十分です。 メモリの制限を満たすために、このビットの情報を格納するために2バイト以下を使用する必要がありました。



包囲タスクは19人によって解決されました。 Peter MITRICHEVは87分でこのタスクに誰よりも速く対処しました（Siegeタスクの前に、Peterは最初の3つを成功裏にパスしました）。



シャッフルデッキ



NRU ITMOの学生であるSergey MELNIKOVは、デッキのミキシングのタスクについて次のように語っています。







このタスクでは、デッキのミキシングメカニズムを検討する必要があります。これにより、完全にミキシングすることができます（デッキの中央から最後までのカードブロックの最小移動回数）（つまり、2枚の同一のカードが次々に移動しないことを確認します）、またはデッキを完全にミキシングできないことを報告します。 最初に、デッキは非減少の尊厳によってソートされます。 カードのさまざまな利点の数、デッキ内のカードの順序、デッキの数を考えると。







問題の詳細な声明
自動化とコンピューター化は、私たちの生活のあらゆる分野に急速に浸透しています。 , , — . — .



, , 1 t. , .



. , 1, — t. , , .



, .



, : i j , i- j- .

, , .







x — , . x .



. n — . n , . , , 1.



200000.







, , «-1», , , . , k — , . k , i j — , , .







, , :







, , . , .







. , . , .



K. , ⌈K / 2⌉ ( ⌊…⌋ ⌈…⌉ — ).



M «». , M = ⌈K / 2⌉.



, .



, 1122333344 3 ( 33), – 6. M = ⌈K / 2⌉.



( ) :



  1. K — ( ). , «» A, «» B, — C. |A| + |B| + |C| = |K|, |A| + |C| = |B| = M. 1122333344 AABBBC.



    : (B, C), , — (A, B). , (B, C)* (A, B)*, * — .



    :

    1122333344 (AABBC) ->1122333-4.34 (AAB) -> 1-2333-4.3412 (BB)



    ( , . – )



    , . : |C| > 0, C , B. |C| = 0, (A, B)*, B .



  2. K — . . A, , A-. C, C- , .




, ⌈K / 2⌉. , , «» ( ). .



. Q.







, ( ) (C 1 , C 2 ). , , . , .



, . Z, (X, Z) Z , Z Z (X 1 , Z) (X 2 , Z)…. Z- , (X, Y) , (X k , Z) (X k+1 , Y), X k+1 ≠ Z.



, (X, Z) X Z (M). M ≠ Z, Z (X, Z) (Z, ...) , Z M, (X, Z) (M, Z).



, , ⌈K / 2⌉ .



, , , . , O(N log N). , - , , . , , , : . O(n), .



« » .





():







N . , , .



, . , . , , , . , , .



, .



, , .



, .



3 258 , –1000 1000, .



Russian Code Cup .



— .



.



, . , , , . , .



, . , .



, . , , , , .



, . , , .









, . , . , . .







. , — . .



O(n 3 ) , O(n 2 ) O(n) . O(n) O(n 2 ) O(n 2 ). , O(n 3 ).



« » . , 93- .



Russian Code Cup 2012 . , , , - ( , , ), – - ( ) . , , , . , , , , ?







Mail.Ru Group



More articles:


All Articles