A - eject

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

極端な入力に対して誤差が出ないように注意しましょう。

B - ぽよぽよ

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 として、

  • x_i は整数
  • p_i - l_i \leq x_i \leq p_i + l_i
  • どのような j (1 \leq j \leq n) についても、 i \lt j であるならば、 x_i \lt x_j となっている

    • 位置の組み合わせが互いに異なるとは、少なくともどれか一匹のぽよくんについて、位置が異なることだとします。

    答えは非常に大きな値になるので、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 通りです。

    C - 宝探し 2

    Time Limit: 5 sec / Memory Limit: 256 MB

    問題文

    太郎君は、ある広場にお宝を探しにやってきました。

    この広場には、水平な方向に n 本、垂直な方向に m 本の線が等間隔に引かれています。隣接する線同士の距離は 1 です。
    上から i 番目の水平な線と左から j 番目の垂直な線が交わる点の位置は (i, j) で表され、そこには k 種類のうちの 1 つのお宝が 1 つだけ埋められています。

    太郎君は最新の機械を持っているので、どこにどのようなお宝が埋まっているかをすべて知っています。
    そこで、太郎君はこの広場の中のさまざまな長方形の領域に対して、その中にどのようなお宝が多く埋まっているかを調べようとしています。

    しかし、次郎君がときどきいたずらをして、隣接しているお宝の位置を入れ替えてしまいます。
    ここでお宝が隣接しているとは、それぞれのお宝が埋まっている点同士の距離がちょうど 1 であることを言います。

    次郎君のいたずらに困ってしまった太郎君に代わって、与えられた各領域に対して、その時に領域の中にある最も数の多いお宝を求めてください。

    入力

    入力は以下の形式で与えられる。

    n m k
a_{1,1} a_{1,2} ... a_{1,m}
...
a_{n,1} a_{n,2} ... a_{n,m}
q
t_1 x_{11} y_{11} x_{21} y_{21}
...
t_q x_{1q} y_{1q} x_{2q} y_{2q}
    • 1 行目には、広場に引かれた水平な線の本数を表す整数 n (1 \leq n \leq 500)、垂直な線の本数を表す整数 m (1 \leq m \leq 500) と、広場に埋められているお宝の種類数を表す整数 k (1 \leq k \leq 100) が与えられる。
    • 続く n 行には、広場の各位置に埋められているお宝の種類が与えられる。
    • a_{i,j} (1 \leq a_{i,j} \leq k) は、広場の (i, j) の位置に埋められているお宝の種類を表す。
    • n + 2 行目には、クエリの数を表す整数 q (1 \leq q \leq 100{,}000) が与えられる。
    • 続く q 行には、それぞれのクエリの情報が与えられる。
    • t_i (1 \leq t_i \leq 2) は、i 番目のクエリの種類を表す。
    • t_i = 1 のとき、i 番目のクエリが次郎君によってお宝が交換されるクエリであることを表し、(x_{1i}, y_{1i}) の位置にあるお宝と (x_{2i}, y_{2i}) の位置にあるお宝が交換されることを意味する。
    • t_i = 1 のとき、(x_{1i}, y_{1i}) と (x_{2i}, y_{2i}) は隣接していることが保証される。
    • t_i = 2 のとき、i 番目のクエリが現在のお宝の状況を調べるクエリであることを表し、(x_{1i}, y_{1i}) と (x_{2i}, y_{2i}) を対角線上の頂点とする広場に引かれた線に平行な長方形の中にあるお宝の状況を調べることを意味する。
    • t_i = 2 のとき、x_{1i} \leq x_{2i} かつ y_{1i} \leq y_{2i} であることが保証される。
    • 各クエリにおいて、1 \leq x_{1i}, x_{2i} \leq n かつ 1 \leq y_{1i}, y_{2i} \leq m であることが保証される。

    出力

    それぞれの t_i = 2 のクエリに対して、各クエリが表す長方形内に含まれる最も数の多いお宝の種類とその数を 1 行で出力せよ。

    最も数の多いお宝の種類が複数ある場合は、その中で最もお宝の種類を表す数が大きいものを答えよ。

    最後は改行し、余計な文字、空行を含まないこと。

    入力例1

    3 3 3
1 1 1
2 2 2
3 3 3
5
2 1 1 2 3
1 2 2 3 2
2 1 1 2 3
1 1 3 2 3
2 2 2 3 3

    出力例1

    2 3
1 3
3 2

    入力例2

    2 4 5
1 2 3 3
2 5 1 1
4
2 1 1 1 1
1 1 3 1 2
1 2 3 1 3
2 2 1 2 4

    出力例2

    1 1
2 2
    D - Rail Tour

    Time Limit: 2 sec / Memory Limit: 256 MB

    問題文

    無限に広がる xy 平面として表現される街があります。

    現在、amylase さんは点 (x_s, y_s) におり、点 (x_g, y_g) に移動したいと考えています。

    この街にはただ 1 つの鉄道である陸道電鉄が存在しており、この鉄道は、n 個の点 (x_1, y_1), (x_2, y_2) ... (x_n, y_n) を順番に通る折れ線として表されます。この鉄道は途中で交差することはありません。

    amylase さんは鉄道上の任意の地点で乗り降りすることができ、鉄道上では前後どちらの方向へも速度 v で移動することができます。それ以外の場所では、速度 1 で移動することができます。

    amylase さんが移動に必要とする最小の時間を求めてください。

    入力

    入力は以下の形式で与えられる。

    n v x_s y_s x_g y_g
x_1 y_1
...
x_n y_n
    • 1 行目には、鉄道を構成する点の数を表す整数 n (2 \leq n \leq 50)、鉄道上の移動速度を表す整数 v (2 \leq v \leq 1{,}000{,}000)、始点の座標を表す整数 x_s, y_s (-1{,}000{,}000 \leq x_s, y_s \leq 1{,}000{,}000) と、終点の座標を表す整数 x_g, y_g (-1{,}000{,}000 \leq x_g, y_g \leq 1{,}000{,}000) が与えられる。
    • 続く n 行には、鉄道を構成する各点の座標が与えられる。
    • x_i, y_i (-1{,}000{,}000 \leq x_i, y_i \leq 1{,}000{,}000) は、鉄道を構成する i 番目の点の座標が (x_i, y_i) であることを意味する。
    • 与えられるすべての座標は整数である。

    出力

    始点から終点まで移動するために必要な最小の時間を 1 行で出力せよ。

    絶対誤差と相対誤差のうち少なくとも片方が 10^{-6} 以下ならば正解とみなされる。

    最後は改行し、余計な文字、空行を含まないこと。

    入力例1

    2 2 -10 0 20 0
0 0
10 0

    出力例1

    25

    入力例2

    2 2 0 3 20 3
0 0
20 0

    出力例2

    15.1961524227

    入力例3

    2 2 0 3 10 3
0 0
10 0

    出力例3

    10

    入力例4

    4 3 -10 10 10 -20
0 10
0 0
-10 -10
10 -10

    出力例4

    33.5702260396

    入力例5

    4 3 -10 10 10 -20
0 10
0 0
-50 -10
10 -10

    出力例5

    34.9509379141