AtCoder Daily Training ALL 2024/05/21 19:30start

A - Christmas Present

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

野球少年の高橋君は今年とても良い子にしていたので、サンタさんはバットかグローブのうち値段が高い方を高橋君にプレゼントすることにしました。

バットの値段が B 円、グローブの値段が G 円 (B\neq G) のとき、サンタさんが高橋君にプレゼントするのはどちらですか？

制約

B,G は 1 以上 1000 以下の相異なる整数

入力

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

B G

出力

サンタさんが高橋君にプレゼントするのがバットであるとき Bat を、グローブであるとき Glove を出力せよ。

入力例 1

300 100

出力例 1

Bat

バットの方がグローブより値段が高いので、サンタさんは高橋君にバットをプレゼントします。

入力例 2

334 343

出力例 2

Glove

グローブの方がバットより値段が高いので、サンタさんは高橋君にグローブをプレゼントします。

Score : 100 points

Problem Statement

Takahashi, a young baseball enthusiast, has been a very good boy this year, so Santa has decided to give him a bat or a glove, whichever is more expensive.

If a bat costs B yen and a glove costs G yen (B\neq G), which one will Santa give to Takahashi?

Constraints

B and G are different integers between 1 and 1000, inclusive.

Input

The input is given from Standard Input in the following format:

B G

Output

If Santa gives Takahashi a bat, print Bat; if Santa gives him a glove, print Glove.

Sample Input 1

300 100

Sample Output 1

Bat

The bat is more expensive than the glove, so Santa will give Takahashi the bat.

Sample Input 2

334 343

Sample Output 2

Glove

The glove is more expensive than the bat, so Santa will give Takahashi the glove.

B - Capitalized?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英大文字・英小文字からなる空でない文字列 S が与えられます。以下の条件が満たされているか判定してください。

S の先頭の文字は大文字であり、それ以外の文字はすべて小文字である。

制約

1 \leq |S| \leq 100（|S| は文字列 S の長さ）
S の各文字は英大文字または英小文字である。

入力

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

出力

条件が満たされていれば Yes、そうでなければ No を出力せよ。

入力例 1

Capitalized

出力例 1

Yes

Capitalized の先頭の文字 C は大文字であり、それ以外の文字 apitalized はすべて小文字であるため、Yes を出力します。

入力例 2

AtCoder

出力例 2

No

AtCoder は先頭以外にも大文字 C を含むため、No を出力します。

入力例 3

yes

出力例 3

No

yes の先頭の文字 y は大文字でないため、No を出力します。

入力例 4

出力例 4

Yes

Score: 100 points

Problem Statement

You are given a non-empty string S consisting of uppercase and lowercase English letters. Determine whether the following condition is satisfied:

The first character of S is uppercase, and all other characters are lowercase.

Constraints

1 \leq |S| \leq 100 (|S| is the length of the string S.)
Each character of S is an uppercase or lowercase English letter.

Input

The input is given from Standard Input in the following format:

Output

If the condition is satisfied, print Yes; otherwise, print No.

Sample Input 1

Capitalized

Sample Output 1

Yes

The first character C of Capitalized is uppercase, and all other characters apitalized are lowercase, so you should print Yes.

Sample Input 2

AtCoder

Sample Output 2

No

AtCoder contains an uppercase letter C that is not at the beginning, so you should print No.

Sample Input 3

yes

Sample Output 3

No

The first character y of yes is not uppercase, so you should print No.

Sample Input 4

Sample Output 4

Yes

C - Same Map in the RPG World

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は RPG を作っています。高橋君は 2 枚の RPG 世界のマップが一致しているかを判定するプログラムを書くことにしました。

縦 H マス横 W マスの 2 つのグリッド A, B があります。グリッドの各マスには # と . のいずれかの文字が書かれています。
A と B の上から i 行目、左から j 列目に書かれている文字をそれぞれ A_{i, j}, B_{i, j} と呼びます。

次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。

j=1, 2, \dots, W について次の操作を同時に行う。
- A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} を A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j} に同時に置き換える。
i = 1, 2, \dots, H について次の操作を同時に行う。
- A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} を A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1} に同時に置き換える。

次の条件を満たす非負整数の組 (s, t) は存在しますか？存在する場合は Yes を、存在しない場合は No を出力してください。

縦方向のシフトを s 回行い、次に横方向のシフトを t 回行った時、操作後の A が B と一致する。

ここで、A と B が一致するとは、1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) すべてに対して A_{i, j} = B_{i, j} が成り立つことを言います。

制約

2 \leq H, W \leq 30
A_{i,j},B_{i,j} は # または .
H, W は整数

入力

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

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

出力

条件を満たす整数の組 (s, t) が存在する場合は Yes を、存在しない場合は No を出力せよ。

入力例 1

4 3
..#
...
.#.
...
#..
...
.#.
...

出力例 1

Yes

(s, t) = (2, 1) とすると A と B を一致させることができます。
(s, t) = (2, 1) の時の操作の手順を説明します。はじめ、A は次の通りです。

..#
...
.#.
...

まず、縦方向のシフトを行います。A は次のようになります。

...
.#.
...
..#

次に、再び縦方向のシフトを行います。A は次のようになります。

.#.
...
..#
...

最後に、横方向のシフトを行います。A は次のようになり、これは B と一致しています。

#..
...
.#.
...

入力例 2

3 2
##
##
#.
..
#.
#.

出力例 2

No

どのように (s, t) を選んでも A と B を一致させることはできません。

入力例 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

出力例 3

Yes

入力例 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

出力例 4

Yes

Score : 200 points

Problem Statement

Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.

We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.

The following two operations are called a vertical shift and horizontal shift.

For each j=1, 2, \dots, W, simultaneously do the following:
- simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
For each i = 1, 2, \dots, H, simultaneously do the following:
- simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.

After applying a vertical shift s times and a horizontal shift t times, A is equal to B.

Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.

Constraints

2 \leq H, W \leq 30
A_{i,j} is # or ., and so is B_{i,j}.
H and W are integers.

Input

The input is given from Standard Input in the following format:

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

Output

Print Yes if there is a conforming integer pair (s, t); print No otherwise.

Sample Input 1

4 3
..#
...
.#.
...
#..
...
.#.
...

Sample Output 1

Yes

By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.

..#
...
.#.
...

We first apply a vertical shift to make A as follows.

...
.#.
...
..#

Then we apply another vertical shift to make A as follows.

.#.
...
..#
...

Finally, we apply a horizontal shift to make A as follows, which equals B.

#..
...
.#.
...

Sample Input 2

3 2
##
##
#.
..
#.
#.

Sample Output 2

No

No choice of (s, t) makes A equal B.

Sample Input 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

Sample Output 3

Yes

Sample Input 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Sample Output 4

Yes

D - Adjacency List

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1, \dots, N と番号付けられた N 個の都市と、都市間を結ぶ M 本の道路があります。
i \, (1 \leq i \leq M) 番目の道路は都市 A_i と都市 B_i を結んでいます。

以下の指示に従い、N 行にわたって出力してください。

都市 i \, (1 \leq i \leq N) と道路で直接結ばれた都市が d_i 個あるとし、それらを昇順に都市 a_{i, 1}, \dots, a_{i, d_i} とおく。
i \, (1 \leq i \leq N) 行目には、d_i + 1 個の整数 d_i, a_{i, 1}, \dots, a_{i, d_i} を、この順番で空白区切りで出力せよ。

制約

2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
(i \neq j) ならば (A_i, B_i) \neq (A_j, B_j)
入力される値は全て整数

入力

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

N M
A_1 B_1
\vdots
A_M B_M

出力

問題文の指示に従い、N 行にわたって出力せよ。

入力例 1

出力例 1

都市 1 と道路で直接結ばれているのは都市 2, 3, 6 です。よって、d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6 であるので、1 行目には 3, 2, 3, 6 をこの順番で空白区切りで出力します。

a_{i, 1}, \dots, a_{i, d_i} は昇順に並んでいなければならないことに注意してください。例えば、1 行目に 3, 3, 2, 6 をこの順番で出力した場合、不正解となります。

入力例 2

出力例 2

Score : 200 points

Problem Statement

There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.

Print N lines as follows.

Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.

Constraints

2 \leq N \leq 10^5
1 \leq M \leq 10^5
1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
(A_i, B_i) \neq (A_j, B_j) if (i \neq j).
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print N lines as specified in the Problem Statement.

Sample Input 1

Sample Output 1

The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.

Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.

Sample Input 2

Sample Output 2

E - 1 2 1 3 1 2 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

列 S_n を次のように定義します。

S_1 は 1 つの 1 からなる長さ 1 の列である。
S_n (n は 2 以上の整数) は S_{n-1}, n, S_{n-1} をこの順につなげた列である。

たとえば S_2,S_3 は次のような列です。

S_2 は S_1, 2, S_1 をこの順につなげた列なので 1,2,1 である。
S_3 は S_2, 3, S_2 をこの順につなげた列なので 1,2,1,3,1,2,1 である。

N が与えられるので、列 S_N をすべて出力してください。

制約

N は整数
1 \leq N \leq 16

入力

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

出力

S_N を空白区切りで出力せよ。

入力例 1

出力例 1

1 2 1

問題文の説明にある通り、S_2 は 1,2,1 となります。

入力例 2

出力例 2

入力例 3

出力例 3

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

S_4 は S_3,4,S_3 をこの順につなげた列です。

Score : 300 points

Problem Statement

We define sequences S_n as follows.

S_1 is a sequence of length 1 containing a single 1.
S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

N is an integer.
1 \leq N \leq 16

Input

Input is given from Standard Input in the following format:

Output

Print S_N, with spaces in between.

Sample Input 1

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

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

S_4 is a concatenation of S_3, 4, and S_3, in this order.

F - Collision 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

xy 座標平面上に N 人の人がいます。人 i は (X_i, Y_i) にいます。すべての人は異なる地点にいます。

L, R からなる長さ N の文字列 S があります。
人 i は S_i = R ならば右向きに、S_i = L ならば左向きに、一斉に同じ速度で歩き始めます。ここで、右は x 軸の正の向き、左は x 軸の負の向きです。

たとえば (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL の場合は次の図のように動きます。

反対の向きに歩いている人同士が同じ地点に来ることを「衝突」と呼びます。すべての人が歩き続けたとき、衝突は発生しますか？

制約

2 \leq N \leq 2 \times 10^5
0 \leq X_i \leq 10^9
0 \leq Y_i \leq 10^9
i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j) である。
X_i, Y_i はすべて整数である。
S は L および R からなる長さ N の文字列である。

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

出力

衝突が発生するならば Yes を、発生しないならば No を出力せよ。

入力例 1

出力例 1

Yes

この入力は問題文にある例と同じケースです。
すべての人が歩き続けると人 2 と人 3 が衝突します。よって Yes を出力します。

入力例 2

出力例 2

No

人 1 と人 2 は同じ向きに歩いているので衝突することはありません。

入力例 3

出力例 3

Yes

Score : 300 points

Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq X_i \leq 10^9
0 \leq Y_i \leq 10^9
(X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
All X_i and Y_i are integers.
S is a string of length N consisting of L and R.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

Output

If there will be a collision, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

Sample Output 3

Yes

G - President

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君と青木君が選挙で戦っています。
選挙区は N 個あります。i 番目の選挙区には X_i + Y_i 人の有権者がいて、そのうち X_i 人が高橋派、Y_i 人が青木派です。(X_i + Y_i はすべて奇数です)
それぞれの区では、多数派がその区の Z_i 議席を全て獲得します。そして、N 個の選挙区全体として過半数の議席を獲得した方が選挙に勝利します。(\displaystyle \sum_{i=1}^N Z_i は奇数です)
高橋君が選挙で勝利するには最低で何人を青木派から高橋派に鞍替えさせる必要がありますか？

制約

1 \leq N \leq 100
0 \leq X_i, Y_i \leq 10^9
X_i + Y_i は奇数
1 \leq Z_i
\displaystyle \sum_{i=1}^N Z_i \leq 10^5
\displaystyle \sum_{i=1}^N Z_i は奇数

入力

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

N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_N Y_N Z_N

出力

答えを出力せよ。

入力例 1

1
3 8 1

出力例 1

選挙区が 1 個しかないので、1 番目の選挙区で議席を獲得した人が選挙に勝利します。
1 番目の選挙区の青木派 3 人を高橋派に鞍替えさせると、1 番目の選挙区にいる有権者のうち高橋派は 6 人、青木派は 5 人になり、高橋君は議席を獲得できます。

入力例 2

2
3 6 2
1 8 5

出力例 2

1 番目の選挙区の議席数よりも 2 番目の選挙区の議席数の方が多いため、高橋君が選挙に勝つには 2 番目の選挙区で高橋派を多数派にする必要があります。
2 番目の選挙区の青木派の 4 人を鞍替えさせると高橋君は 5 議席を獲得できます。このとき青木君の獲得する議席は 2 議席なので、高橋君は選挙に勝利できます。

入力例 3

出力例 3

青木派から高橋派に鞍替えする人が 0 人でも高橋君が選挙で勝つ場合は 0 人が答えになります。

入力例 4

10
1878 2089 16
1982 1769 13
2148 1601 14
2189 2362 15
2268 2279 16
2394 2841 18
2926 2971 20
3091 2146 20
3878 4685 38
4504 4617 29

出力例 4

Score : 400 points

Problem Statement

Takahashi and Aoki are competing in an election.
There are N electoral districts. The i-th district has X_i + Y_i voters, of which X_i are for Takahashi and Y_i are for Aoki. (X_i + Y_i is always an odd number.)
In each district, the majority party wins all Z_i seats in that district. Then, whoever wins the majority of seats in the N districts as a whole wins the election. (\displaystyle \sum_{i=1}^N Z_i is odd.)
At least how many voters must switch from Aoki to Takahashi for Takahashi to win the election?

Constraints

1 \leq N \leq 100
0 \leq X_i, Y_i \leq 10^9
X_i + Y_i is odd.
1 \leq Z_i
\displaystyle \sum_{i=1}^N Z_i \leq 10^5
\displaystyle \sum_{i=1}^N Z_i is odd.

Input

The input is given from Standard Input in the following format:

N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_N Y_N Z_N

Output

Print the answer.

Sample Input 1

1
3 8 1

Sample Output 1

Since there is only one district, whoever wins the seat in that district wins the election.
If three voters for Aoki in the district switch to Takahashi, there will be six voters for Takahashi and five for Aoki, and Takahashi will win the seat.

Sample Input 2

2
3 6 2
1 8 5

Sample Output 2

Since there are more seats in the second district than in the first district, Takahashi must win a majority in the second district to win the election.
If four voters for Aoki in the second district switch sides, Takahashi will win five seats. In this case, Aoki will win two seats, so Takahashi will win the election.

Sample Input 3

Sample Output 3

If Takahashi will win the election even if zero voters switch sides, the answer is 0.

Sample Input 4

10
1878 2089 16
1982 1769 13
2148 1601 14
2189 2362 15
2268 2279 16
2394 2841 18
2926 2971 20
3091 2146 20
3878 4685 38
4504 4617 29

Sample Output 4

H - Roulettes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

N 台のルーレットがあります。 i 番目 (1\leq i\leq N) のルーレットには P _ i 個の整数 S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} が書かれており、C _ i 円支払うことで 1 回プレイできます。 i 番目のルーレットを 1 回プレイすると、1 以上 P _ i 以下の整数 j が一様ランダムに選ばれ、S _ {i,j} ポイントを得ることができます。

ルーレットで得られるポイントは、過去の結果と独立に決まります。

高橋くんは、ポイントを M ポイント以上獲得したいです。高橋くんは、M ポイント以上獲得するまでに支払う金額をなるべく小さくするように行動します。ただし、高橋くんはルーレットをプレイするたびこれまでのルーレットの結果を見て次にプレイするルーレットを選ぶことができます。

高橋くんがポイントを M ポイント以上獲得するまでに支払う金額の期待値を求めてください。

より厳密な定義

より厳密には、次のようになります。高橋くんがルーレットを選ぶ戦略を決めるごとに、その戦略で M ポイント以上獲得するまでに支払う金額の期待値 E が次のように定義されます。

自然数 X に対して、その戦略に従って高橋くんが M ポイント以上獲得するか、ルーレットを X 回プレイするまでに支払う金額の期待値を f(X) とする。E=\displaystyle\lim _ {X\to+\infty}f(X) とする。

この問題の条件のもとで、高橋くんがどのような戦略をとっても \displaystyle\lim _ {X\to+\infty}f(X) が有限の値になることが証明できます。高橋くんが E を最小にするような戦略をとったときの E の値を求めてください。

制約

1\leq N\leq 100
1\leq M\leq 100
1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
1\leq P _ i\leq 100\ (1\leq i\leq N)
0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
\displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
入力はすべて整数

入力

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

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

出力

高橋くんが M ポイント以上獲得するまでに支払う金額の期待値を 1 行で出力せよ。出力された値と真の値の相対誤差もしくは絶対誤差が 10 ^ {-5} 以下のとき、正答と判定される。

入力例 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

出力例 1

215.913355350494384765625

例えば、高橋くんはルーレットを次のようにプレイすることができます。

50 円を支払ってルーレット 2 をプレイする。S _ {2,4}=8 ポイントを得る。
50 円を支払ってルーレット 2 をプレイする。S _ {2,1}=1 ポイントを得る。
100 円を支払ってルーレット 1 をプレイする。S _ {1,1}=5 ポイントを得る。得たポイントの合計が 8+1+5\geq14 ポイントとなったため、終了する。

この例では、14 ポイントを得るまでに 200 円を支払っています。

出力と真の値の相対誤差もしくは絶対誤差が 10 ^ {-5} 以下のとき正答と判定されるため、215.9112 や 215.9155 などと出力しても正解になります。

入力例 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

出力例 2

100 ポイントが出るまでルーレット 2 を回し続けるのが最適です。

入力例 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

出力例 3

45037.072314895291126319493887599716

Score : 475 points

Problem Statement

There are N roulette wheels. The i-th (1\leq i\leq N) wheel has P _ i integers S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} written on it, and you can play it once by paying C _ i yen. When you play the i-th wheel once, an integer j between 1 and P _ i, inclusive, is chosen uniformly at random, and you earn S _ {i,j} points.

The points you earn from the wheels are determined independently of past results.

Takahashi wants to earn at least M points. Takahashi will act to minimize the amount of money he pays before he earns at least M points. After each play, he can choose which wheel to play next based on the previous results.

Find the expected amount of money Takahashi will pay before he earns at least M points.

More formal definition

Here is a more formal statement. For a strategy that Takahashi can adopt in choosing which wheel to play, the expected amount of money E that he pays before he earns at least M points with that strategy is defined as follows.

For a natural number X, let f(X) be the expected amount of money Takahashi pays before he earns at least M points or plays the wheels X times in total according to that strategy. Let E=\displaystyle\lim _ {X\to+\infty}f(X).

Under the conditions of this problem, it can be proved that \displaystyle\lim _ {X\to+\infty}f(X) is finite no matter what strategy Takahashi adopts. Find the value of E when he adopts a strategy that minimizes E.

Constraints

1\leq N\leq 100
1\leq M\leq 100
1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
1\leq P _ i\leq 100\ (1\leq i\leq N)
0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
\displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
C _ 1 P _ 1 S _ {1,1} S _ {1,2} \ldots S _ {1,P _ 1}
C _ 2 P _ 2 S _ {2,1} S _ {2,2} \ldots S _ {2,P _ 2}
\vdots
C _ N P _ N S _ {N,1} S _ {N,2} \ldots S _ {N,P _ N}

Output

Print the expected amount of money Takahashi will pay until he earns at least M points in a single line. Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}.

Sample Input 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

Sample Output 1

215.913355350494384765625

For instance, Takahashi can play the wheels as follows.

Pay 50 yen to play roulette 2 and earn S _ {2,4}=8 points.
Pay 50 yen to play roulette 2 and earn S _ {2,1}=1 point.
Pay 100 yen to play roulette 1 and earn S _ {1,1}=5 points. He has earned a total of 8+1+5\geq14 points, so he quits playing.

In this case, he pays 200 yen before earning 14 points.

Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}, so outputs such as 215.9112 and 215.9155 would also be considered correct.

Sample Input 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

Sample Output 2

It is optimal to keep spinning roulette 2 until you get 100 points.

Sample Input 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

Sample Output 3

45037.072314895291126319493887599716

I - Vacation Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

0, 1 からなる長さ N の文字列 S が与えられます。S の i 文字目を S_i とします。

Q 個のクエリを与えられた順に処理してください。
クエリは 3 個の整数の組 (c, L, R) で表されて、c の値によってクエリの種類が異なります。

c=1 のとき : L \leq i \leq R を満たす整数 i について、S_i が 1 ならば 0 に、0 ならば 1 に変更する。
c=2 のとき : S の L 文字目から R 文字目までを取り出して出来る文字列を T とする。T に含まれる連続する 1 の長さの最大値を出力する。

制約

1 \leq N \leq 5 \times 10^5
1 \leq Q \leq 10^5
S は長さ N の 0, 1 からなる文字列
c \in \lbrace 1, 2 \rbrace
1 \leq L \leq R \leq N
N, Q, c, L, R は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは次の形式で与えられる。

c L R

出力

c=2 であるクエリの個数を k として、k 行出力せよ。
i 行目には i 番目の c=2 であるクエリに対する答えを出力せよ。

入力例 1

出力例 1

クエリを順に処理すると次のようになります。

はじめ、S= 1101110 です。
1 番目のクエリについて、T = 1101110 です。T に含まれる連続する 1 の中で最も長いものは、T の 4 文字目から 6 文字目からなる 111 なので、答えは 3 になります。
2 番目のクエリについて、T = 101 です。T に含まれる連続する 1 の中で最も長いものは、T の 1 文字目あるいは 3 文字目の 1 なので、答えは 1 になります。
3 番目のクエリについて、操作後の S は 1110000 です。
4 番目のクエリについて、T = 00 です。T に 1 は含まれないので答えは 0 になります。
5 番目のクエリについて、操作後の S は 1111111 です。
6 番目のクエリについて、T = 1111111 です。T に含まれる連続する 1 の中で最も長いものは、T の 1 文字目から 7 文字目からなる 1111111 なので、答えは 7 になります。

Score : 550 points

Problem Statement

You are given a string S of length N consisting of 0 and 1. Let S_i denote the i-th character of S.

Process Q queries in the order they are given.
Each query is represented by a tuple of three integers (c, L, R), where c represents the type of the query.

When c=1: For each integer i such that L \leq i \leq R, if S_i is 1, change it to 0; if it is 0, change it to 1.
When c=2: Let T be the string obtained by extracting the L-th through R-th characters of S. Print the maximum number of consecutive 1s in T.

Constraints

1 \leq N \leq 5 \times 10^5
1 \leq Q \leq 10^5
S is a string of length N consisting of 0 and 1.
c \in \lbrace 1, 2 \rbrace
1 \leq L \leq R \leq N
N, Q, c, L, and R are all integers.

Input

The input is given from Standard Input in the following format, where \mathrm{query}_i represents the i-th query:

N Q
S
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

c L R

Output

Let k be the number of queries with c=2. Print k lines.
The i-th line should contain the answer to the i-th query with c=2.

Sample Input 1

Sample Output 1

The queries are processed as follows.

Initially, S= 1101110.
For the first query, T = 1101110. The longest sequence of consecutive 1s in T is 111 from the 4-th character to 6-th character, so the answer is 3.
For the second query, T = 101. The longest sequence of consecutive 1s in T is 1 at the 1-st or 3-rd character, so the answer is 1.
For the third query, the operation changes S to 1110000.
For the fourth query, T = 00. T does not contain 1, so the answer is 0.
For the fifth query, the operation changes S to 1111111.
For the sixth query, T = 1111111. The longest sequence of consecutive 1s in T is 1111111 from the 1-st to 7-th characters, so the answer is 7.