ロシアコードカップ2013：最初の予選ラウンドのタスクの分析

制限時間 -1秒
256 MBのメモリ制限
現在、ノームランドでは、今後のオリンピックに備えています。 ノーム・ブリゲーダーには、ハートボール、ジョーダンボール、メドボールをプレーするためのフィールドを構築する任務が与えられました。 各フィールドは長方形です。 ゲームのルールに従って、フィールドは、その側面が南北方向と西東方向に平行になるように配置する必要があります。
ノームランドの土地は非常に高価であるため、ゲームの主催者は土地の購入にできるだけお金をかけたくないと考えています。 Hertball、Jordanball、Medwebolの競技会は異なる時期に開催されるため、フィールドが重複する可能性があります。
ドワーフが、建設後に3つのフィールドが占有できる最小面積を見つけるのに役立ちます。
最初の例で考えられる最適なフィールドレイアウトの1つを図に示します。

入力形式
入力データには1000行以下が含まれ、各行には3つのフィールドの説明が含まれます。6つの自然数で、それぞれ10000を超えません。
最初と2番目の数字は最初のフィールドのサイズ、3番目と4番目-2番目のフィールドのサイズ、5番目と6番目-3番目のフィールドのサイズを示します。
入力は、6つのゼロのストリングで終了します。 このリクエストを処理する必要はありません。
出力形式
各セットに対して、3つのフィールドが占めることができる最小領域である数字を印刷します。

2秒の制限時間
256 MBのメモリ制限
アントン・セルゲイエビッチは、台形地図を作成するためのアルゴリズムを学生に教えました。 準備運動として、彼は空中ブランコのタスクを彼らに与えました。 彼はボード上にn個のセグメントを描きました。 i番目のセグメントの長さはaiです。 学生は、ゼロ以外の面積の二等辺台形を作成できる4つのセグメントの異なるセットの数を見つける必要があります。
二等辺台形は四角形であり、その2つの反対側は平行であり、他の2つは等しいことを思い出してください。 等脚台形の例を図に示します。

最初のセットに属し、2番目のセットに属さないセグメントがある場合、2つのセットは異なると見なされます。 各セットで取得されるセグメントの数は、ペアごとに異なる必要があります。
学生がそのようなセットの数を見つけるのを助けます。
入力形式
最初の行には数字tが含まれています-アントンは生徒にこの課題を何度も与えました。 次の2t行には、すべてのタスクの説明が含まれています。
各タスクの説明は2行で構成されています。 説明の最初の行には、番号n-ボードに描かれたセグメントの数が含まれています。 問題の説明の2行目は、n個の整数ai-その長さ（1からnまでのすべてのiに対して4≤n≤5000、1≤ai≤108）を与えます。
すべてのタスクのすべてのセグメントの総数は5000を超えません。
出力形式
個別の行の各タスクについて、1つの数字-必要なセット数を印刷します。

2秒の制限時間
256 MBのメモリ制限
2345年に発見された化学元素ムランは非常に放射性が高いです。 ムーランの不適切な取り扱いは予測できない結果を招く可能性があるため、ムーランを使用、保管、輸送する際には特別な注意が必要です。
ムラノには多くの異なる同位体があり、それぞれが1つの自然数-原子質量によって特徴付けられます。 質量の合計がk個の「臨界数」の1つに等しい同位体のペアを一緒に長期間保管すると、この同位体のペアが反応し、爆発が発生します。 すべてのクリティカル数は、2の非負のべき乗であることが知られています。
フラットランド原子力研究所では、ムラノのサンプルは2つの特別な倉庫に保管されています。 科学者は、n個の異なるムラン同位体を取得することができました。その質量は1からnまでの数字です。 ここで、保管のために倉庫に同位体を配布する必要があります。 安全な方法とは、各同位体を1つの倉庫に保管し、質量の合計が「クリティカル数」のいずれかと等しい2つの異なる同位体を異なる倉庫に保管する保管方法です。
科学者がMluranを保管するためにいくつの異なる安全な方法を見つけ出すのを助けます。
入力形式
タスクへの入力には、いくつかのテストスイートが含まれます。 各セットの説明は2行で構成されています。
説明の最初の行には、2つの整数nおよびk（1≤n≤1018、1≤k≤61）-格納する必要のある同位体の数、および「臨界数」の数が含まれます。 次の行にはk個の異なる自然数が含まれています。各自然数は2のべき乗であり、2n-臨界数を超えていません。 クリティカル数はスペースで区切られます。
各テストのデータセットの数は10,000を超えません。テストの最後の行には2つのゼロが含まれます。
出力形式
別の行の各テストセットについて、109 + 7を法として2つの倉庫にすべての同位体を保存する安全な方法の数を印刷します。

2秒の制限時間
256 MBのメモリ制限
ウラルでのals石の最近の落下の後、多くの国の政府は小惑星から地球を保護することを考えました。 このために、国際Anti石防止機構（MAMA）が設立され、宇宙物理学の分野で最高の科学者が招待されました。
数週間にわたって、科学者たちはn個の小惑星が地球のすぐ近くを飛ぶことを発見しました。小惑星が地球からのRよりも厳密に大きい場合、それは危険ではありません。 簡単にするために、科学者は地球の近くのすべての小惑星が直線で飛ぶことを示唆し、ゼロ時間でそれらの位置と速度ベクトルを決定しました。 今、科学者たちは、ある時点でいくつの小惑星が地球に危険をもたらすかについての質問に答える方法を学びたいと思っています。
便宜上、直交デカルト座標系を導入します。 地球に座標（0、0、0）を持たせます。 すべての小惑星と地球は、宇宙の物質的なポイントと見なされます。
特定の時点についていくつかの質問がありました。 それらのそれぞれについて、この瞬間にいくつの小惑星が地球に危険をもたらすかを決定する必要があります。
入力形式
最初の行には、2つの整数nおよびR（1≤n≤100000、1≤R≤106）-小惑星の数と危険ゾーンの半径が含まれています。
次のn行のそれぞれには、xi、yi、zi、vxi、vyi、およびvziの6つの整数が含まれます（-106≤xi、yi、zi≤106、-100≤vxi、vyi、vzi≤100）-初期値を指定する座標i番目の小惑星の位置と速度のベクトル。 速度ベクトルが0に等しくないことが保証されています。
次の行には、1つの整数m（1≤m≤100000）-科学者が関心を持っている時点の数が含まれています。
次のm行のそれぞれには、1つの整数ti（0≤ti≤107）が含まれています。これは、科学者が興味を持つ時点です。
出力形式
時間の各瞬間について、単一の整数-危険ゾーンにある小惑星の数を出力します。

2秒の制限時間
256 MBのメモリ制限
2112年は終わりに近づいており、あなたは志を同じくする人々の小さなチームとともに、ある放棄された国で宝物を探しに行くことにしました。 この国の都市は、両方向に移動できる道路に接続されています。 あなたは、この国の住民がこれらの道路に沿って宝物を埋めることを愛していたことを知っています。 したがって、あなたはこの国のすべての道路に沿って運転し、埋蔵された宝物を見つけたいです。 事前に効果的な旅行計画を立てる必要があります。 これを行うには、旅行を開始する都市を選択します。 次に、道路に沿って移動し、さらにいくつかの都市を訪れます。 作成された計画は、各道路が一度だけ訪問される場合に有効と呼ばれます。
計画は1つの事実によって複雑になります。 都市のいくつかのペアはテレポーターによって接続されています。 たとえば、都市Aと都市Bがテレポートで接続されている場合、都市Aへの道路に到着すると、すぐに都市Bにテレポートし、都市Bに接続されている道路のみを運転し続けることができます。都市B、その後すぐに都市Aにテレポートし、都市Aに接続している道路に沿って進みます。
各都市は、他の1つの都市にのみテレポートできます。 効果的な旅行計画を立てる必要があります。
入力形式
入力には、いくつかのテストの説明が含まれます。 各テストの構造は次のとおりです。 最初の行には3つの整数n、m、k（1≤n≤105、1≤m≤105、0≤k≤105）が含まれています-都市の数、道路の数、テレポーターの数。 次のm行には、次の道路で接続されている都市の数という2つの異なる数字が含まれています。 次に、k行には、テレポーターによって接続されている都市のペアを表す2つの異なる番号が含まれています。
2つの都市間に複数の道路が存在する場合があります。 道路で接続されている都市はありません。 都市はそれ自体にテレポートされません。 どの都市も他の1つの都市にテレポートされます。
すべてのテストでの都市の総数が105を超えないことが保証されています。同様に、道路の合計数とテレポーターの合計数も105を超えません。入力の最後の行には3つのゼロが含まれます。 それらを処理する必要はありません。
出力形式
各データセットについて、次の形式で回答を印刷します。効果的な訪問計画を作成できない場合は、唯一の行に番号を印刷します。 そうでない場合は、最初の行に「はい」、2番目の行に-道路番号を示すmの数字を印刷します。 道路は、訪問しなければならない順序で表示する必要があります。 道路は、入力で指定された順に1から番号が付けられます。 各テストでは、道路に個別に番号が付けられます。