問題文

すぬけ君は 2018 年のカレンダーを持っており、そこには全部で N 個の祝日が存在します。新年から数えて i 番目の祝日の曜日は、S_i と書かれていました。 S_i は Mon, Tue, Wed, Thu, Fri, Sat, Sun のうちいずれかであり、それぞれ月曜日、火曜日、水曜日、……、日曜日を表しています。

日本と違いすぬけ君の住む国では、2019 年も全く同じ N 個の日付に祝日が存在しています。 すぬけ君は 2019 年のカレンダーではこれらの日付が何曜日になるか気になっています。N 個それぞれの祝日について、2019 年のカレンダーに書かれているべき 曜日を表す長さ 3 の文字列を答えてください。

制約

• 1 ≤ N ≤ 50
• S_i は Mon, Tue, Wed, Thu, Fri, Sat, Sun のうちいずれか

入力例 1

8
Fri
Tue
Sun
Sun
Mon
Sun
Wed
Thu

出力例 1

Sat
Wed
Mon
Mon
Tue
Mon
Thu
Fri

問題文

xy 平面上の点 (0,0) にロボットが 1 個置かれています。 あなたは、このロボットに、L, R, U, D からなる文字列を 1 つ命令として与えることができます。 ロボットは文字列を与えられると、先頭の文字から順に、 L なら x 軸方向に -1、R なら x 軸方向に +1、U なら y 軸方向に +1、D なら y 軸方向に -1 動くという動作を最後の文字まで行います。

あなたは、W,X,Y,Z からなる文字列 S を持っています。あなたは、これら 4 種類の文字をそれぞれ L ,R ,U ,Dのいずれかに置き換えた文字列を、ロボットに与えようとしています。 ただし、S において異なる文字を命令において同じ文字に割り当てることはできません。

文字列 S と整数 g_x, g_y が与えられます。 適切な文字の割り当てによってロボットが動き始めてから移動を終えるまで (開始、終了点を含みます) のどこかで座標 (g_x,g_y) を通るようにできるなら Yes を、できないなら No を出力してください。

制約

• 1 ≤ |S| ≤ 10^5
• S は W, X, Y, Z からなる文字列
• |g_x|, |g_y| ≤ 10^5
• g_x, g_y は整数

入力例 1

WWYWYWWW
3 0

出力例 1

Yes

例えば、W を R に、X を U に、Y を L に、Z を D に割り当てることによって、(3,0) を通ることができます。

入力例 2

YYYYW
-1 -3

出力例 2

No

入力例 3

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
0 50

出力例 3

Yes

問題文

N 冊の本が 1 列に積まれています。下から i 段目 (1 ≤ i ≤ N) の本の厚さは h_i です。

あなたは、積まれた本を 1 冊ずつ取り出そうとしています。 ある本の最高点の高さが H 以下であるならば、積まれた中でどこにあってもその本を取り出すことができます。 1 冊本を取り出すと、それより上にあった本が平行移動して降りてきます。

全ての本を取り出すとき、本を取り出す順番として可能なものの総数を求めてください。

制約

• 1 ≤ N ≤ 10
• 1 ≤ H ≤ 100
• 1 ≤ h_i ≤ H
• 入力で与えられる値は全て整数

入力例 1

4 3
2
1
2
3

出力例 1

3

以下の 3 通りがあります。

• 最初の状態で下から 1 段目、下から 2 段目、下から 3 段目、下から 4 段目にあるものを順に取り出す。
• 最初の状態で下から 1 段目、下から 3 段目、下から 2 段目、下から 4 段目にあるものを順に取り出す。
• 最初の状態で下から 2 段目、下から 1 段目、下から 3 段目、下から 4 段目にあるものを順に取り出す。

入力例 2

10 100
19
2
1
2
18
4
9
4
24
19

出力例 2

3225600

問題文

数直線上に N 個の点があり、i 番目の点の座標は x_i です。また、N 個の整数 w_i が与えられます。

次の条件を満たす点 p の座標を求めてください。条件を満たす点が複数ある場合は、最も座標が小さいものを求めてください。

条件: 「1≤i≤N を満たす整数 i に対する (p から点 i までの距離) × w_i の最大値が最小になる。」

制約

• 1 ≤ N ≤ 10^5
• |x_i| ≤ 10^7
• x_i < x_{i+1} (1 ≤ i ≤ N-1)
• 1 ≤ w_i ≤ 10^7
• 入力で与えられる値は全て整数

入力例 1

6
-9 1
-6 1
-4 1
1 1
9 1
10 1

出力例 1

0.500000000000

点 p の座標が 0.5 のとき、各点 i (1≤i≤N) に対する (p から点 i までの距離) × w_i の値はそれぞれ 9.5, 6.5, 4.5, 0.5, 8.5, 9.5 となり、 これらの最大値は 9.5 です。 この値をこれより小さくすることはできないので、答えは 0.5 です。

入力例 2

20
-8965725 4915988
-8830129 1578539
-8356752 3503810
-7479989 5100308
-6995994 3722838
-6861764 3493854
-6486775 1657800
-4577872 7994227
-3685008 7178154
-3169623 9319261
-2694681 7493276
-1967934 3837689
-1634671 544297
-1232484 6010778
2733239 4318924
4797695 2789412
5713704 4416095
6609027 2426329
6997023 2155233
7812383 9912027

出力例 2

2249873.278320866637

問題文

N 個の椅子が円環上に並んでいます。椅子には 1 〜 N の番号が付けられており、2 ≤ i ≤ N-1 である i それぞれについて、i 番目の椅子は i-1 番目の椅子および i+1 番目の椅子に隣接しています。1 番目の椅子は 2 番目の椅子および N 番目の椅子に隣接しています。 N 番目の椅子は 1 番目の椅子および N-1 番目の椅子に隣接しています。

狼 A 匹と狐 N-A 匹が N 個の椅子に 1 匹ずつ座ることにしました。すでにこのうちの何匹かは椅子に座っています。具体的には、W, F, ? からなる長さ N の文字列 S が与えられます。 S の i 文字目が W のとき、i 番目の椅子にはすでに狼が座っています。 S の i 文字目が F のとき、i 番目の椅子にはすでに狐が座っています。 S の i 文字目が ? のとき、i 番目の椅子にはまだ誰も座っていません。

まだ椅子に座っていない狼が x 匹、狐が y 匹いるとき、狼同士、狐同士を区別しないとすると、残り狼と狐の座り方は全部で _{x+y}C_x 通りあります。 これら全てに対し、隣り合う 2 つの椅子に異なる種類の動物が座っている場所の個数を求め合計すると、いくつになるでしょうか。10^9+7 で割った余りを求めてください。

制約

• 3 ≤ |S| ≤ 10^6
• N = |S|
• 0 ≤ A ≤ N
• S は W, F, ? からなる文字列
• S に含まれる W の個数は A 以下
• S に含まれる F の個数は N-A 以下

入力例 1

??FFW
2

出力例 1

6

残りの狼と狐の座り方は 2 通りあり、 WFFFW と FWFFW が可能な座り方です。

• WFFFW の場合、2 箇所において異なる種類の動物が座っています。
• FWFFW の場合、4 箇所において異なる種類の動物が座っています。

よって、求める答えは 2+4=6 です。

入力例 2

FW???WF??????W??????
10

出力例 2

73788

問題文

N+1 個のバス停があり、0 から N の番号が付けられています。 バス停 i (0 ≤ i ≤ N-1)からはバス停 i+1 行きのバスが出ており、移動するのに t_{i+1} 分かかります。

また、正整数 k が定まっています。どのバス停 i (0 ≤ i ≤ N-1)からも、バス停 i+1 行きのバスは (時刻 0 分 〜 時刻 k-1 分のうち整数分のどこかで 1 回)、(時刻 k 分 〜 時刻 2k-1 分のうち整数分のどこかで 1 回)、(時刻 2k 分 〜 時刻 3k-1 分のうち整数分のどこかで 1 回)、... に発車します。 それぞれの時刻 mk 分〜 時刻 (m+1)k-1 分 の中では、等確率でどの整数分に発車するかが選ばれます。これは m ごと、バス停ごとに独立です。

すぬけ君は時刻 0 分にバス停 0 を出発し、N 本のバスに乗ってバス停 N まで移動しようとしています。 ただし、すぬけ君はあるバス停に到着すると同時に次のバスに乗ることができます。

バス停 N に到着するのに何分かかるか、期待値を求めてください。

制約

• 1 ≤ N ≤ 10^5
• 1 ≤ k ≤ 300
• 1 ≤ t_i ≤ 10^9
• 入力で与えられる値は全て整数

入力例 1

2 2
2
1

出力例 1

4.125000000000

• 時刻 0 分にバス停 0 からバスが発車し、時刻 2 分にバス停 1 に到着し、時刻 2 分にバス停 1 からバスが発車し、時刻 3 分にバス停 2 に到着する。これは確率 1/4 で起こります。
• 時刻 0 分にバス停 0 からバスが発車し、時刻 2 分にバス停 1 に到着し、時刻 3 分にバス停 1 からバスが発車し、時刻 4 分にバス停 2 に到着する。これは確率 1/4 で起こります。
• 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 3 分にバス停 1 からバスが発車し、時刻 4 分にバス停 2 に到着する。これは確率 1/4 で起こります。
• 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 4 分にバス停 1 からバスが発車し、時刻 5 分にバス停 2 に到着する。これは確率 1/8 で起こります。
• 時刻 1 分にバス停 0 からバスが発車し、時刻 3 分にバス停 1 に到着し、時刻 5 分にバス停 1 からバスが発車し、時刻 6 分にバス停 2 に到着する。これは確率 1/8 で起こります。

よって、求める期待値は、3 \times (1/4) + 4 \times (1/4) + 4 \times (1/4) + 5 \times (1/8) + 6 \times (1/8) = 33/8 です。

入力例 2

6 4
4
6
4
2
1
7

出力例 2

34.524398803711

問題文

2 次元平面上に N 個のバス停があり、i 番目のバス停の座標は (x_i, y_i) です。ただし、x_i, y_i はいずれも整数です。

すぬけ君は、N 個のうち 3 個以上のバス停を選び、凸包 (選ばれた点の集合を全て包含する中で面積が最小の凸多角形) の面積を計算する、ということを全ての選び方について行ったときの総和を知りたいです。 あなたはすぬけ君の代わりにこの値を求めることになりました。

ただし、この面積の総和を a/2 とすると a は必ず整数になることが証明できるので、a を 10^9+7 で割った余りを答えてください。

制約

• 3 ≤ N ≤ 2000
• |x_i|, |y_i| ≤ 10000
• (x_i, y_i) ≠ (x_j, y_j) (1 ≤ i < j ≤ N)
• 与えられる点のうちいずれの 3 点も同一直線上にない
• 入力で与えられる値は全て整数

入力例 1

4
0 0
1 0
-1 1
-1 -1

出力例 1

12

• 1 番目の点、2 番目の点、3 番目の点を選んだ時、凸包の面積は 1/2 です。
• 1 番目の点、2 番目の点、4 番目の点を選んだ時、凸包の面積は 1/2 です。
• 1 番目の点、3 番目の点、4 番目の点を選んだ時、凸包の面積は 1 です。
• 2 番目の点、3 番目の点、4 番目の点を選んだ時、凸包の面積は 2 です。
• 1 番目の点、2 番目の点、3 番目の点、4 番目の点を選んだ時、凸包の面積は 2 です。

よって、面積の総和は 1/2+1/2+1+2+2=6 です。面積の総和の 2 倍を 10^9+7 で割った余りである 12 を出力します。

入力例 2

10
-3 1
2 3
-2 0
-3 2
-5 -5
1 -5
2 4
5 4
5 -3
-2 5

出力例 2

75282

問題文

世界最悪のバス停を投票で決めるトーナメントが開催されています。バス停は 2^N 個あり、バス停 i と バス停 j (i < j) が対戦するとき、 後述する例外を除いて必ずバス停 i がより多くの票を獲得し、次のラウンドに進みます。

トーナメントは以下のように進行します。

• まず、長さ 2^N の順列 (p_1, ..., p_{2^N}) を選ぶ。
• バス停 p_1 とバス停 p_2、バス停 p_3 とバス停 p_4、...、バス停 p_{2^N-1} とバス停 p_{2^N} が対戦する。
• バス停 p_1, p_2 の勝者とバス停 p_3, p_4 の勝者、バス停 p_5, p_6 の勝者とバス停 p_7, p_8 の勝者、...、バス停 p_{2^N-3}, p_{2^N-2} の勝者とバス停 p_{2^N-1}, p_{2^N} の勝者が対戦する。

:

• バス停 p_1 〜 p_{2^{N-1}} の勝者とバス停 p_{2^{N-1}+1} 〜 p_{2^N} の勝者が対戦する。

すぬけ君は、バス停 M を応援しています。すぬけ君は、バス停 M と他のバス停との対戦のうち、最大 K 回においてバス停 M を宣伝することができます。 宣伝を行うと、その対戦においては必ずバス停 M が勝つことができます。

2^N! 個の順列 (p_1, ..., p_{2^N}) で表される初期状態のうち、 すぬけ君が適切に宣伝を行うことでバス停 M がトーナメントで最終的に残ることができるものは何通りあるかを、10^9+7 で割った余りを求めてください。

制約

• 1 ≤ N ≤ 20
• 1 ≤ M ≤ 2^N
• 0 ≤ K ≤ 20

入力例 1

2 3 1

出力例 1

8

条件を満たす初期状態は、 (1,2,3,4), (1,2,4,3),(2,1,3,4),(2,1,4,3),(3, 4, 1, 2), (3, 4, 2, 1), (4, 3, 1, 2), (4, 3, 2, 1) の 8 個です。

入力例 2

20 49300 4

出力例 2

77113063

問題文

近年狼の国では、1 円玉が廃止され、最小額の硬貨が 5 円玉となり、全ての貨幣の額面が 5 の倍数になりました。 しかし、商品の値段は未だに 5 の倍数でないものが存在しています。

狼の国に遊びに来たすぬけ君は、ある店で N 個の商品全てを買うことにしました。i 番目の商品の値段は p_i 円です。

この国には 1 円玉がないので、幾つかの商品をレジに持っていくと、持って行った商品の値段の合計を 5 で割ったあまりを v としたとき、v が 1 または 2 ならばそれぞれ 1 円、2 円引きになり、3 または 4 ならばそれぞれ 2 円、1 円が合計金額に上乗せされます。v が 0 ならば合計金額はそのままです。

ところがすぬけ君は、N 個の商品を何回かに分けてレジに持っていくと、持っていく方法によって支払う金額の総計が変わる可能性があることに気がつきました。 すぬけ君は可能な限り節約したいので、適切な方法でレジに持っていくことで、N 個全ての商品を買うのに払う金額の総計を最小化したいです。 ただし、レジに何度も商品を持っていくのはあまりに疲れる行為なので、金額の総計が最小な中でレジに持っていく回数を最小化したいです。

すぬけ君が払う金額の総計の最小値と、そのうちレジに持っていく回数の最小値を求めてください。

制約

• 1 ≤ N ≤ 10^6
• 1 ≤ p_i ≤ 1000
• 入力で与えられる値は全て整数

入力例 1

6
1
1
2
1
2
1

出力例 1

0 4

• 1 番目の商品と 2 番目の商品をレジに持っていくと、合計金額から 2 円引きとなり、0 円になります。
• 4 番目の商品と 6 番目の商品をレジに持っていくと、合計金額から 2 円引きとなり、0 円になります。
• 3 番目の商品をレジに持っていくと、合計金額から 2 円引きとなり、0 円になります。
• 5 番目の商品をレジに持っていくと、合計金額から 2 円引きとなり、0 円になります。

以上により、総計 0 円をレジに 4 回持っていくことで達成できます。

入力例 2

5
968
127
125
966
861

出力例 2

3045 1

全ての商品を一度にレジに持っていくのが最適です。

問題文

狼と狐が健康診断を行うことになりました。健康診断は N 日間にわたって行われ、それぞれの狼と狐は、N 日間のうちある 1 日に健康診断に参加することになっています。 i 日目に健康診断に参加したい狼は w_i 匹、i 日目に健康診断に参加したい狐は f_i 匹います。

ただし、N 日間のそれぞれの日において、狼または狐のいずれか一方しか診断できないことになっています。 希望が合わない場合は他の日に参加することになるが、i 日目に健康診断に参加したい狼や狐が j 日目に健康診断を行う場合、不満度は |i-j| です。 健康診断を行える日が存在しないときは、不満度は 10^{100} です。それぞれの狼と狐は、参加できる中で不満度が最小になるような日に健康診断に参加します。

N 日間のそれぞれの日において、狼と狐いずれを診断するかを最適に決めた時の、全ての狼と狐の不満度の合計の最小値を求めてください。

制約

• 2 ≤ N ≤ 3000
• 0 ≤ w_i, f_i ≤ 10^9

入力例 1

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

出力例 1

15

3,5,6 日目に狼を診断し、1,2,4 日目に狐を診断するのが最適です。

入力例 2

10
26 37
1 49
1 74
2 99
2 100
2 75
3 62
3 62
2 37
2 37

出力例 2

108