説明
石切りバサミは一般的なジャンケンゲームです：石はハサミを勝ち、ハサミは布を勝ち、布は石を勝ちます。二人が同じ手を出した場合、勝敗はありません。『ライフ・オブ・ザ・ビーチ』第2シーズン第8話で登場したアップグレード版のジャンケンゲームでは、この伝統的なジャンケンゲームに二つの新しいジェスチャーが追加されました：
スポック：『スターゲート・ドライブ』の主要キャラクターの一つ。 ライザード：『スターゲート・ドライブ』の反対側のキャラクター。
これらの5つのジェスチャーの勝敗関係は表1に示されています。表には甲が乙に対しての結果が記載されています。
今、小Aと小Bはこのアップグレード版のジャンケンゲームを試しています。彼らの出拳は周期性があり、ただし周期長は必ずしも一致しません。例えば、小Aが「石-布-石-剪刀-ライザード-スポック」の長さ6の周期で出る場合、彼の出拳シーケンスは「石-布-石-剪刀-ライザード-スポック-石-布-石-剪刀-ライザード-スポック-……」になります。一方、小Bが「剪刀-石-布-スポック-ライザード」の長さ5の周期で出る場合、彼の出拳シーケンスは「剪刀-石-布-スポック-ライザード-剪刀-石-布-スポック-ライザード-……」になります。
小Aと小Bが合計N回ジャンケンを行うことがわかっています。各回で勝つ人は1点を得、負けた人は0点を得ます。引き分けの場合は両方とも0点を得ます。このN回のジャンケン終了後に両者の得点を求めてください。
形式
入力形式
第一行には3つの整数N、NA、NBが含まれています。それぞれは合計でN回ジャンケンを行うこと、小Aの出拳の周期長、小Bの出拳の周期長を示します。数字と数字の間は1つの空白で区切ります。
第二行にはNA個の整数が含まれており、これは小Aの出拳のパターンを示します。第三行にはNB個の整数が含まれており、これは小Bの出拳のパターンを示します。0は「ハサミ」、1は「石」、2は「布」、3は「ライザード」、4は「スポック」を表します。数字と数字の間は1つの空白で区切ります。
出力形式
出力は1行であり、2つの整数が含まれており、それぞれ小Aと小Bの得点を示します。1つの空白で区切ります。
例1
例1入力[コピー]
10 5 6 0 1 2 3 4 0 3 4 2 1 0
例1出力[コピー]
例2出力[コピー]
シミュレーション...
説明
無向接続グラフGにはn個の点があり、n-1本の辺があります。点は1からnまで順番に番号付けられています。i番目の点の重みはWiです。各辺の長さは1です。グラフ上の2点(u, v)の距離はuからvへの最短距離として定義されます。グラフ上の点対(u, v)が距離2である場合、それらはWu × Wvの結合重みを持ちます。
グラフG上ですべての結合重みを持つ順序付き点対の中で、最大の結合重みはどれですか？すべての結合重みの合計はどのくらいですか？
形式
入力形式
第一行には1つの整数nが含まれています。
次にn-1行があり、それぞれは2つのスペースで区切られた正の整数u、vが含まれています。これらは、番号uと番号vの点がエッジでつながっていることを示します。
最後の1行にはn個の正の整数が含まれており、それぞれはスペースで区切られ、そのうちi番目の整数はグラフGにおけるi番目の点の重みWiを示します。
出力形式
出力は1行であり、2つの整数が含まれており、それぞれはグラフG上での結合重みの最大値とすべての結合重みの合計を示します。結合重みの合計は非常に大きい可能性があるため、10007で割った余りを求めます。
例1
例1入力[コピー]
5 1 2 2 3 3 4 4 5 1 5 2 3 10
例1出力[コピー]
60%のデータでは、1 < n ≤ 2000です；
100%のデータでは、1 < n ≤ 200,000、0 < Wi ≤ 10,000です。
中間点を検索して計算する際には、一度に加算と乗算を行います
説明
Flappy Birdは人気のあるシンプルなスマートフォンゲームです。プレイヤーは常にスマホ画面をクリックする頻度を調整して鳥の飛行高さを調節し、画面の右側にあるパイプの隙間を通過させなければなりません。もし鳥がパイプに衝突したり地面に落ちたりすると、ゲームは失敗となります。
ゲームのルールを簡略化および変更しました：
- ゲーム画面は長さn、高さmの二次元平面で、k個のパイプ（パイプの幅は無視）があります。
- 鳥は常にゲーム画面内を移動します。鳥はゲーム画面の左端の任意の整数の高さ位置から出発し、ゲーム画面の右端に到達したときにゲームが完了します。
- 鳥は単位時間ごとに横座標方向に右に1ずつ移動し、縦方向の移動距離はプレイヤーの操作によって決まります。画面をクリックすると、鳥は一定の高さXだけ上昇し、単位時間ごとに複数回クリックしても効果は重なることができます。画面をクリックしない場合、鳥は一定の高さYだけ下降します。鳥の横座標の位置が異なる場合、上昇する高さXと下降する高さYは異なります。
- 鳥の高さが0または鳥がパイプに当たった場合、ゲームは失敗です。鳥の高さがmの場合、上昇することはできません。
あなたはゲームを成功させることができるかどうかを判断してください。成功できる場合は、画面を通過するのに必要な最小のクリック回数を出力してください。そうでない場合は、鳥が通過できるパイプの隙間の最大数を出力してください。
形式
入力形式
第1行には3つの整数n、m、kがあります。それぞれはゲーム画面の長さ、高さ、パイプの数を示します。それぞれの整数は1つの空白で区切られます；
次のn行には、それぞれ2つのスペースで区切られた整数XとYがあります。これは、横座標位置0〜n-1で画面をクリックした場合、鳥が次の位置で上昇する高さXと、この位置で画面をクリックしなかった場合に鳥が次の位置で下降する高さYを示します。
次のk行には、それぞれ3つの整数P、L、Hがあります。それぞれは1つのパイプを示し、Pはパイプの横座標、Lはこのパイプの下端の高さ、Hはパイプの上端の高さを示します（入力データではPはすべて異なるが、大きさ順に与えられるとは限りません）。
出力形式
共に2行あります。
第一行には、ゲームを成功させることができれば1を出力し、そうでなければ0を出力します。 第二行には、第一行が1であれば成功するために必要な最小のクリック回数を出力し、そうでなければ鳥が通過できるパイプの隙間の最大数を出力します。
例1
例1入力[コピー]
10 10 6 3 9 9 9 1 2 1 3 1 2 1 1 2 1 2 1 1 6 2 2 1 2 7 5 1 5 6 3 5 7 5 8 8 7 9 9 1 3
例1出力[コピー]
例2出力[コピー]
50%のデータでは、5≤n≤20、5≤m≤10、最適解の1つの単位時間内で最大3回クリックすることを保証します；
70%のデータでは、5≤n≤1000、5≤m≤100；
100%のデータでは、5≤n≤10000、5≤m≤1000、0≤k<n、0<X<m、0<Y<m、0<P<n、0≤L<H ≤m、L+1<Hです。
dp...転送が少し難しく、間違いやすいです