Problem Statement

Given is a 2 \times 2 matrix A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}.
The determinant of A can be found as ad-bc.
Find it.

Constraints

• All values in input are integers.
• -100 \le a, b, c, d \le 100

Sample Input 1

1 2
3 4

Sample Output 1

-2

The determinant of \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} is 1 \times 4 - 2 \times 3 = -2.

Sample Input 2

0 -1
1 0

Sample Output 2

1

Sample Input 3

100 100
100 100

Sample Output 3

0

Problem Statement

Takahashi will answer N quiz questions.
Initially, he has X points. Each time he answers a question, he gains 1 point if his answer is correct and loses 1 point if it is incorrect.
However, there is an exception: when he has 0 points, he loses nothing for answering a question incorrectly.

You will be given a string S representing whether Takahashi's answers are correct.
If the i-th character of S from the left is o, it means his answer for the i-th question is correct; if that character is x, it means his answer for the i-th question is incorrect.
How many points will he have in the end?

Constraints

• 1 \le N \le 2 \times 10^5
• 0 \le X \le 2 \times 10^5
• S is a string of length N consisting of o and x.

Sample Input 1

3 0
xox

Sample Output 1

0

Initially, he has 0 points.
He answers the first question incorrectly but loses nothing because he has no point.
Then, he answers the second question correctly, gains 1 point, and now has 1 point.
Finally, he answers the third question incorrectly, loses 1 point, and now has 0 points.
Thus, he has 0 points in the end. We should print 0.

Sample Input 2

20 199999
oooooooooxoooooooooo

Sample Output 2

200017

Sample Input 3

20 10
xxxxxxxxxxxxxxxxxxxx

Sample Output 3

0

Problem Statement

There is an infinite two-dimensional grid, and we have a piece called Super Ryuma at square (r_1, c_1). (Ryu means dragon and Ma means horse.) In one move, the piece can go to one of the squares shown below:

More formally, when Super Ryuma is at square (a, b), it can go to square (c, d) such that at least one of the following holds:

• a + b = c + d
• a - b = c - d
• |a - c| + |b - d| \le 3

Find the minimum number of moves needed for the piece to reach (r_2, c_2) from (r_1, c_1).

Constraints

• All values in input are integers.
• 1 \le r_1, c_1, r_2, c_2 \le 10^9

Sample Input 1

1 1
5 6

Sample Output 1

2

We need two moves - for example, (1, 1) \rightarrow (5, 5) \rightarrow (5, 6).

Sample Input 2

1 1
1 200001

Sample Output 2

2

We need two moves - for example, (1, 1) \rightarrow (100001, 100001) \rightarrow (1, 200001).

Sample Input 3

2 3
998244353 998244853

Sample Output 3

3

We need three moves - for example, (2, 3) \rightarrow (3, 3) \rightarrow (-247, 253) \rightarrow (998244353, 998244853).

Sample Input 4

1 1
1 1

Sample Output 4

0

Problem Statement

We have a bag containing A gold coins, B silver coins, and C bronze coins.

Until the bag contains 100 coins of the same color, we will repeat the following operation:

Operation: Randomly take out one coin from the bag. (Every coin has an equal probability of being chosen.) Then, put back into the bag two coins of the same kind as the removed coin.

Find the expected value of the number of times the operation is done.

Constraints

• 0 \leq A,B,C \leq 99
• A+B+C \geq 1

Sample Input 1

99 99 99

Sample Output 1

1.000000000

No matter what coin we take out in the first operation, the bag will contain 100 coins of that kind.

Sample Input 2

98 99 99

Sample Output 2

1.331081081

We will do the second operation only if we take out a gold coin in the first operation. Thus, the expected number of operations is 2\times \frac{98}{98+99+99}+1\times \frac{99}{98+99+99}+1\times \frac{99}{98+99+99}=1.331081081\ldots

Sample Input 3

0 0 1

Sample Output 3

99.000000000

Each operation adds a bronze coin.

Sample Input 4

31 41 59

Sample Output 4

91.835008202

Problem Statement

There is a town represented as a two-dimensional grid with H horizontal rows and W vertical columns.
A character a_{i,j} describes the square at the i-th row from the top and j-th column from the left. Here, a_{i,j} is one of the following: S , G , . , # , a, ..., and z.
# represents a square that cannot be entered, and a, ..., z represent squares with teleporters.

Takahashi is initially at the square represented as S. In each second, he will make one of the following moves:

• Go to a non-# square that is horizontally or vertically adjacent to his current position.
• Choose a square with the same character as that of his current position, and teleport to that square. He can only use this move when he is at a square represented as a, ..., or z.

Find the shortest time Takahashi needs to reach the square represented as G from the one represented as S.
If the destination is unreachable, report -1 instead.

Constraints

• 1 \le H, W \le 2000
• a_{i,j} is S, G, ., #, or a lowercase English letter.
• There is exactly one square represented as S and one square represented as G.

Sample Input 1

2 5
S.b.b
a.a.G

Sample Output 1

4

Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Initially, Takahashi is at (1, 1). One way to reach (2, 5) in four seconds is:

• go from (1, 1) to (2, 1);
• teleport from (2, 1) to (2, 3), which is also an a square;
• go from (2, 3) to (2, 4);
• go from (2, 4) to (2, 5).

Sample Input 2

11 11
S##...#c...
...#d.#.#..
..........#
.#....#...#
#.....bc...
#.##......#
.......c..#
..#........
a..........
d..#...a...
.#........G

Sample Output 2

14

Sample Input 3

11 11
.#.#.e#a...
.b..##..#..
#....#.#..#
.#dd..#..#.
....#...#e.
c#.#a....#.
.....#..#.e
.#....#b.#.
.#...#..#..
......#c#G.
#..S...#...

Sample Output 3

-1

Problem Statement

Takahashi will participate in a programming contest, which lasts for T minutes and presents N problems.
With his extrasensory perception, he already knows that it will take A_i minutes to solve the i-th problem.
He will choose zero or more problems to solve from the N problems so that it takes him no longer than T minutes in total to solve them.
Find the longest possible time it takes him to solve his choice of problems.

Constraints

• All values in input are integers.
• 1 \le N \le 40
• 1 \le T \le 10^9
• 1 \le A_i \le 10^9

Sample Input 1

5 17
2 3 5 7 11

Sample Output 1

17

If he chooses the 1-st, 2-nd, 3-rd, and 4-th problems, it takes him 2+3+5+7=17 minutes in total to solve them, which is the longest possible time not exceeding T=17 minutes.

Sample Input 2

6 100
1 2 7 5 8 10

Sample Output 2

33

It is optimal to solve all the problems.

Sample Input 3

6 100
101 102 103 104 105 106

Sample Output 3

0

He cannot solve any of the problems.

Sample Input 4

7 273599681
6706927 91566569 89131517 71069699 75200339 98298649 92857057

Sample Output 4

273555143

If he chooses the 2-nd, 3-rd, and 7-th problems, it takes him 273555143 minutes in total to solve them.