Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

• All participants who ranked A-th or higher get a T-shirt.
• Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

• All values in input are integers.
• 1 \le A < B \le 1000
• 1 \le C \le B-A
• 1 \le X \le 1000

Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.

Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.

Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

Problem Statement

There is a row of N people. They are described by a string S of length N. The i-th person from the front is male if the i-th character of S is M, and female if it is F.

Determine whether the men and women are alternating.

It is said that the men and women are alternating if and only if there is no position where two men or two women are adjacent.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• S is a string of length N consisting of M and F.

Sample Input 1

6
MFMFMF

Sample Output 1

Yes

There is no position where two men or two women are adjacent, so the men and women are alternating.

Sample Input 2

9
FMFMMFMFM

Sample Output 2

No

Sample Input 3

1
F

Sample Output 3

Yes

Problem Statement

There are N platforms arranged in a row. The height of the i-th platform from the left is H_i.

Takahashi is initially standing on the leftmost platform.

Since he likes heights, he will repeat the following move as long as possible.

• If the platform he is standing on is not the rightmost one, and the next platform to the right has a height greater than that of the current platform, step onto the next platform.

Find the height of the final platform he will stand on.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq H_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
1 5 10 4 2

Sample Output 1

10

Takahashi is initially standing on the leftmost platform, whose height is 1. The next platform to the right has a height of 5 and is higher than the current platform, so he steps onto it.

He is now standing on the 2-nd platform from the left, whose height is 5. The next platform to the right has a height of 10 and is higher than the current platform, so he steps onto it.

He is now standing on the 3-rd platform from the left, whose height is 10. The next platform to the right has a height of 4 and is lower than the current platform, so he stops moving.

Thus, the height of the final platform Takahashi will stand on is 10.

Sample Input 2

3
100 1000 100000

Sample Output 2

100000

Sample Input 3

4
27 1828 1828 9242

Sample Output 3

1828

Problem Statement

A supermarket sells egg packs.

A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.

When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.

Constraints

• 1 \leq N \leq 100
• 1 \leq S,M,L \leq 10^4
• All input values are integers.

Sample Input 1

16 120 150 200

Sample Output 1

300

It is optimal to buy two 8-egg packs.

Sample Input 2

10 100 50 10

Sample Output 2

10

It is optimal to buy one 12-egg pack.

Sample Input 3

99 600 800 1200

Sample Output 3

10000

It is optimal to buy five 8-egg packs and five 12-egg packs.

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

• 1 \leq a \lt b \leq H
• 1 \leq c \lt d \leq W
• There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

• 2 \leq H, W \leq 500
• S_{i,j} is # or ..

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

Problem Statement

You are given two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.

Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.

Constraints

• 1 \leq N,M \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

2 2
1 6
4 9

Sample Output 1

2

Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.

Sample Input 2

1 1
10
10

Sample Output 2

0

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Sample Output 3

3

Problem Statement

Given is a sequence of length N: A=(A_1,A_2,\ldots,A_N), and an integer K.

How many of the contiguous subsequences of A have the sum of K?
In other words, how many pairs of integers (l,r) satisfy all of the conditions below?

• 1\leq l\leq r\leq N
• \displaystyle\sum_{i=l}^{r}A_i = K

Constraints

• 1\leq N \leq 2\times 10^5
• |A_i| \leq 10^9
• |K| \leq 10^{15}
• All values in input are integers.

Sample Input 1

6 5
8 -3 5 7 0 -4

Sample Output 1

3

(l,r)=(1,2),(3,3),(2,6) are the three pairs that satisfy the conditions.

Sample Input 2

2 -1000000000000000
1000000000 -1000000000

Sample Output 2

0

There may be no pair that satisfies the conditions.

Problem Statement

There is a connected undirected graph with N vertices and M edges, where the i-th edge connects vertex U_i and vertex V_i bidirectionally.
Each vertex has an integer written on it, with integer A_v written on vertex v.

For a simple path from vertex 1 to vertex N (a path that does not pass through the same vertex multiple times), the score is determined as follows:

• Let S be the sequence of integers written on the vertices along the path, listed in the order they are visited.
• If S is not non-decreasing, the score of that path is 0.
• Otherwise, the score is the number of distinct integers in S.

Find the path from vertex 1 to vertex N with the highest score among all simple paths and print that score.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• N-1 \le M \le 2 \times 10^5
• 1 \le A_i \le 2 \times 10^5
• The graph is connected.
• 1 \le U_i < V_i \le N
• (U_i,V_i) \neq (U_j,V_j) if i \neq j.

Sample Input 1

5 6
10 20 30 40 50
1 2
1 3
2 5
3 4
3 5
4 5

Sample Output 1

4

The path 1 \rightarrow 3 \rightarrow 4 \rightarrow 5 has S=(10,30,40,50) for a score of 4, which is the maximum.

Sample Input 2

4 5
1 10 11 4
1 2
1 3
2 3
2 4
3 4

Sample Output 2

0

There is no simple path from vertex 1 to vertex N such that S is non-decreasing. In this case, the maximum score is 0.

Sample Input 3

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

Sample Output 3

5

Problem Statement

There is a directed graph with N vertices and M edges. Each edge has two positive integer values: beauty and cost.

For i = 1, 2, \ldots, M, the i-th edge is directed from vertex u_i to vertex v_i, with beauty b_i and cost c_i. Here, the constraints guarantee that u_i \lt v_i.

Find the maximum value of the following for a path P from vertex 1 to vertex N.

• The total beauty of all edges on P divided by the total cost of all edges on P.

Here, the constraints guarantee that the given graph has at least one path from vertex 1 to vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq u_i \lt v_i \leq N
• 1 \leq b_i, c_i \leq 10^4
• There is a path from vertex 1 to vertex N.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0.7500000000000000

For the path P that passes through the 2-nd, 6-th, and 7-th edges in this order and visits vertices 1 \rightarrow 3 \rightarrow 4 \rightarrow 5, the total beauty of all edges on P divided by the total cost of all edges on P is (b_2 + b_6 + b_7) / (c_2 + c_6 + c_7) = (9 + 4 + 2) / (5 + 8 + 7) = 15 / 20 = 0.75, and this is the maximum possible value.

Sample Input 2

3 3
1 3 1 1
1 3 2 1
1 3 3 1

Sample Output 2

3.0000000000000000

Sample Input 3

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

Sample Output 3

1.8333333333333333