# 题解 - [Atcoder ABC 184] (C - F)

## 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 Input 1

1 | 1 1 |

### Sample Output 1

1 | 2 |

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

### Sample Input 2

1 | 1 1 |

### Sample Output 2

1 | 2 |

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

### Sample Input 3

1 | 2 3 |

### Sample Output 3

1 | 3 |

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

### Sample Input 4

1 | 1 1 |

### Sample Output 4

1 | 0 |

### 解题思路

做这题时我想到了国际象棋中的象，如果两点同色，则必然能在两步内到达

不难发现最多只需三步即可到达

其他的情况简单讨论下即可

### 代码参考

## Show code

1 | /* |

## 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 Input 1

1 | 99 99 99 |

### Sample Output 1

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

1 | 98 99 99 |

### Sample Output 2

1 | 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...\)

### Sample Input 3

1 | 0 0 1 |

### Sample Output 3

1 | 99.000000000 |

Each operation adds a bronze coin.

### Sample Input 4

1 | 31 41 59 |

### Sample Output 4

1 | 91.835008202 |

### 解题思路

比较简单的期望 MS

设 \(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

1 | /* |

## 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 `S`

tandard 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 Input 1

1 | 2 5 |

### Sample Output 1

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

1 | 11 11 |

### Sample Output 2

1 | 14 |

### Sample Input 3

1 | 11 11 |

### Sample Output 3

1 | -1 |

### 解题思路

简单的 BFS 会卡一个点，要加优化

注意到任意一个传送门最多都只会经过一次，所以我们可以把经过的传送门销毁

注意一下 `std::list<>.erase()`

的用法

### 代码参考

## Show code

1 | /* |

## 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 Input 1

1 | 5 17 |

### Sample Output 1

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

1 | 6 100 |

### Sample Output 2

1 | 33 |

It is optimal to solve all the problems.

### Sample Input 3

1 | 6 100 |

### Sample Output 3

1 | 0 |

He cannot solve any of the problems.

### Sample Input 4

1 | 7 273599681 |

### Sample Output 4

1 | 273555143 |

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

### 解题思路

直接查肯定 T, 折半搜索可以

将数据分成两部分，一部分二进制枚举所有可能结果并排序；另一部分二进制枚举，二分查找前一部分结果中满足 " 两部分结果之和 \(<T\)" 的最大结果

### 复杂度

\(\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

1 | /* |