問題文

文字列 S と文字 c が与えられます。

文字列 S のすべての文字 x に対して、以下の操作を同時に一度だけ行ってできる文字列を出力してください。

• x が c と等しいとき、x を xx に置き換える。そうでないときは何もしない。

制約

• 1 \leq |S| \leq 100
• S は英小文字のみからなる文字列
• c は英小文字

入力例 1

quen
e

出力例 1

queen

操作によって e は ee に置き換えられるので、答えとなる文字列は queen です。

入力例 2

kenkoo
o

出力例 2

kenkoooo

操作は同時に行われることに注意してください。

入力例 3

abracadabra
a

出力例 3

aabraacaadaabraa

問題文

縦に N マス、横に N マスからなる、マス目状に区切られた盤面があります。上から i 番目 (1 \leq i \leq N)、左から j 番目 (1 \leq j \leq N) のマスを、マス (i, j) と呼ぶことにします。

盤面には N-1 個のクイーンが配置されており、i 番目のクイーンはマス (r_i, c_i) にあります。

ここで、盤面が次の条件を満たすとき、盤面は 良い状態 です。

• 盤面上のどの縦・横・斜め 45 度のマス目の列を見ても、クイーンが 2 つ以上存在しない。

また、与えられる盤面は 良い状態 であることが保証されます。

この盤面に対して、良い状態 を保ちつつクイーンを追加で 1 個配置することができるかを判定し、できる場合は配置する位置を出力してください。

制約

• 入力はすべて整数で与えられる
• 2 \leq N \leq 5{,}000
• 1 \leq r_i, c_i \leq N (1 \leq i \leq N - 1)
• 与えられる盤面は 良い状態 である

入力例 1

5
5 5
3 1
1 2
4 3

出力例 1

2 4

マス (2, 4) を通る、どの縦・横・斜め 45 度のマス目の列を見ても、クイーンは置かれていません。よって、(2, 4) にクイーンを置いた後も 良い状態 が保たれます。

入力例 2

5
2 5
3 1
1 2
4 4

出力例 2

-1

問題文

頂点に 1, 2, \ldots, N の番号がついた N 頂点の木と、頂点の番号 S, T が与えられます。i = 1, 2, \ldots, N-1 について、i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。

木のそれぞれの頂点 j について、以下の質問に答えてください。

• 頂点 S から頂点 j までの最短経路に含まれる頂点集合（頂点 S や頂点 j を含む）と、頂点 T から頂点 j までの最短経路に含まれる頂点集合（頂点 T や頂点 j を含む）の両方に属する頂点の数はいくつでしょうか？

制約

• 入力はすべて整数で与えられる
• 3 \leq N \leq 200{,}000
• 1 \leq S, T \leq N
• S \neq T
• 1 \leq u_i, v_i \leq N (1 \leq i \leq N-1)
• 与えられるグラフは木である

入力例

11 1 4
1 2
2 3
3 5
3 6
2 4
4 7
1 8
8 9
8 10
9 11

出力例

1
1
2
1
3
3
2
2
3
3
4

この入力例では、S = 1, T = 4 です。

• j = 1 のとき
  • S から j までの最短経路に含まれる頂点集合は \left\{ 1 \right\} です。
  • T から j までの最短経路に含まれる頂点集合は \left\{ 1, 2, 4 \right\} です。
  • 両方に属するのは、頂点 1 のみなので、答えは 1 です。
• j = 5 のとき
  • S から j までの最短経路に含まれる頂点集合は \left\{ 1, 2, 3, 5 \right\} です。
  • T から j までの最短経路に含まれる頂点集合は \left\{ 2, 3, 4, 5 \right\} です。
  • 両方に属するのは、頂点 2, 3, 5 なので、答えは 3 です。

問題文

縦に R マス、横に C マスからなる、マス目状に区切られた盤面があります。上から i 番目 (1 \leq i \leq R)、左から j 番目 (1 \leq j \leq C) のマスを、マス (i, j) と呼ぶことにします。

現在マス (r_s, c_s) に 1 個のクイーンが配置されています。 以下の行動を三回繰り返した時、 クイーンが (r_t, c_t) にある様な動き方は何通りありますか。

• クイーンを盤面上の現在配置されているマスを含む縦・横・斜め 45 度のマス目の列上の他のマスに移動する（現在配置されているマスに留まることはできない）

制約

• 入力はすべて整数で与えられる
• 2 \leq R \leq 100{,}000
• 2 \leq C \leq 100{,}000
• 1 \leq r_s, r_t \leq R
• 1 \leq c_s, c_t \leq C

入力例 1

3 3 1 1 3 3

出力例 1

29

例えば、マス (1,1) \rightarrow マス (1,2) \rightarrow マス (2,2) \rightarrow マス (3,3) の様に動かす事でクイーンをマス (1,1) から マス (3,3) に移動させる事が出来ます。

入力例 2

3 3 2 2 2 2

出力例 2

40

入力例 3

100000 100000 1 1 100000 100000

出力例 3

10001499973

答えは 32-bit 整数型に収まらない場合があります。

問題文

長さ N の数列 A = \left( a_1, a_2, \ldots, a_N \right) が与えられます。

この数列を、いくつかの連続する空でない部分列 B_1, B_2, \ldots, B_K に分割することを考えます。たとえば、A = (5, -3, 6, 2, 4) のとき、A の分割の例は以下のとおりです。

• B_1 = (5), B_2 = (-3, 6, 2), B_3 = (4)
• B_1 = (5, -3), B_2 = (6, 2, 4)
• B_1 = (5, -3, 6, 2, 4)

部分列 B_i の スコア S \left( B_i \right) を、B_i に含まれる項の最大値と最小値の差 \max B_i - \min B_i と定義します。

A を最適に分割したときの、部分列のスコアの和 \sum_i S \left( B_i \right) の最大値を求めてください。

制約

• 入力はすべて整数で与えられる
• 1 \leq N \leq 200{,}000
• |a_i| \leq 10^{9} (1 \leq i \leq N)

入力例 1

9
1 2 2 4 5 2 3 4 1

出力例 1

9

B_1 = (1, 2, 2, 4), B_2 = (5, 2, 3), B_3 = (4, 1) が最適な分割のうちのひとつです。

• S(B_1) = 4 - 1 = 3
• S(B_2) = 5 - 2 = 3
• S(B_3) = 4 - 1 = 3

であるので、その合計である 9 が答えです。

入力例 2

12
3 -1 4 1 5 -9 2 6 5 -3 5 9

出力例 2

37

問題文

以下の条件を満たす様に二次元平面上に N 個の点 P_1 , P_2 , \ldots , P_N を置きます。この条件の元、N 角形 P_1 P_2 \dots P_N の面積の最大値を求めてください。ただし、原点と点 P_i を結ぶ直線の x 軸正の向きとのなす角を \theta_i\ \mathrm{rad} とします。

• i 番目の点 P_i は原点を中心とする半径 R_i の円周上に存在する
  • 与えられる R は、\displaystyle R_1 = R_N かつ \displaystyle R_1, R_N \leq R_i (1 \leq i \leq N) を満たすことが保証されます
• \displaystyle \frac{\pi}{2N} \leq \theta_{i+1} -\theta_{i} (1 \leq i \leq N-1) (14:07 修正)
• \displaystyle \theta_1 = 0 , \displaystyle \theta_N = \frac{2\pi}{3}

制約

• 入力はすべて整数で与えられる
• 3 \leq N \leq 100{,}000
• 0< R_i \leq 1{,}000 (1 \leq i \leq N)
• R_1=R_N かつ R_1, R_N \leq R_i (1 \leq i \leq N)

入力例 1

3
1 1 1

出力例 1

0.433012701892219

3 個の点 P_1 , P_2 , P_3 を ( (1,0) , (\frac{1}{2},\frac{\sqrt{3}}{2}) , (-\frac{1}{2},\frac{\sqrt{3}}{2}) ) と設定すると三角形 P_1P_2P_3 の面積は \frac{\sqrt{3}}{4} となり、これは制約内における最大値となります。

入力例 2

7
1 2 1 3 1 2 1

出力例 2

2.147031208123904

7 個の点　P_1 , P_2 , \ldots , P_7 を適切に設定すると七角形 P_1P_2\dots P_7 の面積は約 2.147031208123904 となり、これは制約内における最大値となります。