Time Limit: 2 sec / Memory Limit: 256 MB
問題文
C さんは斜めがけの鞄を愛用しています。 しかし、片方の肩にばかり鞄をかけていると、身体が歪んでしまうと言われたため、両方の肩に同じ時間だけ鞄をかけるように心がけることにしています。
C さんの住んでいる国には、n 個の街と、街同士をつなぐ m 個の道があります。 どの 2 つの異なる道に関しても、結んでいる 2 つの街同士が一致することはありません。
C さんはある日、街 s から街 t へと移動する必要が出てきました。 そこで、途中の街 u で一度だけ鞄を持ち替えて、左右の肩に鞄をかける時間を同じにしたいと考えています。 しかし、C さんは最強最速なので、街 s から街 u、街 u から街 t への移動は最短経路を通ります。
このような街 u の選び方があるかどうかを求めてください。
入力
入力は以下の形式で与えられる。
n m s t x_1 y_1 d_1 x_2 y_2 d_2 ... x_m y_m d_m
- 1 行目には、街の数を表す整数 n (3 \leq n \leq 1{,}000) と、道の数を表す整数 m (1 \leq m \leq min(n(n-1)/2, 10^4)) が与えられる。
- 街にはそれぞれ 1 から n までの番号が振られている。
- 2 行目には、出発する街の番号を表す整数 s (1 \leq s \leq n) と、目的地の街の番号を表す整数 t (1 \leq t \leq n) が与えられる。
- 続く m 行には、各道の情報が与えられる。
- x_i, y_i (1 \leq x_i, y_i \leq n かつ x_i \neq y_i) と d_i (1 \leq d_i \leq 1{,}000) は、i 番目の道によって街 x_i と街 y_i の間を移動するのに d_i の時間がかかることを意味する。
- 街 s から街 t へは到達可能であることが保証される。
出力
答えとなる街 u が存在する場合は、その街の番号を 1 行で出力せよ。
答えの候補が複数ある場合は、どれを出力してもよい。
また、そのような街 u が無い場合は -1 を出力せよ。
最後は改行し、余計な文字、空行を含まないこと。
入力例1
3 3 1 2 1 3 3 3 2 3 1 2 1
出力例1
3
街 1 から街 2 へ行く際に、街 3 を経由した場合、1 → 3 で 3 の時間がかかり、3 → 2 で 3 の時間がかかるため、街 3 を経由して、そこで鞄を持ち替えればよい。
入力例2
4 4 1 3 1 2 2 1 4 3 2 4 3 3 4 5
出力例2
-1
1 → 2 → 4 → 3 という順に移動すれば、街 4 で鞄を持ち替えることで左右にかかる負担を同じにすることができるが、C さんは街 1 から街 4 まで最短経路を通るので、このような移動のしかたはできない。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
CODE FESTIVAL 2014 の参加者のうち、n 人の人がホテルに宿泊しようとしています。
ホテルには m 個の部屋があり、部屋 i には高さが a_i の枕が置いてあります。 ホテルの部屋はあまり広くないため、1 つの部屋には高々 1 人しか宿泊することができません。 参加者はそれぞれ枕の高さに対して好みがあり、i 番目の参加者は x_i 以上 y_i 以下の高さの枕を好んでいます。
できるだけ多くの参加者が好みの枕を使うことができるようにホテルの部屋を割り当てたときに、好みの枕を使うことができる人数を求めてください。
入力
入力は以下の形式で与えられる。
n m x_1 y_1 ... x_n y_n a_1 ... a_m
- 1 行目には、宿泊する人数を表す整数 n (1 \leq n \leq 100{,}000) と、ホテルの部屋の数を表す整数 m (1 \leq m \leq 100{,}000) が与えられる。
- 続く n 行には、各参加者の枕の高さに対する好みの範囲が与えられる。
- x_i, y_i (1 \leq x_i \leq y_i \leq 100{,}000) は、i 番目の宿泊者が x_i 以上 y_i 以下の高さの枕を好むことを意味する。
- 続く m 行には、ホテルの各部屋にある枕の高さが与えられる。
- a_i (1 \leq a_i \leq 100{,}000) は、i 番目の部屋にある枕の高さが a_i であることを意味する。
出力
できるだけ多くの参加者が好みの枕を使えるようにホテルの部屋を割り当てたときに、好みの枕を使うことができる人数を 1 行で出力せよ。
最後は改行し、余計な文字、空行を含まないこと。
入力例1
3 3 1 2 2 3 3 4 1 2 3
出力例1
3
入力例2
3 3 1 2 2 3 3 4 2 4 5
出力例2
2
入力例3
3 4 1 4 2 3 5 5 2 4 5 6
出力例3
3
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
一人暮らしをしている amylase さんは、夏に帰宅したとき部屋が暑くてつらい思いをしていました。 amylase さんは、帰宅した時にすでに部屋を涼しい状態にするために、家の外からエアコンを ON にしたいと考えました。
そこで、PC の CD トレイの前にエアコンのスイッチを置くことで CD トレイを開閉するたびにスイッチを押す装置を制作しました。 これにより、CD トレイを遠隔操作によって開閉することで、離れた場所からエアコンの ON と OFF を切り替えられるようになりました。
このエアコンのスイッチは初期状態が OFF であり、1 回スイッチを押すたびにエアコンの OFF と ON が切り替わります。
しかし amylase さんは小学校の図画工作で成績 1 をもらうほど不器用だったので、CD トレイを 1 回開閉しても確率 p でしかスイッチが押せないことがわかりました。
ヤケになった amylase さんは CD トレイを n 回開閉しました。
このとき、最終的にエアコンが ON になっている確率を求めてください。
入力
入力は以下の形式で与えられる。
p n
- 1 行目には、スイッチを押せる確率を表す小数 p (0 \leq p \leq 1) と、CD トレイを開閉した回数を表す整数 n (1 \leq n \leq 10^{18}) が与えられる。
- p は最大で小数第 10 位まで与えられる。
出力
最終的にエアコンが ON になっている確率を 1 行で出力せよ。
絶対・相対誤差のうち少なくとも片方が 10^{-6} 以下ならば正解とみなされる。
最後は改行し、余計な文字、空行を含まないこと。
入力例1
0.3 1
出力例1
0.3
入力例2
0.0000000001 10000000000
出力例2
0.432332358362
極端な入力に対して誤差が出ないように注意しましょう。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
今、直線上に並んだマスの上に n 匹のぽよくんが存在しており、i (1 \leq i \leq n) 番目のぽよくんは、p_i の位置にある杭に長さ l_i の鎖で繋がれています。 つまり、 i 番目のぽよくんは p_i - l_i から p_i + l_i の範囲（両端を含む）のマスを自由に動くことができます。
ぽよくんが添字の順に左からそれぞれ異なるマスにいるとき、ぽよくん達の配置は何通り考えられますか。 つまり、次の条件をみたすぽよくんの位置の組み合わせとして考えられる場合の数を求めてください。 i (1 \leq i \leq n) 番目のぽよくんの位置を x_i として、
位置の組み合わせが互いに異なるとは、少なくともどれか一匹のぽよくんについて、位置が異なることだとします。
答えは非常に大きな値になるので、1{,}000{,}000{,}007 で割った余りを答えてください。
入力
入力は以下の形式で与えられる。
n p_1 l_1 p_2 l_2 ... p_n l_n
- 1 行目には、ぽよくんの総数を表す整数 n (1 \leq n \leq 1,000) が与えられる。
- 続く n 行には、i 番目のぽよくんが繋がれている杭の位置を表す整数 p_i (0 \leq p_i \leq 1,000,000,000) と、i 番目のぽよくんを繋いでいる鎖の長さを表す整数 l_i (0 \leq l_i \leq 1,000) が与えられる。
- i \lt j であるとき、p_i \lt p_j であることが保証されている。
出力
ぽよくんの可能な配置の総数を 1,000,000,007 で割った余りを 1 行で出力せよ。
最後は改行し、余計な文字、空行を含まないこと。
入力例1
1 0 3
出力例1
7
ぽよくんの可能な配置は、-3, -2, -1, 0, 1, 2, 3 の 7 通りです。
入力例2
2 0 3 1 2
出力例2
20
ぽよくんの可能な配置の総数は、(1 番目のぽよくんの位置, 2 番目のぽよくんの位置) とすると、 (-3, -1), (-3, 0), (-3, 1), (-3, 2), (-3, 3), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-2, 3), (-1, 0), (-1, 1), (-1, 2), (-1, 3), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) の 20 通りです。