モバイルYandex。Blitz：タスクを分析します

2018年、機械学習、モバイル開発、フロントエンドの3つのYandex。Blitzコンテストを開催しました。 3番目のコンテストが最近開催されました -受賞者の皆さん、おめでとうございます！ それまでの間、2番目のアルゴリズムに戻りたいと思います。そこでは、AndroidとiOS用のアルゴリズムとライティングソフトウェアのジャンクションでタスクが提案されました。 Yandexでのモバイル開発者の地位の候補者は、そのような問題を解決する経験から恩恵を受けるでしょう 。 それらのいくつかの詳細な分析を読んでください。 また、Blitzに参加しなかった場合は、まず自分で解決することをお勧めします 。

「ガス供給」のタスク

Nikaは、大手ガス会社のトップマネージャーが生産計画を支援するためのアプリケーションを開発しています。

同社は、パイプラインからd ₁ ... d _i ... d _nキロメートル離れた、n個のフィールドを検討しており、v ₁ ... v _i ... v _nのガスユニットを生産できます。 フィールドごとに個別のライセンスが販売されます。ライセンスのコストはs ₁ ... s _i ... s _nです。

フィールドを高速道路に接続するには、パイプラインを構築する必要があります。 さまざまな種類のパイプを敷設できる請負業者がこの会社を支援しています。 パイプの長さ（l ₁ ... l _i ... l _m ）と価格（p ₁ ... p _i ... p _m ）は互いに異なります。 好きなように組み合わせて使用​​できます。

同社はk枚のコインを所有しており、できるだけ多くのガスを入手したいと考えています。

請負業者に最適な注文を出せば、会社はどれくらい生産できるでしょうか？

パイプラインは、フィールドからパイプラインまでの距離より長い場合があります。

入力形式

最初の行には、整数k≤10 ⁵が含まれています。

2行目には、n≤15の整数が含まれます。

次のn行には、3つの整数d i≤100、v i≤100、s i≤100が含まれています。

数字はスペースで区切られます。

次の行には、整数m≤15が含まれています。

次のm行には、2つの整数l i≤100およびp i≤100が含まれます。数字はスペースで区切られます。

出力形式

答えがある唯一の行。

例

  116
 3
 58 7 50
 81 71 56
 52 57 31
 3
 47 9
 1 25
 18 61 

  57 

解析

まず、表記法を定義しましょう。 オブジェクトのクラスがあり、パラメータを持つDeposit（デポジット）があるとします$$ $インライン$ Dd_ {i} $インライン$ （リモート）$$ $インライン$ Dv_ {i} $インライン$ （生産量）および$$ $インライン$ Ds_ {i} $インライン$ （ライセンス費用）。 このタイプのインデックスオブジェクトは変数iになります。 パラメーターを持つPipelinerオブジェクトクラスもあります$$ $インライン$ PPl_ {j} $インライン$ （請負業者が構築できるパイプの長さ）および$$ $インライン$ PPp_ {j} $インライン$ （このパイプの価格）、jを介したインデックス。 電撃の参加者は、1種類のパイプを2回使用できるかどうかを何度も尋ねました。 いいえと仮定され、上記の例はこれを明確に示しています。 このタスクの条件により、受け入れます$$ $インライン$ D_ {i} = {0、1} $インライン$ （フィールドを選択するかどうか）および$$ $インライン$ PP_ {j} = {0、1} $インライン$ （請負業者を選択するかどうか）、線形プログラミングタスクを作成できます。

$$$ inline $ \ sum \ limits_ {i} D_ {i} * Dv_ {i} \ rightarrow max \\ \ sum \ limits_ {i} D_ {i} * Ds_ {i} + \ sum \ limits_ {j} PP_ { j} * PPp_ {j} \ leq k \\ \ sum \ limits_ {i} D_ {i} * Dd_ {i} \ leq \ sum \ limits_ {j} PP_ {j} * PPl_ {j} \\ D_ { i} = {0、1}、PP_ {j} = {0、1} $インライン$

たとえば、シンプレックス法によって解決できます。 ただし、タスクの条件により、最大生産量（つまり、目的関数の値）のみを返す必要があり、どのフィールドとどの請負業者を選択するかを示す必要はありません。 条件の制限とともに、テーブルdp [length] [money]を構築することにより、動的プログラミングによって問題を解決できます。ここで、lengthはパイプラインの長さ、moneyはmoneyです。 テーブルを正しく構築したら、その中の最大値を見つけるだけで十分です。これが答えです。 タスクのメモリ制約は構築するのに十分です。

「タワーとAI」のタスク

Artemは、敵対的なモバイルゲームをプレイする人工知能を開発しています。 ゲームのルールは簡単です。

プレーヤーの前には、高さがc ₁ ... c _i ... c _nのタワーがn _個あります。 そのターンで、プレイヤーはいくつかの小さな塔が得られるように塔の一つを壊すことができます。 プレイヤーはタワーで混乱することを恐れているため、制限に同意しました。分離後、同じ高さの2つのタワーを取得しないでください。 たとえば、高さ7のタワーは（1、2、4）に分割できますが、（1、3、3）には分割できません。 高さは常に整数です。

破壊できる塔がない人を失います。

アルテムには最適なプレイをする非​​常に賢い友人がいます。アルテムの人工知能と戦うのは彼です。 AIの動作を評価するには、Artyomは、両方のプレイヤーが最適に行動した場合にロボットが勝つべきかどうかを知る必要があります。 これで彼を助けてください。

人間は常に最初に歩きます。 彼はAI kゲームでプレイします。

入力形式

最初の行には、整数k <500が含まれています。

これに2行のkブロックが続きます。

各ブロックの最初の行は、整数0 <n≤50です。

各ブロックの2行目には、0 <c i≤50のn個の整数があります。数字はスペースで区切られています。

出力形式

k行。各行には、その人がゲームに勝ったかどうかに応じて、trueまたはfalseが含まれます。

例

  2
 1
 4
 2
 1 1 

 偽
偽 

解析

提案されているタワーゲームは、2人のプレイヤーが描くことができない、公平な最終ゲームです。

したがって、ゲーム内の特定のプレーヤーの勝利は、ゲームの状態と2人のプレーヤーの動きの順序によって決まります。 ゲーム理論に精通している読者にとっては、2人のプレーヤーの同等のゲームのいずれかが実際に「彼」のゲームと同等であることは明らかです。

ここにゲームの簡単な説明があります（ソースへのリンク -詳細なレビューのためにそれをクリックしてください）：

いくつかのヒープがあり、それぞれにいくつかの石があります。 1回の動きで、プレーヤーは任意の1つの山からゼロ以外の数の石を取り、それらを捨てることができます。 したがって、損失はそれ以上の動きがない場合に発生します。 すべての山は空です。

したがって、ゲーム「彼」の状態は、自然数の順序付けられていないセットによって一意に記述されます。 1回の移動で、任意の数値を厳密に減らすことができます（結果として数値がゼロになる場合、その数値はセットから削除されます）。

さらに、Sprag-Grandiの定理は、2人のプレーヤーの同等のゲームの状態UをサイズXの少数の彼のゲームに関連付けることができると述べています。それを解決する-すでに知られているゲーム。

タスク「評価表示」

Galyaはレビューアグリゲーターを開発しています。 彼女は、7つ星の星の助けを借りて機関の格付けを指定することにしました。

入力レンダリングシステムは、高さhと幅wの長方形を受け取り、その左上隅は点（x、y）にあります。 次の規則に従って星を描画する必要があります。

1. 星のサイズは、長方形の幅または高さ、つまり小さい方によって決まります。 （図面を参照してください。）
2. 長方形の寸法の1つが星の対応する寸法よりも大きい場合、星はその寸法の中央に配置する必要があります。
3. 星は上向きです。

レンダリングシステムは、Galiコードから星の頂点の座標を予測します。 ゲイルがそれらを計算するのを助けてください。

ガリアは、七角形の星を作成するために、通常の七角形の頂点を1つにつないで得られる図の外側の輪郭を取ります。 座標系では、X軸は左から右に、Y軸は上から下に向けられています。 Galiのプログラムはクラッシュせず、入力として不適切な幅と高さの値を受け取ります。

入力形式

単一行には、スペースで区切られた整数x、y、w、およびhが含まれます。

例：エントリ150 0 50 100は、幅が50ポイント、高さが100ポイント、左上隅がポイント（150、0）の長方形を示します。

出力形式

スペースで区切られた28個の数字を含む唯一の行は、星の頂点の座標で、上から始まり時計回りです。 数値は最も近い整数に丸める必要があります。 解決策を進める前に、出力例と問題の図を参照してください。

例：3つのポイント（1、2）、（3、4）、（5、6）の出力は次のようになります：1 2 3 4 5 6。

例

  0 0 100 100 

  50 1 65 21 90 21 85 45100 64 78 75 72 99 50 88 28 99 22 75 0 64 15 45 10 21 35 21 

注釈

• 必要な精度は有効数字10桁です。

  
  

• 座標系：X軸は左から右に向けられ、Y軸は上から下に向けられます。

  
  

• 予想される頂点の順序：

内接星の例：

解析

この問題の解決策は、3つの段階に縮小されます。空間内で目的の方向を持つ基準星を作成し、結果のポイントをスケーリングし、オフセットを計算して適用します。

スタービル
最も簡単な方法は、原点を中心とする単位半径の円に内接する星を作成することです。 外部頂点のポイントは、自明な三角法を使用して計算されますが、内部頂点では、タスクはもう少し複雑です。 それらは、少なくとも2つの方法で見つけることができます。 より簡単な方法は、外側の頂点を接続するセグメントの交点を見つけることです。 より複雑なのは、外接円の半径から内接円の半径を計算する式を見つけることです。 最初にこれを行うのが最も簡単です。たとえば、5の尖った星の場合、接続された頂点間に任意のギャップがあるNの尖った星に一般化します。

スケーリング
すべての場合において、星を収めるのに必要なサイズが与えられます。 したがって、左端から右端までの距離が指定された幅を超えず、最高から最低までの距離が指定された高さを超えないように、取得したポイントをスケーリングする必要があります。 スケーリング係数を使用して、幅と高さを目的の値にし、小さい方を選択します。 中心を原点にした基準星を慎重に作成したため、各ポイントの座標に選択した係数を掛けるだけで十分です。

オフセット
最後に残っているのは、星が指定されたフレーム内に収まるようにポイントを移動することです。 すべてのオプションの入力データは、左上隅の特定の座標を持つ境界ボックスに縮小できます。 ここではすべてが簡単です。最後の段階で得られた結果から最高点を取得し、そのy座標と左上隅のy座標の差を考慮し、すべての点を取得した値だけ垂直にシフトします。 X座標でも同じことを行います。一番上の点ではなく、一番左の点を取ります。 最後にもう1つ、星をこの長方形の中央に配置します。

さらなるアクションは、前の段階で選択した係数によって異なります。

• 高さをスケーリングした場合-長方形の幅と左から右端までの距離の差を取ります。
• 幅がスケーリングされている場合-長方形の高さと最高点から最低点までの距離の差を取ります。

得られた値を2で除算し、対応する測定値に従ってポイントをシフトします。 回答を受け取りました。

タスク「円の回転とスケーリング」

Vikaは、スマートフォンとタブレット用のグラフィックエディターを開発しています。 彼女は、次のように、ユーザーに2本の指で画面上の円を回転させ、サイズを変更する機会を与えたいと考えています。

図は、指を接続するセグメントが回転するのと同じ角度で回転します。 図のサイズは、セグメントの長さに比例して変化します。 最初に、Figureが回転し、次にそのサイズが変更されます。 最初、円には座標（x、y）と半径rがあります。 ユーザーのジェスチャーを説明するタッチイベントのリストが表示されます。 Vikaが円の中心とその半径の最終座標を計算するのを助けます。 円は、点（a、b）に対して回転します。

タッチイベントの説明には、指のID、座標、イベントのタイプが含まれます。 ユーザーがアタッチした最初の指はid 0、2番目の指はid 1などを受け取ります。

例：
0 337 490 ACTION_DOWN-これは、ポイント0（337、490）でACTION_DOWNイベントが発生したことを意味します。

タッチイベントには次の種類があります。

• ACTION_DOWN-ユーザーは、指定されたポイントで画面に最初の指を当てました。
• ACTION_POINTER_DOWN-ユーザーが特定のポイントで2本目の指を画面に適用しました。
• ACTION_MOVE-ユーザーは指を指定されたポイントに移動しました。
• ACTION_POINTER_UP-ユーザーは、2番目の指を指定されたポイントに移動してリリースしました。
• ACTION_UP-ユーザーは最初の指を特定のポイントに移動して離しました。
• ACTION_CANCEL-ユーザーがジェスチャーを中止しました。

入力形式

最初の行には、スペースで区切られた数字x、y、およびrが含まれています。 2行目には、スペースで区切られた数字aとbが含まれています。 次の数行には、連続したタッチイベントが含まれています。

出力形式

座標と半径を持つ唯一の線。 数字はスペースで区切られます。

例

  252 194 78
 445,559
 0 337,490 ACTION_DOWN
 1,599,490 ACTION_POINTER_DOWN
 1,576,564 ACTION_MOVE
 1,552,590 ACTION_MOVE
 0 407,375 ACTION_MOVE
 1 505 615 ACTION_MOVE
 1 482 620 ACTION_MOVE
 0 477 360 ACTION_MOVE
 1,435,616 ACTION_MOVE
 1,411,607 ACTION_MOVE
 0 547 386 ACTION_MOVE
 1 364 548 ACTION_POINTER_UP
 0 571 387 ACTION_UP 

  831 704 73 

注釈

結果を表示するときは、数学的な丸めの規則に従って、すべての浮動小数点値を整数値に丸める必要があります。

解析

ジェスチャは複雑に思えますが、回転とスケーリングの2つのコンポーネントに分けることができます。 図を回転させるには、回転角を計算する必要があります。回転角は次の式を使用して取得できます。
a = atan2（prevTouchX2-prevTouchX1、prevTouchY2-prevTouchY1）-atan2（currentTouchX2-currentTouchX1、currentTouchY2-currentTouchY1）。

回転角度を受け取ったら、フィギュア自体を回転させる必要があります。これにより、フィギュアの各ポイントを回転角度だけ回転させることになります。 図を回転させた後、それを拡大縮小する必要があります。 図のスケーリングは非常に簡単です。 2本目の指のACTION_POINTER_DOWNイベントを受信するときは、1本目と2本目の指の間の距離を覚えておく必要があります。その後、最初の2本の指の間の距離を追跡することで、図をスケーリングするために必要な係数を計算できます。

タスク「道路建設」

モバイルゲームでは、主人公は遠くの惑星に基盤を構築します。 彼は周囲から始まります-直接レーザー壁で接続された塔。 本社の建築家は、座標（x ₁ 、y ₁ ）...（x _i 、y _i ）...（x _n 、y _n ）を持つn塔を示す計画を彼に送信します。 基地防衛の観点からは、3本以上の隣接する塔を1本の直線上に置くことは意味がありません。 ただし、スタッフアーキテクトはこのようにタワーを配置することがあるため、プレイヤー自身が余分な中間タワーを削除する必要があります。

境界線を使い終えると、ヒーローはベースを内側から装備し始めます。 彼はタワー間にk本の道路を建設したいと考えています。道路は、隣接していない2つのタワーを接続できますが、別の道路や壁を横切ることはできません。 1つの塔からは、好きなだけ道路を出ることができます。

主人公はp個の道路ロボットを持っています。 最適な道路建設計画を選択するために、ヒーローは可能なすべてのオプションを並べ替えるよう指示します。 ロボットは同時に何度も何度も動作を開始し、同時に道路の位置に独自のオプションをもたらします。 次の反復の前に、ロボットよりも残りのオプションが少ないことが判明した場合、余分なロボットは解放され、夕食を調理するためにキッチンに送られます。 残りのロボットは最後のオプションを終了し、電源を切ります。

基地の外の道路を舗装できることが判明した場合、ヒーローは基地を安全でないと宣言し、惑星から飛び去ります。

キッチンで何台のロボットが動作しますか？

入力形式

最初の行には、3つの整数4≤n≤10 7、1≤k≤n、および素数105 <p <11×104が含まれます。数字はスペースで区切られます。

次のn行には、0 <x _i 、y _i <109の2つの整数が含まれています。数字はスペースで区切られています。

出力形式

答えがある唯一の行。 ベースが安全でない場合、-1を印刷します。

例1

  4 1 101363
 0 0
 1 0
 1 1
 0 1 

  101361 

唯一の道路を舗装する方法は2つあります：（0、0）-（1、1）および（1、0）-（0、1）。 2つのロボットがそれらに従事し、残りはキッチンに行きます：p-2 = 101 361。

例2

  4 1 101363
 1 0
 2 0
 0 1
 1 2 

  -1 

ここでは、（1、0）-（0、1）の間の道路を構築できますが、これはベースの外側にあります。 主人公は基地を安全でないと認識し、答えは-1です。

例3

  4 1 101363
 0 0 
 1 0
 2 0
 0 1 

  101363 

塔（0、0）、（1、0）、および（2、0）は同じ線上にあるため、ヒーローは中央の塔（1、0）を建設しません。 道路を舗装することはできないため、すべてのロボットはすぐにキッチンに行きます：p = 101 363。

解析

問題の解決策を3つのステップに分けます。

最初のステップは、入力頂点データセットについて、多角形が凸面かどうか、もしそうなら、実際の頂点の数を決定することです。 すべての頂点がエッジをサポートするラインの片側にある場合、ポリゴンは凸型です。 隣接する頂点の各トリプルについて$$ $インライン$（x_ {i-1}、y_ {i-1}）、（x_ {i}、y_ {i}）、（x_ {i + 1}、y_ {i + 1}）$ inline $ いくつかのベクトルを構築する$$ $インライン$ ab =（（x_ {i-1}、y_ {i-1}）、（x_ {i}、y_ {i}））およびbc =（（x_ {i}、y_ {i}）、 （x_ {i + 1}、y_ {i + 1}））$インライン$ 、および式ab.x bc.y-bc.x ab.yの符号を計算します。 式が0の場合、頂点は1つの直線上にあり、問題の状態に応じて、中央の頂点にあるタワーが消え、タワーの総数が減少します。 すべての頂点のトリプルで積符号が0または常に同じである場合、2番目のステップに進みます。そうでない場合は、ベースが安全でないと見なし、答え-1を出力します。

2番目のステップ。 凸N角の内部にk個の互いに素な対角線を構築する方法の数は$$ $ inline $ V = 1 /（k + 1）{N-3 \ choose k} {N + k-1 \ choose k} $ inline $ 、しかし、式p-V mod pを計算する必要があります。ここで、pは素数です。

Nを想像してください！ どうやって$$ $インライン$ a * p ^ e $インライン$ ここで、最大公約数はaであり、p gcd（a、p）= 1です。

$$$ inline $ {n \ choose r} =（n！）/（r！（nr）！）= a_ {1} * p ^ {e_ {1}} / a_ {2} * p ^ {e_ {2} } * a_ {3} * p ^ {e_ {3}} =（a_ {1} / a_ {2} * a_ {3}）* p ^ {e_ {1} -e_ {2} -e_ {3} } $インライン$

もし$$ $インライン$ e_ {1} -e_ {2} -e_ {3}> 0 $インライン$ 、式はpで完全に割り切れ、問題の答えは数pです。

ケース用$$ $インライン$ e_ {1} -e_ {2} -e_ {3}> 0 $インライン$ = 0答えは$$ $インライン$ a_ {1} / a_ {2} * a_ {3} $インライン$ mod p。

計算では、 a b mod p =（a mod p） （b mod p）mod p、および$$ $インライン$ k ^ {-1} $インライン$ mod p =$$ $インライン$（k）^ {p-2} $インライン$ 素数pのmod p。

第三のステップ。 式を計算するには$$ $インライン$ e_ {1} -e_ {2} -e_ {3} $ inline $ 想像してみて！ as 1 2 ... p （p + 1） ... 2p （2p + 1） ...、while（p + 1） ... （2p-1）mod p = 1 2 ...（p-1 ）=（p-1）！..合計、n mod p =（$$ $ inline $（p-1）！^ k $ inline $ k （n mod p）！）mod p、k = floor（n / p）。

タスク「Super Simple Scheduler」

スマートフォンのプロセッサで実行するタスクはn個あります。 それらの実装には時間単位t ₁ ... t _i ... t _nが必要であり、 _i番目の時間単位の開始までにi番目のタスクを完了する必要があります。

間に合うように、タスクは複数のスレッドで実行できますが、新しいスレッドごとにバッテリーの負荷が増加します。 最初のストリームでは、単位時間あたりのエネルギー単位が消費され、2番目の1.5単位ではエネルギーが消費され、3番目では1.5秒単位でエネルギーが消費されます。

タスクは時間単位に分割できます。最初に部分的に完了し、次に別のタスクに移動してから、最初のタスクに戻ります。 異なるスレッドでタスクの異なる部分を同時に実行することは不可能です。

スケジューラは一度に1つのタスクを受け取ります。 タスクを受信すると、彼はすぐにそのタスクにタイムスロットを割り当てます。 タスクが配布された後、スケジューラはそれを他のスロットに転送できません。

すべてのタスクが最適に分散されている場合、すべてのタスクを完了するにはどのくらいのエネルギーが必要ですか？

入力形式

最初の行には、整数1 <n≤3×10 ³が含まれています。
次のn行には、0≤t i≤10 ⁴および0≤d i≤10 ^4の 2つの整数が含まれています。 数字はスペースで区切られます。

出力形式

答えがある唯一の行。 精度-小数点以下8桁。

例

  5
 2 2
 1 1
 3 4
 1 10
 1 2 

  10.25000000 

解析

問題の状況に応じて、消費されるエネルギー量のみを計算すれば十分なので、時間単位ごとに消費されるエネルギー量を計算することにより、解法を使用できます。 タスクを計画するとき、消費されるエネルギーの最小値k = 1を取り、タスクの期限から開始して、時間間隔のすべてのスロットをソートします。

スロットのエネルギー消費が係数（k）より小さく、タスクを計画するときにこのタイムスロットが使用されなかった場合、このスロットを占有して、スロットの係数をK増やしてタスクを完了します。期間の開始に達すると、係数kを1.5倍増やし期限からタスクが完全に計画されるまで、タイムスロットの検索を繰り返します。 すべてのタスクの計画が完了すると、取得した各時間単位の係数を加算して総エネルギー消費量を計算するだけです。

破壊可能なオブジェクトのタスク

2Dゲームでは、オブジェクトを破壊できます。 ゲームは開発段階にあり、これまでのところ、すべてが非常に簡単に行われています：破壊可能なオブジェクトは、ポイント（x ₁ 、y ₁ ）...（x _i 、y _i ）...（x _n 、y _n ）。 アルゴリズムは、最小数の凹面頂点を取り、それを最も近い非隣接頂点に接続します-そのため、接続セグメントの長さは最小になります。 次に、結果のポリゴンで同じことが行われます。 凸面のポリゴンのみが残るまで、すべてが繰り返されます。これらは、プレイヤーが見るフラグメントです。

たとえば、頂点[0 1 2 3 4]の多角形があり、頂点1が凹で頂点3が最も近い場合、アルゴリズムは頂点1と3を接続して、頂点[1 2 3]と[0 1 3 4]を持つ図形を取得します。

アルゴリズムは、接続セグメントを描画して、完全にポリゴンの内側に配置します。 リブ間の角度が発達した頂点は、凸と見なされます。 複数の等距離の頂点にセグメントを構築することが可能である場合、アルゴリズムはより小さい番号の頂点を選択します。

オブジェクトを破壊するために構築されたすべてのセグメントの長さの合計は何ですか？

入力形式

最初の行には、n≤500の整数が含まれます。次のn行には、2つの整数xとyが含まれます。 数字はスペースで区切られます。

出力形式

答えがある唯一の行。 精度-小数点以下6桁。

例1

  4
 100 100
 200 100
 200 200
 100 200 

  0.000000 

例2

  6
 167 84
 421 84
 283 192
 433,298
 164,275
 320 133 

  326.986753 

解析

問題の主な難点は、セグメントがポリゴン内の2つの頂点の間にあるかどうかを判断することです。 この問題を解決した後、すべての接続オプションを徹底的に検索することにより、問題の上記の条件を「正面から」満たすことができます。実行時間と頂点の数の制限はかなり緩やかです。 マイナーポイント：凸状および凹状の頂点の決定、およびトラバースの方向（頂点が時計回りまたは反時計回りに設定されているかどうか）は、ベクトルのスキュー積を使用して簡単に解決されます。

問題は、ラインセグメントがポリゴン内にあるかどうかです。 必要な条件は、セグメントとポリゴンの他の側面との交差がないことです（セグメントの端である頂点に隣接する側面を除く）。 ただし、この条件では十分ではありません。2つの頂点を接続するセグメントが外側になり、同時にその辺と交差しない図を簡単に見つけることができます。 したがって、必要な条件が満たされている場合、このセグメントのいずれかのポイント（エンドポイントを除く）がポリゴン内にあるかどうかを判断する必要があります。 これは、いわゆる偶奇規則を使用して行うことができます。この点から目に見えない光線を投げ、多角形の辺との交点の数を計算します。 交差点の数が奇数の場合、ポイント（およびセグメント全体）はポリゴンの内側にあり、そうでない場合は外側にあります。

もちろん、このタスクには落とし穴があります。解決策がシンプルで明白な場合、最終ラウンドでは提供されません。 実装中に発生する可能性のある問題は次のとおりです（もちろん、リストは続行できます）。

• 隣接する頂点の決定（ゼロインデックスを通過する場合）;
• 平行線：いずれかの側が問題のセグメントと部分的または完全に一致する場合。
• 丸め誤差（一般的な場合、浮動小数点数は特定の値内で比較する必要があります。この場合、テストに合格するには10e-5以上の値で十分でした）。
• 偶奇規則を実装する場合、光線が頂点を通過する場合。
• ビームが上部を通過する場合、別の落とし穴があります。ビームが上部を通過し、側面間で180度の角度で、これらの側面と一致する場合です。

DNAチャレンジ

Good Corporationは、遺伝子型によって人々を即座に識別するデバイスを開発しました。 人が指で特別なセンサーに触れると、デバイスはDNAの特定のフラグメントを取得し、このフラグメントのデータベースに保存されているシーケンスを探します。 DNAフラグメントとn個の異なるシーケンスの例を示します。 デバイスが見つける部分文字列のリストを作成します。 DNAには、A、T、G、Cの4つの文字があります。検索シーケンスは部分的に重複する場合があります。 シーケンスは、別のシーケンスの開始と完全に一致することはできません。

入力形式

最初の行には整数nが含まれています。 次のn行には1つのDNA配列が含まれています。 最後の行には、テストするDNAフラグメントが含まれています。 入力データの合計量は、 ⁶ ×10 ⁶文字を超えません。

出力形式

出力の各行に、チェックされるフラグメント内のシーケンスの1つのオカレンスを書き込みます。 開始位置番号とサブストリング自体を示します。 1つをスペースで区切ります。 DNAフラグメントの文字の番号付けは1から始まります。 開始位置番号で出力をソートします。 タスクを開始する前に例を必ず確認してください。

例

入力 （フラグメントをエディターにコピーして、全体を表示します）：

5
TTT
GAAGCT
CAAT
AGA
アグカ

2 TTT
6 AGA
28 AGA
30 AGA
57 CAAT
86 AGA
100 GAAGCT
190 TTT
191 TTT
196 AGA
219 TTT
232 AGA
271 TTT
284 TTT
285 TTT
298 TTT
320 TTT
330 TTT
331 TTT
342 TTT
373 AGA
397 AGA
488 AGA
509 AGA
524 AGA
565 TTT
574 AGA
605 AGA
625 CAAT
630 AGA
681 CAAT
718 TTT
719 TTT
744 AGGCA
754 AGA
784 AGA
808 TTT
821 CAAT
833 AGA
861 CAAT
879 AGA
921 AGA
955 AGA

解析

これは決勝戦の最後のタスクですが、複雑さの最後のタスクではありません。 この問題の解決策は、Aho-Korasikアルゴリズムを使用するなど、最適な方法で文字列のパターンを見つけることでした。 アルゴリズムは、状態文字列を構築し、検索文字列を渡します。 機械は文字列のすべての文字を順番に受け取り、対応するエッジに沿って移動します。 マシンが終了位置に達すると、対応する辞書行が検索行に存在します。

全体の難しさは、ラインのそのような解決策を見つける必要があるということでした。

QR Questタスク

入力形式

最初の行には、テストケースの数を示す単一の整数tが含まれています。 次のt行には、スペースで区切られた8つの整数n _iが含まれています。

出力形式

t行。各行には1つの整数が含まれます。

例1

  4
 8 10 1 9 2 6 7 8
 14 2 0 11 10 4 1 0
 6 6 4 1 10 0 11 6
 11 4 3 4 14 8 12 5 

  0
 13
 15
 5 

例2

  4
 9 10 6 2 12 11 7 2
 3 10 1 14 13 13 1 1
 6 8 8 5 3 2 6 4
 5 11 5 5 3 1 10 7 

  3
 9
 2
 7 

解析

ソリューションメソドロジを考えなければならなかったため、このボーナスタスクを最も好奇心for盛な人に任せました。 QRコードは、3つの値のテーブルを含むドキュメントへのリンクをたどることを許可しました。 これらの値では、いくつかの操作が必要でした。

合計8つの数字が入力されました-これらのテーブルのセルの座標、つまり、列と行の座標との4つのペア。 これらのセルで実行された操作と、どのテーブルから追加のセルが実行されたかを推測する必要がありました。

簡単な操作を使用して、これがテーブルA、B、Cの4つのセルのxor-sumであり、インデックスa ₀ ... a ₇でアドレス指定されていることを確認できました。
R = A [a ₀ 、a ₁ ] ^ B [a ₂ 、a ₃ ] ^ B [a ₄ 、a ₅ ] ^ C [a ₆ 、a ₇ ]。