## C - Super Ryuma

### 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|≤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≤r_1,c_1,r_2,c_2≤10^9$$

### Input

Input is given from Standard Input in the following format:

$$\begin{matrix} r_1&c_1\\ r_2&c_2 \end{matrix}$$

### Output

Print the minimum number of moves needed for Super Ryuma to reach $$(r_2,c_2)$$ from $$(r_1,c_1)$$.

### Sample Output 1

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

### Sample Output 2

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

### Sample Output 3

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

Show code

## D - increment of coins

### 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≤A,B,C≤99$$
• $$A+B+C≥1$$

### Input

Input is given from Standard Input in the following format:

$$A\ B\ C$$

### Output

Print the expected value of the number of times the operation is done. Your output will be accepted if its absolute or relative error from the correct value is at most $$10^{-6}$$.

### Sample Output 1

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

### Sample Output 2

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...$$

### Sample Output 3

Each operation adds a bronze coin.

### 解题思路

$$f(a,b,c)$$ 表示三种硬币各有 $$a,b,c$$ 个的时候，胜利的期望步数

$f(a,b,c)=\frac{a\ f(a+1,b,c)+b\ f(a,b+1,c)+c\ f(a,b,c+1)}{a+b+c}+1$

Show code

## E - Third Avenue

### 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≤H,W≤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.

### Input

Input is given from Standard Input in the following format:

$$\begin{matrix} H&W\\ a_{1,1}&...&a_{1,W}\\ \vdots\\ a_{H,1}&...&a_{H,W} \end{matrix}$$

### Output

Print the shortest time Takahashi needs to reach the square represented as G from the one represented as S. If the destination is unreachable from the initial position, print -1 instead.

### Sample Output 1

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)$$.

Show code

## F - Programming Contest

### 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 Ai 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≤N≤40$$
• $$1≤T≤109$$
• $$1≤A_i≤109$$

### Input

Input is given from Standard Input in the following format:

$$\begin{matrix} N&T\\ A_1&...&A_N \end{matrix}$$

### Output

Print the answer as an integer.

### Sample Output 1

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 Output 2

It is optimal to solve all the problems.

### Sample Output 3

He cannot solve any of the problems.

### Sample Output 4

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

### 复杂度

$$\displaystyle\Theta\left(n\cdot 2^\frac{n}{2}+2^\frac{n}{2}\left(\frac{n}{2}\right)^2\right)\implies O\left(\left(\frac{n}{2}\right)^22^\frac{n}{2}\right)$$

Show code