title: [ICPC2016 WF] Swap Space

description:
You administer a large cluster of computers with hard drives that use various file system types to store data. You recently decided to unify the file systems to the same type. That is quite a challenge since all the drives are currently in use, all of them are filled with important data to the limits of their capacities, and you cannot afford to lose any of the data. Moreover, reformatting a drive to use a new file system may significantly change the drive’s capacity. To make the reformat possible, you will have to buy an extra hard drive. Obviously, you want to save money by minimizing the size of such extra storage.

You can reformat the drives in any order. Prior to reformatting a drive, you must move all data from that drive to one or more other drives, splitting the data if necessary. After a drive is reformatted, you can immediately start using it to store data from other drives. It is not necessary to put all the data on the same drives they originally started on – in fact, this might even be impossible if some of the drives have smaller capacity with the new file system. It is also allowed for some data to end up on the extra drive.

As an example, suppose you have four drives $A$, $B$, $C$, and $D$ with drive capacities $6$, $1$, $3$, and $3$ GB. Under the new file system, the capacities become $6$, $7$, $5$, and $5$ GB, respectively. If you buy only $1$ GB of extra space, you can move the data from drive $B$ there and then reformat drive $B$. Now you have $7$ GB free on drive $B$, so you can move the $6$ GB from drive $A$ there and reformat drive $A$. Finally, you move the six total gigabytes from drives $C$ and $D$ to drive $A$, and reformat $C$ and $D$.

inputFormat:
The input begins with a line containing one integer $n$ ($1 \le n \le 10^6$), which is the number of drives in your cluster. Following this are $n$ lines, each describing a drive as two integers $a$ and $b$, where $a$ is the capacity with the old file system and $b$ is the capacity with the new file system.

All capacities are given in gigabytes and satisfy $1 \le a,b \le 10^9$. (One thousand petabytes should be enough for everyone, right?)

outputFormat: Display the total extra capacity in gigabytes you must buy to reformat the drives.

translation:
### 题目描述

你有许多电脑，它们的硬盘用不同的文件系统储存数据。你想要通过格式化来统一文件系统。格式化硬盘可能使它的容量发生变化。为了格式化，你需要买额外的硬盘。当然，你想要买容量最小的额外储存设备以便省钱。你可以按任意顺序格式化硬盘。格式化之前，你要把该硬盘上所有数据移到一个或更多的其他硬盘上（可以分割数据）。格式化后，该硬盘可以立刻开始使用。你没有必要把数据放到它原来所在的硬盘上。数据也可以被放到你额外买的硬盘上。举个例子，假设你有4个硬盘A、B、C、D，容量分别为6、1、3、3(GB)。新的文件系统下，它们的容量变为6、7、5、5(GB)。如果你只买1GB额外空间，你可以把B硬盘的数据放过去然后格式化硬盘B。现在你的B硬盘有7GB容量了，那么你就可以把A的数据放过去然后格式化A，最后把C、D的数据放到A上，再格式化C和D。

### 输入格式

第一行一个数 $n(1≤n≤1,000,000)$，表示你的硬盘数。接下来 $n$ 行，每行两个数 $a$ 和 $b$，分别表示该硬盘的原容量和新文件系统下的容量。所有容量都以 GB 为单位，且$1≤a,b≤1,000,000,000$。

### 输出格式

输出如果要格式化所有硬盘，你最少需要购买多少额外空间(GB)。


title: [ICPC2016 WF] What Really Happened on Mars?

type: P

description:
Real-time software in the Mars Pathfinder spacecraft suffered from an issue known as priority inversion. One technique to address this issue is to use the Priority Ceiling Protocol.

In this problem, you will simulate the execution of multiple tasks according to this protocol. The tasks share a collection of resources, each of which can be used by only one task at a time. To ensure this, resources must be locked before use and unlocked after use. Each task is defined by a start time, a unique base priority, and a sequence of instructions. Each task also has a current priority, which may change during execution. Instructions come in three types:

compute – perform a computation for one microsecond

lock $k$ – lock resource $k$ (which takes no processor time)

unlock $k$ – unlock resource $k$ (which takes no processor time)

After locking a resource, a task is said to own the resource until the task unlocks it. A task will unlock only the owned resource it most recently locked, will not lock a resource it already owns, and will complete with no owned resources.

Each resource has a fixed priority ceiling, which is the highest base priority of any task that contains an instruction to lock that resource.

There is a single processor that executes the tasks. When the processor starts, it initializes its clock to zero and then runs an infinite loop with the following steps:

  Step 1.

Identify running tasks. A task is running if its start time is less than or equal to the current processor clock and not all of its instructions have been executed.

  Step 2.

Determine the current priorities of the running tasks and which of the running tasks are blocked. A running task $T$ is blocked if the next instruction in $T$ is to lock resource $k$ and either resource $k$ is already owned or at least one other task owns a resource $\ell $ whose priority ceiling is greater than or equal to the current priority of $T$. If $T$ is blocked, it is said to be blocked by every task owning such $k$ or $\ell $. The current priority of a task $T$ is the maximum of $T$’s base priority and the current priorities of all tasks that $T$ blocks.

  Step 3.

Execute the next instruction of the non-blocked running task (if any) with the highest current priority. If there was no such task or if a compute instruction was executed, increment the processor clock by one microsecond. If a lock or unlock instruction was executed, do not increment the clock.

The Priority Ceiling Protocol defined above has the following properties:

Current priority is defined in terms of current priority and blocking, and blocking is defined in terms of current priority. While this may appear circular, there will always be a unique set of current priorities that satisfy the definitions.

All tasks will eventually complete.

There will never be a tie in step 3.

inputFormat:
The first line of the input contains two integers $t$ $(1 \leq t \leq 20)$, which is the number of tasks, and $r$ ($1 \leq r \leq 20$), which is the number of resources. This is followed by $t$ lines, where the $i^\text {th}$ of these lines describes task $i$. The description of a task begins with three integers: the task’s start time $s$ ($1 \leq s \leq 10\, 000$), its base priority $b$ ($1 \leq b \leq t$), and an integer $a$ ($1 \leq a \leq 100$). A task description is concluded by a sequence of $a$ strings describing the instructions. Each string is a letter (C or L or U) followed by an integer. The string C$n$ ($1 \leq n \leq 100$) indicates a sequence of $n$ compute instructions. The strings L$k$ and U$k$ ($1 \leq k \leq r$) indicate instructions locking and unlocking resource $k$ respectively.

No two tasks have the same base priority.

outputFormat: For each task, display the time it completes execution, in the same order that the tasks are given in the input.

translation:
你有 $t$ 个进程和 $r$ 个资源，每个进程包含其起始时间与**基础优先级**（保证两两不同），以及若干条指令。指令有以下三种：

- `compute`：进行计算，消耗 $1$ 微秒。
- `lock k`：锁定编号为 $k$ 的资源，不耗时。
- `unlock k`：解锁编号为 $k$ 的资源，不耗时。

在进程锁定资源后，这个进程就拥有了这个资源直到这个进程将它解锁。保证任意进程只会解锁最近锁定的资源，不会锁定自身拥有的资源，且在进程结束时不会拥有任何资源。

每个资源有一个固定的属性**最高优先级**，即包含锁定该资源指令的所有进程的最高**基础优先级**。

有一个处理器处理这些进程。处理器有一个时钟初始为 $0$，然后重复执行下列步骤：

1. 找出所有正在运行的进程。如果进程开始的时间不大于处理器的时钟且该进程的指令未运行完毕，那么称这个进程正在运行。

2. 决定当前所有正在运行的进程的优先级，以及哪些正在运行的进程会被阻塞。进程 $T$ 会被阻塞当且仅当：

   - 进程 $T$ 的下一条指令是锁定资源 $k$。
   - 资源 $k$ 已经被其他进程拥有，或存在另一个进程拥有某个资源 $\ell$，$\ell$ 的**最高优先级**大于 $T$ 的**当前优先级**。

   此时我们称进程 $T$ 被所有拥有资源 $k$ 或满足条件的资源 $\ell$ 的进程阻塞。定义 $T$ 的**当前优先级**为所有阻塞它的进程的**当前优先级**与它本身的**基础优先级**的最大值。

3. 执行**当前优先级**最高且没有被阻塞的进程的下一条指令。如果不存在这样的进程或者执行的指令是 `compute`，则将时钟加 $1$ 微秒。

你需要求所有进程的结束时间。可以证明所有进程一定会结束。

输入格式：

第一行两个整数 $t,r$ 表示进程和资源个数。

接下来 $t$ 行每行描述一个进程，格式如下：

- 三个整数 $s,b,a$，表示进程起始时间、基础优先级、指令条数。
- 接下来 $a$ 个字符串，每个字符串表示一条指令。字符串形如 `Cn` 表示连续 $n$ 个 `compute` 指令（**相互独立**），`Lk` 表示锁定资源 $k$，`Rk` 表示解锁资源 `k`。

输出格式：

$t$ 行每行一个整数表示进程执行完毕的时间。

数据范围：$1 \le t,r \le 20,s \le 10^4,1 \le b \le t$ 且互不相同，$a \le 100$，`Cn` 中 $n \le 100$，`Lk,Rk` 中 $1 \le k \le r$。

Translated by pokefunc (uid=188716)

hint:
Time limit: 1000 ms, Memory limit: 1048576 kB.

 International Collegiate Programming Contest (ACM-ICPC) World Finals 2016


title: [ICPC2017 WF] Airport Construction

description:
The tropical island nation of Piconesia is famous for its beautiful beaches, lush vegetation, cocoa and coffee plantations, and wonderful weather all year round. This paradise is being considered as a future location for the World Finals of the ACM International Collegiate Programming Contest (or at the very least a vacation spot for the executive council). There is only one small problem: the island is really hard to reach.

Currently, the fastest way to reach the island takes three days from the nearest airport, and uses a combination of fishing boat, oil tanker, kayak, and submarine. To make attending the ICPC World Finals slightly easier and to jump-start the island's tourism business, Piconesia is planning to build its first airport.

Since longer landing strips can accommodate larger airplanes, Piconesia has decided to build the longest possible landing strip on their island. Unfortunately, they have been unable to determine where this landing strip should be located. Maybe you can help?

For this problem we model the boundary of Piconesia as a polygon. Given this polygon, you need to compute the length of the longest landing strip (i.e., straight line segment) that can be built on the island. The landing strip must not intersect the sea, but it may touch or run along the boundary of the island. Figure A.1 shows an example corresponding to the first sample input.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14633/1.png)

Figure A.1 : The island modeled as a polygon. The longest possible landing strip is shown as a thick line.

inputFormat: The input starts with a line containing an integer $n (3 \le n \le 200)$ specifying the number of vertices of the polygon. This is followed by $n$ lines, each containing two integers $x$ and $y (|x|, |y| \le 10^{6})$ that give the coordinates $(x , y)$ of the vertices of the polygon in counter-clockwise order. The polygon is simple, i.e., its vertices are distinct and no two edges of the polygon intersect or touch, except that consecutive edges touch at their common vertex. In addition, no two consecutive edges are collinear.

outputFormat: Display the length of the longest straight line segment that fits inside the polygon, with an absolute or relative error of at most $10^{−6}.$

translation:
给定一个 $n$ 边形，第 $i$ 个点为 $(x_i,y_i)$，并且保证顺时针给出。求一条在 $n$ 边形内的最长线段。

$3 \le n \le 200$，$|x|,|y| \le 10^6$。

翻译者：一只书虫仔

hint: Time limit: 2 s, Memory limit: 512 MB.


title: [ICPC2017 WF] Get a Clue!

description:
Developed in the $1940s$ in the United Kingdom, the game of Cluedo is one of the most popular board games in the world. The object of the game is to determine who murdered Mr. Body, which weapon was used to murder him, and where the murder took place. The game uses a set of cards representing six persons (labeled A , $B$ , . . . , $F)$ , six weapons (labeled $G , H$ , . . . , $L)$ and nine rooms (labeled $M , N$ , . . . , $U)$ . At the start of the game, one person card, one weapon card, and one room card are selected at random and removed from the deck so no one can see them $-$ they represent the murderer, the murder weapon, and the murder location. The remaining $18$ cards are shuffled and dealt to the players, starting with player $1$ , then to her right player $2$ , and so on. Some players may end up with one more card than others. For the purposes of this problem there are four players, so the person to the right of player $4$ is player $1$ .

The rest of the game is spent searching for clues. Players take turns, starting with player $1$ and moving to the right. A turn consists of making a suggestion (consisting of a murder suspect, a weapon, and a room) and asking other players if they have any evidence that refutes the suggestion. For example, you might say to another player `I believe the murderer was person A , using weapon $L$ , in room $T$ . $`$ If the other player is holding exactly one of these cards, that player must show you (and only you) that card. If they have more than one such card, they can show you any one of them.

When making a suggestion, you must first ask the person to your right for any evidence. If they have none, you continue with the person on their right, and so on, until someone has evidence, or no one has any of the cards in your suggestion.

Many times you can gain information even if you are not the person making the suggestion. Suppose, in the above example, you are the third player and have cards A and $T$ . If someone else shows evidence to the suggester, you know that it must be weapon card $L$ . Keeping track of suggestions and who gave evidence at each turn is an important strategy when playing the game.

To win the game, you must make an accusation, where you state your final guess of the murderer, weapon, and room. After stating your accusation, you check the three cards that were set aside at the start of the game $-$ if they match your accusation, you win! Needless to say, you want to be absolutely sure of your accusation before you make it.

Here is your problem. You are player $1$ . Given a set of cards dealt to you and a history of suggestions and evidence, you need to decide how close you are to being able to make an accusation.

inputFormat: The input starts with an integer $n (1 \le n \le 50)$ , the number of suggestions made during the game. Following this is a line containing the five cards you are dealt, all uppercase letters in the range $‘A'.$ . . $‘U'.$ The remaining $n$ lines contain one suggestion per line. Each of these lines starts with three characters representing the suggestion (in the order person, weapon, room), followed by the responses of up to three players, beginning with the player to the right of the player making the suggestion. If a player presents no evidence, a $‘-'$ (dash) is listed; otherwise an `evidence character` is listed. If the specific evidence card is seen by you (either because you provided it or you were the person receiving the evidence) then the evidence $character identifies$ that card; otherwise the evidence character is $‘ \times '.$ Note that only the last response can be an evidence character. All characters are separated by single spaces. Only valid $suggestio_n/response$ sequences appear in the input.

outputFormat: Display a three character string identifying the murderer, the murder weapon, and the room. If the murderer can be identified, use the appropriate letter for that person; otherwise use $‘?'.$ Do the same for the murder weapon and the room.

translation:
翻译者吐槽：这个 Cluedo 不就是弹丸论破的学级裁判嘛（

---

Cluedo 是一个盛行的游戏，游戏目的是找出一场谋杀案的凶手。这个游戏是一个卡牌游戏，一共有 $21$ 张卡牌，分类为：A $\sim $ F 是嫌疑人卡牌，G $\sim $ L 是凶器卡牌，M $\sim $ U 是犯罪现场卡牌，在游戏的开始，会在三种卡牌中分别抽出一张，代表真正的凶手，凶器和犯罪现场。

今天，你和你的 $3$ 个小伙伴也来玩 Cluedo 了，你们坐成一个环，你是玩家 $1$，你的小伙伴分别为玩家 $2,3,4$，按照 $1 \to 2 \to 3 \to 4 \to 1 \to 2 \cdots$ 的顺序进行游戏。每一次会从剩下的卡堆中抽出任意一张卡给玩家，直到分完为止。

分完牌后，从玩家 $1$ 开始，还是按照环的顺序，依次提出意见，格式示例为「我认为嫌疑人 A 是凶手，凶器为 L，作案现场是 T」，然后从这个玩家的右手位开始提反对意见，如果要提反对意见的玩家手里有表明意见的玩家要说的牌（因为凶手，凶器和犯罪现场都已经拿出了，所以所有玩家手里都应该没有真正的牌，有的话说明意见错误），那么他就可以成功的提反对意见。如果他不提反对意见，那么反对意见权交给他的右手位，直到有人提出或者没有反对意见。注意，如果 A 对 B 提出反对意见，那么他进行反对的那一张卡牌只有 A 和 B 能看到。

你作为类似于学级裁判中的主侦探一位，你要说明最终意见，即你对凶手，凶器和犯罪现场的最终猜测。在进行猜测后，如果你的猜测与正确结果符合，那么你就赢了。因为你有脑子，所以你只会在得到准确证据后才会进行最终猜测。

现在给定意见数 $n$，你手中的初始卡牌，以及每一次意见，求你能推理出的最终猜测。如果你无法得到完整的最终猜测，请把你尚未得到结论的地方用 $\texttt ?$ 输出。

备注：意见如下描述：

- 首先三个字符代表这个意见所提出的凶手，凶器和犯罪现场。
- 接下来一个或两个或三个字符代表反对意见情况，从他的右手位开始表示，如果这个玩家没有反对意见，那么 $\texttt -$，如果这个玩家有反对意见，且你是提出意见的人或者是进行反对的人，那么输出反驳的是哪张卡牌。如果你不是提出意见的人或者进行反对的人，那么输出 $\texttt *$。当输出了反驳情况时，就可以换行进行下一个意见的反对意见判断了。否则，一直进行到三名玩家的反对意见都判断完。

$1 \le n \le 50$。

翻译者：一只书虫仔

samples:
3
A C M S D
B G S - G
A H S - - S
C J S *

hint: Time limit: 4 s, Memory limit: 512 MB.


title: [ICPC2017 WF] Mission Improbable

description:
It is a sunny day in spring and you are about to meet Patrick, a close friend and former partner in crime. Patrick lost most of his money betting on programming contests, so he needs to pull off another job. For this he needs your help, even though you have retired from a life of crime. You are reluctant at first, as you have no desire to return to your old criminal ways, but you figure there is no harm in listening to his plan.

There is a shipment of expensive consumer widgets in a nearby warehouse and Patrick intends to steal as much of it as he can. This entails finding a way into the building, incapacitating security guards, passing through various arrays of laser beams $-$ you know, the usual heist techniques. However, the heart of the warehouse has been equipped with a security system that Patrick cannot disable. This is where he needs your help.

The shipment is stored in large cubical crates, all of which have the same dimensions. The crates are stacked in neat piles, forming a three-dimensional grid. The security system takes pictures of the piles once per hour using three cameras: a front camera, a side camera and a top camera. The image from the front camera shows the height of the tallest pile in each column, the image from the side camera shows the height of the tallest pile in each row, and the image from the top camera shows whether or not each pile is empty. If the security system detects a change in any of the images, it sounds an alarm.

Once Patrick is inside, he will determine the heights of the piles and send them to you. Figure C.1 shows a possible layout of the grid and the view from each of the cameras.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14635/1.png)

Figure C.1 : Grid of heights and the corresponding camera views.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14635/2.png)

Figure C.2 : Possible grid of heights after the heist

Patrick wants to steal as many crates as possible. Since he cannot disable the security system, he plans to fool it by arranging the remaining crates into piles so that the next set of camera images are the same. In the above example, it is possible to steal nine crates. Figure C.2 shows one possible post-heist configuration that appears identical to the security system.

Patrick asks you to help him determine the maximum number of crates that can be stolen while leaving a configuration of crates that will fool the security system. Will you help him pull off this final job?

inputFormat: The first line of input contains two integers $r (1 \le r \le 100)$ and $c (1 \le c \le 100)$ , the number of rows and columns in the grid, respectively. Each of the following $r$ lines contains $c$ integers, the heights (in crates) of the piles in the corresponding row. All heights are between $0$ and $10^{9}$ inclusive.

outputFormat: Display the maximum number of crates that can be stolen without being detected.

translation:
给定一个 $r \times c$ 的平面，在上面摆有一些箱子。我们可以得到他的三视图（如下图，左边矩阵上的值为平面上每一位摆放的箱子个数，右边三个视图为正视图，俯视图，左视图）：

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14635/1.png)

你可以拿走一些箱子，和重新排列这些箱子的位置，你想知道，最多能拿走多少个箱子，使得这些箱子重新排列后正视图，俯视图，左视图不变？

比如上面这个例子，下面这种拿走 $9$ 个箱子后的重新排列方式也是可以的：

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14635/2.png)

$1 \le r,c \le 100$，平面上每一个位置的箱子个数在 $[0,10^9]$ 内。

翻译者：一只书虫仔

hint: Time limit: 1 s, Memory limit: 512 MB.


title: [ICPC2017 WF] Money for Nothing

description:
In this problem you will be solving one of the most profound challenges of humans across the world since the beginning of time $-$ how to make lots of money.

You are a middleman in the widget market. Your job is to buy widgets from widget producer companies and sell them to widget consumer companies. Each widget consumer company has an open request for one widget per day, until some end date, and a price at which it is willing to buy the widgets. On the other hand, each widget producer company has a start date at which it can start delivering widgets and a price at which it will deliver each widget.

Due to fair competition laws, you can sign a contract with only one producer company and only one consumer company. You will buy widgets from the producer company, one per day, starting on the day it can start delivering, and ending on the date specified by the consumer company. On each of those days you earn the difference between the producer's selling price and the consumer's buying price.

Your goal is to choose the consumer company and the producer company that will maximize your profits.

inputFormat: The first line of input contains two integers $m$ and $n (1 \le m , n \le 500 000)$ denoting the number of producer and consumer companies in the market, respectively. It is followed by $m$ lines, the $i$ th of which contains two integers $p_{i}$ and $d_{i} (1 \le p_{i}, d_{i} \le 10^{9}),$ the price (in dollars) at which the $i$ th producer sells one widget and the day on which the first widget will be available from this company. Then follow $n$ lines, the $j$ th of which contains two integers $q_{j}$ and $e_{j} (1 \le q_{j}, e_{j} \le 10^{9}),$ the price (in dollars) at which the $j$ th consumer is willing to buy widgets and the day immediately after the day on which the last widget has to be delivered to this company.

outputFormat: Display the maximum total number of dollars you can earn. If there is no way to sign contracts that gives you any profit, display $0$ .

translation:
一共有 $m$ 个生产商和 $n$ 个消费商。第 $i$ 个生产商从第 $d_i$ 个时刻开始销售物品，每个物品卖 $p_i$ 元。第 $i$ 个消费商从第 $1$ 个时刻开始需要消费，他的消费欲望一直到第 $e_i-1$ 的时刻，每个物品出价 $q_i$ 元。你作为中间商，只能与一间生产商和一间消费商签订合约，可以选择在生产商那里买下一些物品，也可以选择卖向消费商，你的目的就是赚中间的差价。

你想知道最多能赚到多少差价。

$1 \le m,n \le 5\times 10^5$，$1 \le p_i,d_i,q_i,e_i \le 10^9$。

翻译者：一只书虫仔

hint: Time limit: 5 s, Memory limit: 512 MB.


title: [ICPC2017 WF] Need for Speed

description:
![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14637/1.png)

Sheila is a student and she drives at ypical student car: it is old, slow, rusty, and falling apart. Recently,the needle on the speedometer fell off. She glued it back on, but she might have placed it at the wrong angle. Thus, when the speedometer reads $s$,her true speed is $s+c$, where $c$ is an unknown constant(possibly negative).

Sheila made a careful record of a recent journey and wants to use this to compute $c$ . The journey consisted of $n$ segments. In the $i^{th}$ segment she traveled a distance of $d_{i}$ and the speedometer read $s_{i}$ for the entire segment. This whole journey took time $t$ . Help Sheila by computing $c$ .

Note that while Sheila's speedometer might have negative readings, her true speed was greater than zero for each segment of the journey.

inputFormat: The first line of input contains two integers $n (1 \le n \le 1 000)$ , the number of sections in Sheila's journey, and $t (1 \le t \le 10^{6}),$ the total time. This is followed by $n$ lines, each describing one segment of Sheila's journey. The $i^{th}$ of these lines contains two integers $d_{i} (1 \le d_{i} \le 1 000)$ and $s_{i} (|s_{i}| \le 1 000)$ , the distance and speedometer reading for the $i^{th}$ segment of the journey. Time is specified in hours, distance in miles, and speed in miles per hour.

outputFormat: Display the constant $c$ in miles per hour. Your answer should have an absolute or relative error of less than $10^{−6}.$

translation:
在你面前的是一个坏掉的速度表，当显示速度为 $s$ km/h 时，实际速度为 $s+c$ km/h，$c$ 为固定的常数，为任意实数。你打算计算这个 $c$，于是准备用这个速度表记录速度。现在你要走 $n$ 段路程，第 $i$ 段路程距离为 $d_i$ 米，显示的指数为 $s_i$ km/h，总共路程用了 $t$ 小时。求 $c$ 的值。

你的答案应该与正确答案的差在 $10^{-6}$ 以内。

$1 \le n \le 1000$，$1 \le t \le 10^6$，$1 \le d_i \le 1000$，$|s_i| \le 1000$。

翻译者：一只书虫仔

hint:
Time limit: 1 s, Memory limit: 512 MB.

spj provider:@[shenyouran](/user/137367).


title: [ICPC2017 WF] Posterize

description:
![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14638/1.png)

Pixels in a digital picture can be represented with three integers in the range $0$ to $255$ that indicate the intensity of the red, green, and blue colors. To compress an image or to create an artistic effect, many photo-editing tools include a `posterize` operation which works as follows. Each color channel is examined separately; this problem focuses only on the red channel. Rather than allow all integers from $0$ to $255$ for the red channel, a posterized image allows at most $k$ integers from this range. Each pixel's original red intensity is replaced with the nearest of the allowed integers. The photo-editing tool selects a set of $k$ integers that minimizes the sum of the squared errors introduced across all pixels in the original image. If there are $n$ pixels that have original red values $r_{1},$ . . . , $r_{n},$ and $k$ allowed integers $v_{1},$ . . . , $v_{k},$ the sum of squared errors is defined as

$\(\su_m_{i=1}^{n}{\mi_n_{1 \le j \le k}{(r_i - v_j)^2}}\).$

Your task is to compute the minimum achievable sum of squared errors, given parameter $k$ and a description of the red intensities of an image's pixels.

inputFormat: The first line of the input contains two integers $d (1 \le d \le 256)$ , the number of distinct red values that occur in the original image, and $k (1 \le k \le d)$ , the number of distinct red values allowed in the posterized image. The remaining $d$ lines indicate the number of pixels of the image having various red values. Each such line contains two integers $r (0 \le r \le 255)$ and $p (1 \le p \le 2^{26}),$ where $r$ is a red intensity value and $p$ is the number of pixels having red intensity $r$ . Those $d$ lines are given in increasing order of red value.

outputFormat: Display the sum of the squared errors for an optimally chosen set of $k$ allowed integer values.

translation:
给定 $d$ 类元素，第 $i$ 类元素的取值为 $r_i$，且有 $p_i$ 个，按照这些信息可以将这些元素排列在一个长度为 $n=\sum p_i$ 的序列里，现在你要做的是规划一个长度为 $k$ 的序列 $v_i$，使得按照如下定义的序列误差最小：

$$\sum\limits_{i=1}^n \min\limits_{1 \le j \le k}(r_i-v_j)^2$$

求最小序列误差。

$1 \le k \le d \le 256$，$0 \le r \le 255$，$1 \le p \le 2^{26}$。

翻译者：一只书虫仔


title: [ICPC2017 WF] Replicate Replicate Rfplicbte

description:
The owner of the Automatic Cellular Manufacturing corporation has just patented a new process for the mass production of identical parts. Her approach uses a two-dimensional lattice of two-state cells, each of which is either `empty` or `filled. ` The exact details are, of course, proprietary.

Initially, a set of cells in the lattice is filled with a copy of the part that is to be reproduced. In a sequence of discrete steps, each cell in the lattice simultaneously updates its state by examining its own state and those of its eight surrounding neighbors. If an odd number of these nine cells are filled, the cell's state in the next time step will be filled, otherwise it will be empty. Figure G.1 shows several steps in the replication process for a simple pattern consisting of three filled cells.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14639/1.png)

Figure G.1 : The replication process.

However, a bug has crept into the process. After each update step, one cell in the lattice might spontaneously flip its state. For instance, Figure G.2 shows what might happen if a cell flipped its state after the first time step and another flipped its state after the third time step.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14639/2.png)

Figure G.2 : Errors in the replication process. This figure corresponds to Sample Input $1$ .

Unfortunately, the original patterns were lost, and only the (possibly corrupted) results of the replication remain. Can you write a program to determine a smallest possible nonempty initial pattern that could have resulted in a given final pattern?

inputFormat: The first line of input contains two integers $w (1 \le w \le 300)$ and $h (1 \le h \le 300)$ , where $w$ and $h$ are the width and height of the bounding box of the final pattern. Following that are $h$ lines, each containing $w$ characters, giving the final pattern. Each character is either $‘. '$ (representing an empty cell) or $‘#'$ (representing a filled cell). There is at least one filled cell in the first row, in the last row, in the first column, and in the last column.

outputFormat: Display a minimum-size nonempty pattern that could have resulted in the given pattern, assuming that at each stage of the replication process at most one cell spontaneously changed state. The size of a pattern is the area of its bounding box. If there is more than one possible minimum-size nonempty starting pattern, any one will be accepted. Use the character $‘. '$ for empty cells and $‘#'$ for filled cells. Use the minimum number of rows and columns needed to display the pattern.

translation:
定义一个黑白复制过程，每一次枚举所有格子初始时自身和周围 $8$ 个格子这 $9$ 个格子的黑白情况，如果有奇数个位置为黑，那么这个格子变为黑，否则变为白。但不幸的是，复制过程有 bug，每一次进行复制后，都会有任意一个格子从黑变为白，或者从白变为黑，当然也可以不变。现在给定一份包含 bug 的复制最终结果，包含 $w$ 行 $h$ 列，求行列数最小的初始黑白格子，使得能通过复制过程和 bug 变为最终结果。

$\texttt \#$ 为黑，$\texttt .$ 为白。

注意，如果有多余的白色格子请省掉，比如左边这个黑白格子情况可以变为右边的：

```
...........   .....##..#
......##..#   #........#
.#........#   #..#...#..
.#..#...#..   .#.......#
..#.......#
...........
...........
```

$1 \le w,h \le 300$。

翻译者：一只书虫仔

hint: Time limit: 3 s, Memory limit: 512 MB.


title: [ICPC2017 WF] Scenery

description:
![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14640/1.png)

Images by John Fowler, Carol Highsmith, and Richard Woodland

You have decided to spend a day of your trip to Rapid City taking photographs of the South Dakota Badlands, which are renowned for their spectacular and unusual land formations. You are an amateur photographer, yet very particular about lighting conditions.

After some careful research, you have located a beautiful location in the Badlands, surrounded by picturesque landscapes. You have determined a variety of features that you wish to photograph from this location. For each feature you have identified the earliest and latest time of day at which the position of the sun is ideal. However, it will take quite a bit of time to take each photograph, given the need to reposition the tripod and camera and your general perfectionism. So you are wondering if it will be possible to successfully take photographs of all these features in one day.

inputFormat: The first line of the input contains two integers $n (1 \le n \le 10^{4})$ and $t (1 \le t \le 10^{5}),$ where $n$ is the number of desired photographs and $t$ is the time you spend to take each photograph. Following that are $n$ additional lines, each describing the available time period for one of the photographs. Each such line contains two nonnegative integers a and $b$ , where a is the earliest time that you may begin working on that photograph, and $b$ is the time by which the photograph must be completed, with a $+ t \le b \le 10^{9}.$

outputFormat: Display yes if it is possible to take all $n$ photographs, and no otherwise.

translation:
你要拍 $n$ 张照片，每张照片必须在 $[a_i,b_i]$ 这个时间段内完成拍摄，并且拍每一张图片都需要用 $t$ 的时间，同一个时间内只能拍摄一张图片。求是否能拍摄完所有照片。

$1 \le n \le 10^4$，$1 \le t \le 10^5$，$a_i+t \le b_i \le 10^9$。

翻译者：一只书虫仔

hint: Time limit: 6 s, Memory limit: 512 MB.


title: [ICPC2017 WF] Secret Chamber at Mount Rushmore

description:
![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/14641/1.png)

By now you have probably heard that there is a spectacular stone sculp-ture featuring four famous U.S. presidents at Mount Rushmore.  How-ever, very few people know that this monument contains a secret cham-ber. This sounds like something out of a plot of a Hollywood movie, butthe chamber really exists.  It can be found behind the head of AbrahamLincoln and was designed to serve as a Hall of Records to store impor-tant historical U.S. documents and artifacts.  Historians claim that theconstruction of the hall was halted in 1939 and the uncompleted cham-ber was left untouched until the late 1990s,  but this is not the wholetruth.

In $1982$ , the famous archaeologist $S$ . Dakota Jones secretly visited the monument and found that the chamber actually was completed, but it was kept confidential. This seemed suspicious and after some poking around, she found a hidden vault and some documents inside. Unfortunately, these documents did not make any sense and were all gibberish. She suspected that they had been written in a code, but she could not decipher them despite all her efforts.

Earlier this week when she was in the area to follow the ACM-ICPC World Finals, Dr. Jones finally discovered the key to deciphering the documents, in Connolly Hall of $SDSM&T$ . She found a document that contains a list of translations of letters. Some letters may have more than one translation, and others may have no translation. By repeatedly applying some of these translations to individual letters in the gibberish documents, she might be able to decipher them to yield historical U.S . documents such as the Declaration of Independence and the Constitution. She needs your help.

You are given the possible translations of letters and a list of pairs of original and deciphered words. Your task is to verify whether the words in each pair match. Two words match if they have the same length and if each letter of the first word can be turned into the corresponding letter of the second word by using the available translations zero or more times.

inputFormat: The first line of input contains two integers $m (1 \le m \le 500)$ and $n (1 \le n \le 50)$ , where $m$ is the number of translations of letters and $n$ is the number of word pairs. Each of the next $m$ lines contains two distinct space-separated letters a and $b$ , indicating that the letter a can be translated to the letter $b$ . Each ordered pair of letters $(a , b)$ appears at most once. Following this are $n$ lines, each containing a word pair to check. Translations and words use only lowercase letters $‘a'-‘z',$ and each word contains at least $1$ and at most $50$ letters.

outputFormat: For each pair of words, display yes if the two words match, and no otherwise.

translation:
一共有 $m$ 种字母的转换关系，每一种转换关系表示为，可以从小写字母 $a$ 转化为小写字母 $b$，转换关系单向且不重复。现在给定 $n$ 组询问，每一组询问字符串 $s$ 是否能通过转换关系变为 $t$。

$1 \le m \le 500$，$1 \le n \le 50$，$a,b$ 只为小写字母，$s,t$ 只包含小写字母，长度在 $[1,50]$ 内。

翻译者：一只书虫仔

samples:
9 5
c t
i r
k p
o c
r o
t e
t f
u h
w p
we we
can the
work people
it of
out the


title: [ICPC2017 WF] Son of Pipe Stream

description:
Two years ago, you helped install the nation's very first Flubber pipe network in your hometown, to great success. Polls show that everyone loves having their own Flubber dispenser in their kitchen, and now a few enterprising citizens have discovered a use for it. Apparently Flubber, when mixed with water, can help extinguish fires! This is a very timely discovery, as out-of-control fires have lately been surprisingly common.

Your hometown's city council would like to make use of this property of Flubber by creating the $Flubber/water$ mixture at a centrally located station. This station, which is called the Flubber Department (FD) will also have specialized employees trained to travel to the locations of fires and make use of their processed Flubber to control the blazes.

The pipes are already in place all around the city. You are given a layout of the pipes, and must determine how to route Flubber from the Flubber factory and water from a local source through the pipes to the FD.

Note that both Flubber and water will be flowing through the same network of pipes, perhaps even the same pipe. All pipes are bidirectional, but Flubber and water cannot move in opposite directions through the same pipe. Furthermore, if both liquids are sent in the same direction through the same pipe, they will inevitably mix. Therefore the nodes in the network have been equipped with special membranes and filters that enable you to separate and reorganize all incoming mixtures as you see fit. The network is a closed system, so the total rate of each fluid going into a node must equal the total rate of that fluid going out, except at the source of that fluid and the destination (the FD).

Each pipe has a certain capacity. Flubber, being somewhat sluggish, has a viscosity value $v$ , so a pipe that can transport $v liters/second$ of water can transport only $1 liter/second$ of Flubber. The pipe's capacity scales linearly for mixtures of the two. To be precise, if $c$ denotes the water capacity of the pipe and $f$ and $w$ are the rates of Flubber and water moving through the pipe (all measured in $liters/second),$ then the capacity constraint is given by the inequality $v · f + w \le c$ .

Your main concern is balancing the mixture that reaches the FD. You would like as much total liquid as possible, but you also need a sufficient amount of water $-$ because undiluted Flubber is highly flammable $-$ and a sufficient amount of Flubber $-$ because it would not be much of a `Flubber Department` without Flubber! You have come up with a formula to measure the `value` of the final mixture: $F^{a} · W^{1−a},$ where $F$ is the rate of incoming Flubber in $liters/second, W$ is the rate of incoming water in $liters/second,$ and a is a given constant between $0$ and $1$ .

Determine the maximum value of $F^{a} · W^{1−a}$ that can be achieved and how to route the Flubber and water to achieve it.

inputFormat:
The input starts with a line containing the number of locations $n (3 \le n \le 200)$ , the number of pipes $p (n − 1 \le p \le $ n(n $− 1)/2)$ , and the real values $v (1 \le v \le 10)$ and a ($0$ . $01 \le $ a $ \le 0$ . $99$) . Locations are numbered from $1$ to $n$ ; $1$ is the Flubber factory, $2$ is the water source, and $3$ is the FD. The real values have at most $10$ digits after the decimal point.

The following $p$ lines each describe one pipe. Each line contains two integers $j$ and $k (1 \le j < k \le n)$ , giving the locations connected by the pipe, and an integer $c (1 \le c \le 10)$ , giving the water capacity of the pipe in $liters/second.$

No two pipes connect the same pair of locations. Furthermore, it is guaranteed that the network is connected.

outputFormat:
First, for each pipe (in the order given in the input), display two values: the rate of Flubber moving through it, and the rate of water moving through it (negative if the liquid is moving from $k$ to $j)$ , such that $F^{a} ·W^{1−a}$ is maximized. Then display that maximum value accurate to within an absolute error of $10^{−4}.$

If there are multiple solutions, any one will be accepted. All constraints (not sending Flubber and water in opposite directions along the same pipe, flow conservation, pipe capacities, and consistency between the constructed solution and its claimed value) must be satisfied within an absolute error of $10^{−4}.$

translation:
### 题目描述
两年以前，你帮助你的家乡安装了国内的第一个 Flubber 管道网络，获得了巨大成功。投票表明每个人都喜欢在自己家的厨房里装上 Flubber 分配器，而现在一些有进取心的市民发现了一种新的用途——Flubber 和水混合后似乎可以帮助灭火！这是一个很及时的发现，因为最近无法控制的大火出奇地常见。

你家乡的市议会想在一个位于中央的地方制造 Flubber 和水的混合物以利用 Flubber 的这个属性。这个被称为 Flubber 部门的地方拥有专门训练的员工去往着火的地点并且利用经过处理的 Flubber 来控制火势。

管道已经在城市中铺设好。你会得到管道布局，而你需要决定如何将 Flubber 从 Flubber 工厂、将水从一个本地水源通过管道运送至 Flubber 部门。

注意 Flubber 和水会在同一管道网络中，甚至可能在同一条管道中流动。所有管道是双向的，但是 Flubber 和水不能在同一条管道中异向流动。此外，如果两种液体同向流过一条管道，它们会不可避免地混合，因此网络中的所有节点配备了特殊的膜和筛，如你所见，可以分离和重新组织所有流入的混合物。管道网络是个封闭系统，因此在每个节点处每种液体的总流入速率必须等于总流出速率，除了每种液体各自的源头和目的地（Flubber 部门）。

每条管道有某个容量，有些粘稠的 Flubber 有一个粘度值 v，所以能运输 v 升每秒的水的管道只能运输 1 升每秒的 Flubber。管道对于混合物的容量是线性变化的。更精确地，假设 c 表示管道对于水的容量，f 和 w 分别表示 Flubber 和水流过管道的速率（单位均为升每秒），则容量的限制用不等式 v⋅f+w≤c 表示。

你主要关心的是平衡流到 Flubber 部门的混合物。你想要尽可能多的混合液体，但是也需要足够的水——因为未经稀释的 Flubber 是高度易燃的——也需要足够的 Flubber——因为 Flubber 部门可不能没了 Flubber！你想出了一个公式来衡量最终混合物的价值：$F^a⋅W^{1−a}$，其中 F 是以升每秒为单位的 Flubber 的流入速率，W 是以升每秒为单位的水的流入速率，a 是一个给定的介于 0 和 1 之间的常数。

求出 $F^a⋅W^{1−a}$ 能达到的最大值以及如何安排 Flubber 和水的路径来达到它。

### 输入格式
输入的第一行包含地点的数量 n (3≤n≤300)，管道的数量 $p (n−1≤p≤\frac12n(n−1))$，和实数 v (1≤v≤10) 和 a (0.01≤a≤0.99)。地点从 1 到 n 标号；1 是 Flubber 工厂，2 是水源，3 是 Flutter 部门。实数的小数点后最多有十位。

接下来的 p 行每行描述了一条管道。每行有两个整数 j 和 k (1≤j<k≤n)，表示管道连接的地点，和一个整数 c (1≤c≤10)，表示这条管道的水容量，以升每秒为单位。

没有两条管道连接相同的两个地点，此外，还保证网络是连通的。

### 输出格式
首先，对于每条管道（按照输入的顺序），输出两个值：其中 Flubber 流过的速率和其中水流过的速率 （如果从 k 流到 j 则为负数），使得 $F^a⋅W^{1−a}$ 最大化。然后输出其最大值，在 $10^{−4}$ 的绝对误差以内。

如果有多解，输出任意一种均可。所有限制（Flubber 和水没有在同一条管道内异向流动、流量守恒、管道容量以及构造的解和其声称的值的一致性）需要在 $10^{−4}$ 的绝对误差内满足。


title: [ICPC2017 WF] Tarot Sham Boast

description:
Curse your rival! Every year at the annual Rock Paper Scissors tournament, you have made it to the final match. (Your Rock technique is unmatched, and your Paper cuts to the bone! Your Scissors need a little work, though. ) But every year, he defeats you, even though his moves appear entirely random! And he claims to the press that he simply cannot be beaten. What is his secret?

Fortunately, you think you have figured it out. This year, just before the tournament, you caught him visiting various shamans around town. Aha! He is using the supernatural against you! You figured two can play at this game. So you went and visited a set of fortune-tellers, who have each used a Tarot deck to predict a sequence that your rival will end up using, sometime during the match.

However, your initial excitement has passed, and now you are feeling a little silly. This cannot possibly work, right? In the end it feels like you have paid good money for a fraudulent, random set of predictions. Oh well; you might as well keep an eye out for some of them during the match. But which predictions will you use?

In the final match, you and your rival will play $n$ rounds of Rock Paper Scissors. In each round, your rival and you will both choose one of the three options (Rock, Paper, or Scissors). Based on your selections, a winner of the round will be determined (exactly how is irrelevant to this problem).

Given the length of the final match and the various predictions, sort them in order of how likely they are to appear sometime during the match as a contiguous sequence of options chosen by your rival, assuming he is choosing his symbol in each round independently and uniformly at random.

inputFormat: The first line of input contains two integers $n (1 \le n \le 10^{6}),$ the number of rounds in the final match, and $s (1 \le s \le 10)$ , the number of sequences. The remaining $s$ lines each describe a prediction, consisting of a string of characters $‘R', ‘P',$ and $‘S'.$ All predictions have the same length, which is between $1$ and $n$ characters long, inclusive, and no longer than $10^{5}.$

outputFormat: Display all of the predictions, sorted by decreasing likelihood of appearance sometime during the final match. In the case of tied predictions, display them in the same order as in the input.

translation:
定义某字符串  $s$ 的出现概率为：随机敲  $n$ 个 `R,P,S`， $s$ 作为其子串出现的概率。

给出  $s$ 个长度为  $l$ 的只含 `R,P,S` 的字符串，请你按这  $l$ 个字符串的出现概率从大到小排序。若概率相等则按输入顺序排序。

 $n\le 10^6,s\le 10,l\le 10^5$。


title: [ICPC2017 WF] Visual Python++

description:
In the recently proposed Visual Python++ programming language, a block of statements is represented as a rectangle of characters with top-left corner in row $r_{1}$ and column $c_{1},$ and bottom-right corner in row $r_{2}$ and column $c_{2}.$ All characters at locations $(r , c)$ with $r_{1} \le r \le r_{2}$ and $c_{1} \le c \le c_{2}$ are then considered to belong to that block. Among these locations, the ones with $r = r_{1}$ or $r = r_{2}$ or $c = c_{1}$ or $c = c_{2}$ are called a border.

Statement blocks can be nested (rectangles contained in other rectangles) to an arbitrary level. In a syntactically correct program, every two statement blocks are either nested (one contained in the other) or disjoint (not overlapping). In both cases, their borders may not overlap.

Programmers are not expected to draw the many rectangles contained in a typical program $-$ this takes too long, and Visual $Pytho_n++$ would not have a chance to become the next ICPC programming language. So a programmer only has to put one character $‘p'$ in the top-left corner of the rectangle and one character $‘y'$ in the bottom-right corner. The parser will automatically match up the appropriate corners to obtain the nesting structure of the program.

Your team has just been awarded a five-hour contract to develop this part of the parser.

inputFormat: The first line of the input contains an integer $n (1 \le n \le 10^{5}),$ the number of corner pairs. Each of the next $n$ lines contains two integers $r$ and $c (1 \le r , c \le 10^{9}),$ specifying that there is a top-left corner in row $r$ and column $c$ of the program you are parsing. Following that are $n$ lines specifying the bottom-right corners in the same way. All corner locations are distinct.

outputFormat: Display $n$ lines, each containing one integer. A number $j$ in line $i$ means that the $i^{th}$ top-left corner and the $j^{th}$ bottom-right corner form one rectangle. Top-left and bottom-right corners are each numbered from $1$ to $n$ in the order they appear in the input. The output must be a permutation of the numbers from $1$ to $n$ such that the matching results in properly nested rectangles. If there is more than one valid matching, any one will be accepted. If no such matching exists, display syntax error.

translation:
# 题意

有 $n$ 个矩形，每个矩形左上角为 $(r_1,c_1)$ ，右下角为 $(r_2,c_2)$。

矩形可以嵌套（矩形包含在其他矩形中）任意层。在合法的情况下，任意两个矩形要么是嵌套的（一个包含在另一个中），要么是不交的（不重叠）。在这两种情况中，他们的 **边界也不能重叠**。

# 输入格式

第一行包含一个整数 $n(1\leq n \leq 10^5)$ ，表示矩形的数量。

接下来 $n$ 行，每行两个整数 $r$ 和 $c(1\leq r,c\leq 10^9)$ ，指定 $(r,c)$ 为第 $i$ 个左上角坐标。

接下来 $n$ 行，每行两个整数 $r$ 和 $c(1\leq r,c\leq 10^9)$ ，指定 $(r,c)$ 为第 $j$ 个右下角坐标。

所有给定坐标互不相同。

# 输出格式

输出 $n$ 行，每行包含一个整数。第 $i$ 行整数 $j$ 表示第 $i$ 个左上角和第 $j$ 个右下角组成一个矩形。左上角和右下角均按照他们在输入中的顺序从 $1$ 到 $n$ 标号。输出必须是 $1$ 到 $n$ 的排列，从而匹配可能嵌套的矩形。如果存在超过一种合法的匹配，任意一组合法的匹配都是可接受的。如果不存在合法的匹配，输出 `syntax error`。


title: [ICPC2018 WF] Catch the Plane

description:
Your plane to the ICPC Finals departs in a short time, and the only way to get to the airport is by bus. Unfortunately, some of the bus drivers are considering going on strike, so you do not know whether you can get to the airport on time. Your goal is to plan your journey in such a way as to maximize the probability of catching your plane.

You have a detailed map of the city, which includes all the bus stations. You are at station $0$ and the airport is at station $1$ . You also have a complete schedule of when each bus leaves its start station and arrives at its destination station. Additionally, for each bus you know the probability that it is actually going to run as scheduled, as opposed to its driver going on strike and taking the bus out of service. Assume all these events are independent. That is, the probability of a given bus running as planned does not change if you know whether any of the other buses run as planned.

If you arrive before the departure time of a bus, you can transfer to that bus. But if you arrive exactly at the departure time, you will not have enough time to get on the bus. You cannot verify ahead of time whether a given bus will run as planned $-$ you will find out only when you try to get on the bus. So if two or more buses leave a station at the same time, you can try to get on only one of them.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15689/1.png)

Figure A.1 : Bus schedule corresponding to Sample Input $1$ .

Consider the bus schedule shown in Figure A.1 . It lists the start and destination stations of several bus routes along with the departure and arrival times. You have written next to some of these the probability that that route will run. Bus routes with no probability written next to them have a $100\%$ chance of running. You can try catching the first listed bus. If it runs, it will take you straight to the airport, and you can stop worrying. If it does not, things get more tricky. You could get on the second listed bus to station $2$ . It is certain to leave, but you would be too late to catch the third listed bus which otherwise would have delivered you to the airport on time. The fourth listed bus $-$ which you can catch $-$ has only a $0$ . $1$ probability of actually running. That is a bad bet, so it is better to stay at station $0$ and wait for the fifth listed bus. If you catch it, you can try to get onto the sixth listed bus to the airport; if that does not run, you still have the chance of returning to station $0$ and catching the last listed bus straight to the airport.

inputFormat:
The first line of input contains two integers $m (1 \le m \le 10^{6})$ and $n (2 \le n \le 10^{6}),$ denoting the number of buses and the number of stations in the city. The next line contains one integer $k (1 \le k \le 10^{18}),$ denoting the time by which you must arrive at the airport.

Each of the next $m$ lines describes one bus. Each line contains integers a and $b (0 \le $ a , $b < n$ , a $≠ b)$ , denoting the start and destination stations for the bus. Next are integers $s$ and $t (0 \le s < t \le k)$ , giving the departure time from station a and the arrival time at station $b$ . The last value on the line is $p (0 \le p \le 1$ , with at most $10$ digits after the decimal point), which denotes the probability that the bus will run as planned.

outputFormat: Display the probability that you will catch your plane, assuming you follow an optimal course of action. Your answer must be correct to within an absolute error of $10^{−6}.$

translation:
给定一个图，有 $n$ 个点和 $m$ 条有向边，你现在在 $0$ 号点，你要在 $k$ 的时间前到达 $1$ 号点。

每条边从 $a$ 连向 $b$，在 $s$ 时间到达 $a$ 就可以用 $t$ 的时间到达 $b$，如果你要从 $a$ 到达 $b$，可以选择提前到达然后在 $a$ 等待，或者刚刚好用 $s$ 的时候到达 $a$，但是超过 $s$ 的时间到达就不能通过这条边到达 $b$ 了。每条边有 $p$ 的概率不能通过。

求准时到达 $1$ 号点的概率。

翻译者：一只书虫仔

hint:
Time limit: 10 s, Memory limit: 1024 MB.

spj provider:@[shenyouran](/user/137367).


title: [ICPC2018 WF] Comma Sprinkler

description:
As practice will tell you, the English rules for comma placement are complex, frustrating, and often ambiguous. Many people, even the English, will, in practice, ignore them, and, apply custom rules, or, no rules, at all.

Doctor Comma Sprinkler solved this issue by developing a set of rules that sprinkles commas in a sentence with no ambiguity and little simplicity. In this problem you will help Dr. Sprinkler by producing an algorithm to automatically apply her rules.

Dr. Sprinkler's rules for adding commas to an existing piece of text are as follows:

If a word anywhere in the text is preceded by a comma, find all occurrences of that word in the text, and put a comma before each of those occurrences, except in the case where such an occurrence is the first word of a sentence or already preceded by a comma.

If a word anywhere in the text is succeeded by a comma, find all occurrences of that word in the text, and put a comma after each of those occurrences, except in the case where such an occurrence is the last word of a sentence or already succeeded by a comma.

Apply rules $1$ and $2$ repeatedly until no new commas can be added using either of them.

As an example, consider the text

please sit spot. sit spot, sit. spot here now here.

Because there is a comma after spot in the second sentence, a comma should be added after spot in the third sentence as well (but not the first sentence, since it is the last word of that sentence). Also, because there is a comma before the word sit in the second sentence, one should be added before that word in the first sentence (but no comma is added before the word sit beginning the second sentence because it is the first word of that sentence). Finally, notice that once a comma is added after spot in the third sentence, there exists a comma before the first occurrence of the word here. Therefore, a comma is also added before the other occurrence of the word here. There are no more commas to be added so the final result is

please, sit spot. sit spot, sit. spot, here now, here.

inputFormat:
The input contains one line of text, containing at least $2$ characters and at most $1 000 000$ characters. Each character is either a lowercase letter, a comma, a period, or a space. We define a word to be a maximal sequence of letters within the text. The text adheres to the following constraints:

The text begins with a word.

Between every two words in the text, there is either a single space, a comma followed by a space, or a period followed by a space (denoting the end of a sentence and the beginning of a new one).

The last word of the text is followed by a period with no trailing space.

outputFormat: Display the result after applying Dr. Sprinkler's algorithm to the original text.

translation:
给定一些文本，对他添加逗号。

添加的规则为：

1. 找到一个单词前面有逗号，就在文本中的其他这个单词前添加一个逗号，除非这个单词是句子的第一个单词，或单词前已经有逗号了。
2. 找到一个单词后面有逗号，就在文本中的其他这个单词后添加一个逗号，除非这个单词是句子的最后一个单词，或单词后已经有逗号了。
3. 重复 1 和 2 直到不能填加逗号。

$2 \le $ 文本长度 $ \le 10^6$。

文本满足以下特征：

- 文本开头为一个单词；
- 两个单词之间为一个空格，或者一个逗号一个空格，或者一个句号一个空格；
- 文本末尾为一个句号。

翻译者：一只书虫仔

samples: one, two. one tree. four tree. four four. five four. six five.

samples: one, two. one, tree. four, tree. four, four. five, four. six five.

hint: Time limit: 8 s, Memory limit: 1024 MB.


title: [ICPC2018 WF] Conquer The World

description:
Bwahahahahaha!!! Your nemesis, the dashingly handsome spy Waco Powers, has at last fallen to your secret volcano base's deathtraps (or so you assume, being a little too busy to witness it firsthand). At long last, you are all set to CONQUER THE WORLD!

Nothing will stand in your way! Well, nothing except a minor problem of logistics. Your evil armies have announced that they will not continue carving their relentless path of destruction across the puny nations of the world without being paid. And unfortunately you are running low on cash $-$ a volcano lair has many wonderful qualities, but `reasonably affordable` is not one of them. You have had to pull funds from the travel budget to pay your ungrateful underlings. Now you are not sure how you will actually get your armies into position to CONQUER THE WORLD.

You have a map of the nations of the world and all your available transport routes between them. Each route connects two nations and has a fixed cost per army that uses it. The routes are laid out such that there is exactly one way to travel between any two nations. You know the current position of each of your armies and how many you will need to place permanently in each nation in order to subjugate it. How can you move the armies into place as cheaply as possible so you can CONQUER THE WORLD?

inputFormat:
The first line of input contains an integer $n (1 \le n \le 250 000)$ , the number of nations. This is followed by $n − 1$ lines, each containing three integers $u , v$ , and $c (1 \le u , v \le n , 1 \le c \le 10^{6}),$ indicating that there is a bidirectional route connecting nations $u$ and $v$ , which costs $c$ per army to use.

Finally, another $n$ lines follow, the $i^{th}$ of which contains two non-negative integers $x_{i}$ and $y_{i},$ indicating that there are currently $x_{i}$ armies in nation $i$ , and you need at least $y_{i}$ armies to end up in that nation in the final configuration. The total number of armies (the sum of the $x_{i}$ values) is at least the sum of the $y_{i}$ values, and no more than $10^{6}.$

outputFormat: Display the minimum cost to move your armies such that there are at least $y_{i}$ armies in nation $i$ for all $i$ .

translation:
给定一个 $n$ 点 $n-1$ 边的无向图，每条边 $(u,v)$ 有边权 $c$。

现在第 $i$ 个点有 $x_i$ 的点权，每个点需要 $y_i$ 的点权，所以你可以移动点权到不同的点上。移动一条边上的点 $u$ 的 $k$ 个单位点权到 $v$ 要用 $k \times c$ 的代价。

求满足所有点的需要的最小代价。

$1 \le n \le 2.5 \times 10^5$，$1 \le u,v \le n$，$1 \le c \le 10^6$，$0 \le \sum y_i\le \sum x_i \le 10^6$。

翻译者：一只书虫仔


title: [ICPC2018 WF] Gem Island

description:
Gem Island is a tiny island in the middle of the Pacific Ocean. Until recently, it was known as one of the poorest, but also most peaceful, places on Earth. Today, it is neither poor nor peaceful. What happened?

One sunny morning, not too long ago, all inhabitants of Gem Island woke up to a surprise. That morning, each of them suddenly held one sparkling gem in their hand. The gems had magically appeared overnight. This was cause for much rejoicing $-$ everybody was suddenly rich, they could finally afford all the things they had ever dreamed of, and the name of their island made so much more sense now.

The next morning, one of the inhabitants woke up to another surprise $-$ her gem had magically split into two gems! The same thing happened on each of the following nights, when exactly one of the gems (apparently uniformly at random among all the gems on the island) would split into two.

After a while, the inhabitants of Gem Island possessed a widely varying number of gems. Some had a lot and many had only a few. How come some inhabitants had more gems than others? Did they cheat, were they just lucky, or was something else at work?

The island elders have asked for your help. They want you to determine if the uneven distribution of gems is explained by pure chance. If so, that would greatly reduce tensions on the island.

The island has $n$ inhabitants. You are to determine the gem distribution after $d$ nights of gem splitting. In particular, you are interested in the expected number of gems collectively held by the $r$ people with the largest numbers of gems. More formally, suppose that after $d$ nights the numbers of gems held by the $n$ inhabitants are listed in non-increasing order as $a_{1} \ge a_{2} \ge $ . . . $ \ge a_{n}.$ What is the expected value of $a_{1} + · · · + a_{r}?$

inputFormat: The input consists of a single line containing the three integers $n , d$ , and $r (1 \le n , d \le 500 , 1 \le r \le n)$ , as described in the problem statement above.

outputFormat: Display the expected number of gems that the top $r$ inhabitants hold after $d$ nights, with an absolute or relative error of at most $10^{−6}.$

translation:
有 $n$ 个人，最开始每个人手中有 $1$ 颗绿宝石，每天晚上，会随机选一个绿宝石分裂为两个。

求 $d$ 个晚上后绿宝石数量最多的 $r$ 个人的绿宝石数和的期望值。

$1 \le n,d \le 500$，$1 \le r\le n$。

翻译者：一只书虫仔

hint: Time limit: 3 s, Memory limit: 1024 MB.


title: [ICPC2018 WF] Getting a Jump on Crime

description:
Your friend Robin is a superhero. When you first found out about this, you figured `everybody needs a hobby, and this seems more exciting than stamp collecting,` but now you are really thankful that somebody is doing something about the crime in your hometown.

Every night, Robin patrols the city by jumping from roof to roof and watching what goes on below. Naturally, superheroes need to respond to crises immediately, so Robin asked you for help in figuring out how to get around your hometown quickly.

Your hometown is built on a square grid, where each block is $w \times w$ meters. Each block is filled by a single building. The buildings may have different heights (see Figure E.1) . To get from one building to another (not necessarily adjacent) building, Robin makes a single jump from the center of the roof of the first building to the center of the roof of the second building. Robin cannot change direction while in the air, but can choose the angle at which to lift off.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15693/1.png)

Figure E.1 : Cross-section of buildings corresponding to the first sample input. Buildings are shown in black, and the jump from the roof at $(1 , 1)$ to the roof at $(4 , 1)$ is shown with a green line.

Of course, Robin only wants to perform jumps without colliding with any buildings. Such collisions do little damage to a superhero, but building owners tend to get irritated when someone crashes through their windows. You explain the physics to Robin: `All your jumps are done with the same initial velocity $v$ , which has a horizontal component $v_{d}$ towards the destination and vertical component $v_{h}$ upwards, so $v_{d}^{2} + v_{h}^{2} = v^{2}$ . As you travel, your horizontal velocity stays constant $(v_{d}(t) = v_{d}),$ but your vertical velocity is affected by gravity $(v_{h}(t) = v_{h} − t · g)$ , where $g = 9$ . $80665 m/s^{2}$ in your hometown. Naturally, your cape allows you to ignore the effects of air resistance. This allows you to determine your flight path and $ \cdots `$ at which point you notice that Robin has nodded off $-$ less math, more super-heroing!

So it falls to you: given a layout of the city and the location of Robin's secret hideout, you need to determine which building roofs Robin can reach, and the minimum number of jumps it takes to get to each roof.

Note that if Robin's jump passes over the corner of a building (where four buildings meet), then the jump needs to be higher than all four adjacent buildings.

$ $

inputFormat:
The input starts with a line containing six integers $d_{x}, d_{y}, w , v , ℓ_{x}, ℓ_{y}.$ These represent the size $d_{x} \times d_{y}$ of the city grid $(1 \le d_{x}, d_{y} \le 20)$ in blocks, the width of each building $(1 \le w \le 10^{3})$ in meters, Robin's takeoff velocity $(1 \le v \le 10^{3})$ in meters per second, and the coordinates $(ℓ_{x}, ℓ_{y})$ of Robin's secret hideout $(1 \le ℓ_{x} \le d_{x}, 1 \le ℓ_{y} \le d_{y}).$

The first line is followed by a description of the heights of the buildings in the city grid. The description consists of $d_{y}$ lines, each containing $d_{x}$ non-negative integers. The $j^{th}$ line contains the heights for buildings $(1 , j),(2 , j)$ , . . . $,(d_{x}, j)$ . All heights are given in meters and are at most $10^{3}.$

outputFormat:
Display the minimum number of jumps Robin needs to get from the secret hideout to the roof of each building. If there is no way to reach a building's roof, display $X$ instead of the number of jumps. Display the buildings in the same order as given in the input file, split into $d_{y}$ lines, each containing $d_{x}$ values.

You may assume that changing the height of any building by up to $10^{−6}$ would not change the answers.

translation:
## 题目描述
你的朋友罗宾（Robin）是一位超级英雄。当你第一次发现这个事时，你认为“每个人都需要有爱好，这个看起来比收集邮票有意思多了”，但是现在你十分感谢那些在你的家乡胡作非为的人。

每个晚上， 罗宾（Robin）用在房顶上跳跃的方式巡逻整座城市，并且看下面发生了什么。自然，超级英雄需要立即应对危机，所以罗宾（Robin）寻求你的帮助，帮他找出如何迅速走遍你的家乡。

你的家乡建立在一个方形的格子上，其中每个区块有 $w\times w$ 米。每个区块是一个独立的建筑，建筑有可能有不同的高度,为了从一个建筑到另一个（不一定相邻的）建筑，罗宾（Robin）从第一个房屋屋顶的中间跳到第二个房屋屋顶的中间。不能在空中改变方向，但可以选择起飞的角度。

当然，罗宾（Robin）不想撞到任何一个建筑。一些碰撞很难对超级英雄造成伤害，但是当有人击穿房屋主人的窗户时，他们容易感到生气。你向罗宾（Robin）解释物理学：“你的每次跳都有一个初速度$v$，可以被分解成一个向前的水平分力$v_d$和一个向上的竖直分力$v_h$，且$v_{d}^{2} + v_{h}^{2} = v^{2}$.当你行动时，你的水平分力保持不变$(v_{dt} = v_{d}),$，但是竖直分力受到重力的影响$(v_{h}(t) = v_{h} − t · g)$，设在你的家乡重力加速度$g=9.80665$。自然，你的斗篷可以让你忽略空气阻力的影响。这可以让你确定你的飞行路线和……”这是你注意到罗宾（Robin）已经睡着了-少一点数学，多一点超级英雄！

所以现在轮到你了：已经给出城市的布局和罗宾（Robin）秘密藏身处的位置，你需要确定罗宾（Robin）能到达哪些屋顶并给出最少跳跃次数。

请注意，如果罗宾（Robin）的跳跃经过一栋建筑的角落（四栋建筑交汇的地方），那么跳跃需要比所有四栋相邻建筑都高。

## 输入格式
输入的第一行包含六个整数$d_x$,$d_y$,$w$,$v$,$l_x$,$l_x$.这些代表了 $d_x\times d_y$ 的城市面积（单位：区块）$(1 \le d_{x}, d_{y} \le 20)$，每座建筑的宽度$(1 \le w \le 10^{3})$，罗宾（Robin）的起跳速度$(1 \le v \le 10^{3})$（单位：米每秒），和罗宾（Robin）藏身处的坐标$(1 \le ℓ_{x} \le d_{x}, 1 \le ℓ_{y} \le d_{y}).$。

第一行后面是对城市网格中建筑高度的描述。描述由$d_y$行组成，每个行包含$d_{x}$个非负整数。第j行包含建筑物$(1 , j),(2 , j)$ , . . . $,(d_{x}, j)$ 的高度（单位：米）。高度最高不超过$10^3$米。

## 输出格式
输出罗宾从秘密藏身处跳到每栋建筑屋顶所需的最小跳跃次数。如果无法到达建筑物的屋顶，则显示$X$而不是跳跃次数。按输入文件中给定的顺序显示建筑，分为$d_{y}$行，每行包含$d_{x}$个值。

hint: Time limit: 2 s, Memory limit: 1024 MB.


title: [ICPC2018 WF] Go with the Flow

description:
In typesetting, a `river` is a string of spaces formed by gaps between words that extends down several lines of text. For instance, Figure F.1 shows several examples of rivers highlighted in red (text is intentionally blurred to make the rivers more visible).

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15694/1.png)

Figure F.1 : Examples of rivers in typeset text.

Celebrated river authority Flo Ng wants her new book on rivers of the world to include the longest typographic rivers possible. She plans to set the text in a mono-spaced font (all letters and spaces have equal width) in a left-aligned column of some fixed width, with exactly one space separating words on each line (the text is not aligned on the right). For Flo, a `river` is defined as a sequence of spaces lying in consecutive lines in which the position of each space in the sequence (except the first) differs by at most $1$ from the position of the space in the line above it. Trailing white space cannot appear in a river. Words must be packed as tightly as possible on lines; no words may be split across lines. The line width used must be at least as long as the longest word in the text. For instance, Figure F.2 shows the same text set with two different line widths.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15694/2.png)

Figure F.2 : Longest rivers $( \times )$ for two different line widths.

Given a text, you have been tasked with determining the line width that produces the longest river of spaces for that text.

inputFormat: The first line of input contains an integer $n (2 \le n \le 2 500)$ specifying the number of words in the text. The following lines of input contain the words of text. Each word consists only of lowercase and uppercase letters, and words on the same line are separated by a single space. No word exceeds $80$ characters.

outputFormat: Display the line width for which the input text contains the longest possible river, followed by the length of the longest river. If more than one line width yields this maximum, display the shortest such line width.

translation:
#### 题目描述
在字体排印学中，“川流”是由单词之间的间隙组成的连续几列的空格。如图所示为几个用红色高亮标出的“川流”（文本被有意模糊处理来凸显川流）：

![img](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15694/1.png)

知名川流机构 Flo Ng 希望他在新的关于世界河流的书上出现尽可能长的川流。他会使用一种单一字宽的字体（每个字母和空格都具有相同的宽度）且左对齐，单词之间恰用一个空格分隔。对 Flo 来说，一条“川流”指的是连续几行里的空格，且相邻空格在行里出现的位置的距离不超过 $1$。川流不能包含末尾的空格。每行的单词都必须尽可能地紧凑，但不能有单词被拆到两行里。行宽至少不能短于文本中最长的一个单词。下图是同一个文本使用不同行宽的一个例子。

![img](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15694/2.png)

给定文本，你需要求出一个行宽使得该文本最长的川流尽可能长。

#### 输入格式
第一行有一个整数 $n(2≤n≤2500)$ 表示文本的单词个数。接下来几行为该文本的单词。每个单词都只包含大写和小写字母，且长度不超过 $80$ 个字符。

#### 输出格式
输出两个整数，分别表示使得文本出现最长的川流的行宽以及川流的长度。如果有多个行款达到川流长度的最大值，输出最小的行宽。

samples:
21
The Yangtze is the third longest
river in Asia and the longest in
the world to flow
entirely in one country

samples:
25
When two or more rivers meet at
a confluence other than the sea
the resulting merged river takes
the name of one of those rivers

hint: Time limit: 12 s, Memory limit: 1024 MB.


title: [ICPC2018 WF] Panda Preserve

description:
Last month, Sichuan province secured funding to establish the Great Panda National Park, a natural preserve for a population of more than $1 800$ giant pandas. The park will be surrounded by a polygonal fence. In order for researchers to track the pandas, wireless receivers will be placed at each vertex of the enclosing polygon and each animal will be outfitted with a wireless transmitter. Each wireless receiver will cover a circular area centered at the location of the receiver, and all receivers will have the same range. Naturally, receivers with smaller range are cheaper, so your goal is to determine the smallest possible range that suffices to cover the entire park.

As an example, Figure G.1 shows the park described by the first sample input. Notice that a wireless range of $35$ does not suffice (a) , while the optimal range of $50$ covers the entire park (b) .

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15695/1.png)

Figure G.1 : Illustration of Sample Input $1$ .

inputFormat: The first line of the input contains an integer $n (3 \le n \le 2 000)$ specifying the number of vertices of the polygon bounding the park. This is followed by $n$ lines, each containing two integers $x$ and $y (|x|, |y| \le 10^{4})$ that give the coordinates $(x , y)$ of the vertices of the polygon in counter-clockwise order. The polygon is simple; that is, its vertices are distinct and no two edges of the polygon intersect or touch, except that consecutive edges touch at their common vertex.

outputFormat: Display the minimum wireless range that suffices to cover the park, with an absolute or relative error of at most $10^{−6}.$

translation: 给定一个 $n$ 个点的不自交的多边形（不一定是凸多边形），求最小的圆半径 $r$ 使得在每个顶点画一个半径为 $r$ 的圆，这些圆的并覆盖了整个多边形。$n \le 2000$，绝对误差或相对误差不超过 $10^{-6}$。

hint: Time limit: 10 s, Memory limit: 1024 MB.


title: [ICPC2018 WF] Single Cut of Failure

description:
The Intrusion and Crime Prevention Company (ICPC) builds intrusion detection systems for homes and businesses. The International Collegiate Programming Contest (in a strange coincidence also known as ICPC) is considering hiring the company to secure the room that contains the problem set for next year's World Finals.

The contest staff wants to prevent the intrusion attempts that were made in past years, such as rappelling down the outside of the building to enter through a window, crawling through air ducts, impersonating Bill Poucher, and the creative use of an attack submarine. For that reason, the problems will be stored in a room that has a single door and no other exits.

ICPC (the company) proposes to install sensors on the four sides of the door, where pairs of sensors are connected by wires. If somebody opens the door, any connected sensor pair will detect this and cause an alarm to sound.

The system has one design flaw, however. An intruder might cut the wires before opening the door. To assess the security of the system, you need to determine the minimum number of line segments that cut all wires. Figure H.1 shows two configurations of wires on the door (corresponding to the two sample inputs), and minimum-size cuts that intersect all wires.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15696/1.png)

Figure H.1 : Illustrations of Sample Inputs $1$ and $2$ .

inputFormat: The input starts with a line containing three integers $n , w$ , and $h$ , which represent the number of wires installed $(1 \le n \le 10^{6})$ and the dimensions of the door $(1 \le w , h \le 10^{8}).$ This is followed by $n$ lines, each describing a wire placement. Each of these lines contains four integers $x_{1}, y_{1}, x_{2},$ and $y_{2} (0 \le x_{1}, x_{2} \le w , 0 \le y_{1}, y_{2} \le h)$ , meaning that a wire goes from $(x_{1}, y_{1})$ to $(x_{2}, y_{2}).$ Each wire connects different sides of the door. No wire is anchored to any of the four corners of the door. All locations in the input are distinct.

outputFormat:
Display a minimum-size set of straight line cuts that intersect all wires. First, display the number of cuts needed. Then display the cuts, one per line in the format $x_{1} y_{1} x_{2} y_{2}$ for the cut between $(x_{1}, y_{1})$ and $(x_{2}, y_{2}).$ Each cut has to start and end on different sides of the door. Cuts cannot start or end closer than $10^{−6}$ to any wire anchor location or any corner of the door.

Cuts may be displayed in any order. The start and end locations of each cut may be displayed in either order. If there are multiple sets of cuts with the same minimum size, display any of them.

translation:
#### 题目描述

入侵与犯罪预防公司 (the Intrusion and Crime Prevection Company, 简称 ICPC) 为家庭和商业公司建立了入侵检测系统。国际大学生编程竞赛 (the International Collegiate Programming Contest, 碰巧也简称 ICPC) 正在考虑雇佣该公司来确保下一年 World Finals 的题目文件的储藏房间的安全。

比赛工作人员希望防止过去几年发生的入侵尝试，例如在大楼的外部垂直速降然后从窗户进入，从排气管道爬进来，冒充 Bill Poucher （译者注：某知名计算机科学教授，ACM-ICPC 的执行董事），以及创造性地使用攻击潜艇。正因如此，题目文件将被储藏在仅有一扇门而没有任何其他出入口的房间里。

ICPC （指公司）建议在门的四边安装传感器，每对传感器由电线连接。如果有人打开了门，任何连接的一对传感器将检测到这个动作并引起警报声。

然而这个系统存在一个设计缺陷。入侵者可以在开门之前剪断这些电线。为了评估这个系统的安全性，你需要使用最少的线段剪断所有电线。下图展示了两种具有不同电线分布的门（对应于两个样例）以及最少的与所有电线相交的线段。

![图](http://173.82.2.245/share/eh-1.png)

#### 输入格式

第一行三个整数 $n, w, h$ 分别表示电线的数量 ($1 \le n \le 10^6$) 以及门的尺寸 ($1 \le w, h \le 10^8$) 。接下来 $n$ 行，每行描述一个电线的位置。这些行中每行包含四个整数 $x_1, y_1, x_2, y_2$ ($0 \le x_1, x_2 \le w, 0 \le y_1, y_2 \le h$) 表示该电线从 $(x_1, y_1)$ 连接到 $(x_2, y_2)$ 。每根电线连接门的不同的两边。没有电线连接到门的四个角落。输入的所有位置都是两两不同的。

#### 输出格式

输出最少的一组线段与所有电线有交。首先第一行输出线段的数量。然后逐行输出线段，每行以 $x_1$ $y_1$ $x_2$ $y_2$ 的格式给出一个从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的线段。每条线段的两个端点必须在门的不同的两边。线段的端点与任何电线端点及门的四个角落的距离不能小于 $10^{-6}$ 。

线段可以以任意顺序输出。线段的两个端点也可以以任意顺序输出。如果有多种可行的解，输出任意一组解即可。

译者注：线段的端点坐标可以是满足限制的任意**实数**。

hint: Time limit: 6 s, Memory limit: 1024 MB.


title: [ICPC2018 WF] Triangles

description:
For your trip to Beijing, you have brought plenty of puzzle books, many of them containing challenges like the following: how many triangles can be found in Figure I.1 ?

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15697/1.png)

Figure I.1 : Illustration of Sample Input $2$ .

While these puzzles keep your interest for a while, you quickly get bored with them and instead start thinking about how you might solve them algorithmically. Who knows, maybe a problem like that will actually be used in this year's contest. Well, guess what? Today is your lucky day!

inputFormat: The first line of input contains two integers $r$ and $c (1 \le r \le 3 000 , 1 \le c \le 6 000)$ , specifying the picture size, where $r$ is the number of rows of vertices and $c$ is the number of columns. Following this are 2r $− 1$ lines, each of them having at most 2c $− 1$ characters. Odd lines contain grid vertices (represented as lowercase $x$ characters) and zero or more horizontal edges, while even lines contain zero or more diagonal edges. Specifically, picture lines with numbers 4k $+ 1$ have vertices in positions $1 , 5 , 9 , 13$ , . . . while lines with numbers 4k $+ 3$ have vertices in positions $3 , 7 , 11 , 15$ , . . . . All possible vertices are represented in the input (for example, see how Figure I.1 is represented in Sample Input $2$) . Horizontal edges connecting neighboring vertices are represented by three dashes. Diagonal edges are represented by a single forward slash $(‘/')$ or backslash $(‘\')$ character. The edge characters will be placed exactly between the corresponding vertices. All other characters will be space characters. Note that if any input line could contain trailing whitespace, that whitespace may be omitted.

outputFormat: Display the number of triangles (of any size) formed by grid edges in the input picture.

translation:
**简要题意：** 输入 $r$ 行顶点，每行有 $c$ 列，顶点用 $x$ 表示，每个顶点用水平边（`-`）和对角边（用 `/` 和 `\` 表示）**精确连接**。总共 $2 r - 1$ 行，每行最多有 $2 c - 1$ 个字符，除上述字符外均为空白字符；行末可能存在可忽略的空格。你需要输出所输入的图中由网格边构成了多少个三角形（无论大小）。配图为样例 $2$。

对于所有数据，$1 \le r \le 3000$，$1 \le c \le 6000$。


title: [ICPC2018 WF] Uncrossed Knight’s Tour

description:
A well-known puzzle is to `tour` all the squares of an $8 \times 8$ chessboard using a knight, which is a piece that can move only by jumping one square in one direction and two squares in an orthogonal direction. The knight must visit every square of the chessboard, without repeats, and then return to its starting square. There are many ways to do this, and the chessboard size is manageable, so it is a reasonable puzzle for a human to solve.

However, you have access to a computer, and some coding skills! So, we will give you a harder version of this problem on a rectangular $m \times n$ chessboard with an additional constraint: the knight may never cross its own path. If you imagine its path consisting of straight line segments connecting the centers of squares it jumps between, these segments must form a simple polygon; that is, no two segments intersect or touch, except that consecutive segments touch at their common end point. This constraint makes it impossible to visit every square, so instead you must maximize the number of squares the knight visits. We keep the constraint that the knight must return to its starting square. Figure J.1 shows an optimal solution for the first sample input, a $6 \times 6$ board.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15698/1.png)

Figure J.1 : An optimal solution for a $6 \times 6$ board.

inputFormat: The input consists of a single line containing two integers $m (1 \le m \le 8)$ and $n (1 \le n \le 10^{15}),$ giving the dimensions of the rectangular chessboard.

outputFormat: Display the largest number of squares that a knight can visit in a tour on an $m \times n$ chessboard that does not cross its path. If no such tour exists, display $0$ .

translation:
### 题目描述

马在 $m$ $\times$ $n$ 大小的矩形棋盘上跳跃（走日字）。求从棋盘上一点开始，在保证【性质】的情况下，它最多经过几个格子（包括起点，且终点不算），可以回到初始点？

【性质】：想象马的路径由直线段组成，这些直线段连接着它所跳跃的正方形的中心（如图），这些直线段必须形成一个简单的多边形。也就是说，没有两个线段相交或接触，除非连续线段在其公共端点处接触。

### 输入格式

一行，两个正整数 $m$ $(1 \le m \le 8)$ 和 $n$ $(1 \le n \le 10^{15})$。

### 输出格式

一行，马最多经过的格子数。
若没有这样的路径，输出 $0$ 。


title: [ICPC2018 WF] Wireless is the New Fiber

description:
A new type of unbounded-bandwidth wireless communication has just been tested and proved to be a suitable replacement for the existing, fiber-based communications network, which is struggling to keep up with traffic growth. You have been charged with deciding the layout of the new communications network. The current communications network consists of a set of nodes (which route messages), and links of fiber, each of which connects two different nodes. For each pair of nodes, there exists at least one way (but possibly more, for bandwidth purposes) to travel along the fiber between the two.

The new communications network will not have any fiber. Instead, it will have wireless links, each connecting two nodes. These links have unbounded bandwidth but are expensive, so it has been decided that as few of these links will be built as possible to provide connectivity; for each pair of nodes there should be exactly one way to travel between them along the wireless links. Moreover, you discovered that the nodes have each been built with a particular number of connections in mind. For each node, if it will be connected to a different number of links than it is today, it will have to be reorganized, and that is costly.

Your task is to design the new network so that it has precisely one path between each pair of nodes while minimizing the number of nodes that do not have the same number of connections as in the original network. Figure K.1 shows the original network and a solution for Sample Input $1$ .

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15699/1.png)

Figure K.1 : Illustration of Sample Input $1$ .

inputFormat: The input begins with a line containing two integers $n (2 \le n \le 10^{4})$ and $m (1 \le m \le 10^{5}),$ denoting the number of nodes and the number of fiber links in the existing network. The nodes are numbered from $0$ to $n − 1$ . Each of the next $m$ lines contains two distinct integers $a_{i}$ and $b_{i},$ denoting the fact that the $i^{th}$ fiber link connects nodes numbered $a_{i}$ and $b_{i}.$ It is guaranteed that for each pair of nodes there exists at least one path connecting the two nodes. Any pair of nodes may have more than one fiber link connecting them.

outputFormat: Display the smallest number of nodes for which the number of connected links needs to change. Starting on the next line, display a system of connections in the same format as the input. That is, display a line containing the number of nodes (this will be the same as in the input) and the number of wireless links, and then on subsequent lines descriptions of the links. If more than one layout is possible, any valid layout will be accepted.

translation: 给你一张 $n$ 个点 $m$ 条边的无向连通图，用这 $n$ 个点重新构建一棵树使得有尽可能少的节点度数发生改变，求一种方案。

hint:
Time limit: 2 s, Memory limit: 1024 MB.

SPJ provider: @[shenyouran](/user/137367).


title: [ICPC2021 WF] Crystal Crosswind

description:
You are part of a scientific team developing a new technique to image crystal structures at the molecular level. The technique involves blowing a very fine wind over the surface of the crystal at various angles to detect boundaries (indicated by molecules that are exposed to the wind). This is repeated with different wind directions and the boundaries observed for each direction are recorded. Your team has already collected the data, but – as is often the case with applied science – now the real work, analysis, must begin.

For a given crystal, you will receive the directions in which wind blew over the surface, and the locations of all boundaries encountered by each of these winds. For a wind blowing in direction ($w_x, w_y$), a boundary is defined as a location ($x, y$) such that a molecule exists at ($x, y$) and no molecule exists at ($x-w_x, y-w_y$). Note that for technical reasons $w_x$ and $w_y$ are not necessarily relatively prime.

The data might not uniquely determine the structure of the crystal. You must find the two unique structures with the minimal and maximal number of molecules consistent with the observations.

For example, in the first sample input, nine different molecules are directly encountered by the given winds. There must be a molecule at location ($3, 3$) because otherwise ($4, 2$) would be a boundary for the third wind. For similar reasons, there must be molecules at ($4, 4$) and ($5, 5$). There cannot be any further molecules as they would result in additional observations for some of the winds.

inputFormat:
The first line of input contains three integers $d_x$, $d_y$, and $k$, where $d_x$ and $d_y$ ($1 \leq d_x, d_y \leq 10^3$) are the maximum dimensions of the crystal structure, and $k (1 \leq k \leq 10)$ is the number of times wind was blown over the crystal.

Each of the remaining $k$ lines specifies the data for one wind. These lines each start with two integers $w_x$ and $w_y$ ($-d_x \leq w_x \leq d_x$ and $-d_y \leq w_y \leq d_y$, but not both zero) denoting the direction of the wind. Then comes an integer $b$ ($0 \leq b \leq 10^5$) giving the number of boundaries encountered by this wind. The line finishes with $b$ distinct pairs of integers $x,y$ ($1 \leq x \leq d_x$ and $1 \leq y \leq d_y$) listing each observed boundary.

You may assume the input is consistent with at least one crystal and that no molecules exist outside the specified dimensions.

outputFormat: Output two textual representations of the crystal structure separated by an empty line. Each structure has $d_y$ rows of $d_x$ characters, with the top-left corner corresponding to location ($1, 1$). The first is the structure with the minimal number of molecules consistent with the observations, the second is the maximal one. Use '#' for a location where a molecule exists and '.' for a location where no molecule exists.

translation:
## 题目描述
你是一个科学团队中的一员，正在开发一种在分子级别上成像晶体结构的新技术。这种技术涉及在晶体表面吹送一股非常微弱的风，并以不同的角度吹送，以便检测边界（通过暴露给风的分子来表示）。这个过程会重复进行，每个吹送方向的边界都会被记录下来。你的团队已经收集到了数据，但是如同大多数应用科学一样，现在真正的工作，即分析工作必须开始。

对于给定的晶体，你将接收到风以不同方向吹送过晶体表面的数据，以及每个风吹过时遇到的所有边界的位置。对于在方向（$w_x, w_y$）吹送的风，边界被定义为位置（$x, y$），使得一个分子位于（$x, y$），并且没有分子位于（$x-w_x, y-w_y$）。请注意，出于技术原因，$w_x$ 和 $w_y$ 不一定互质。

这些数据可能无法唯一确定晶体的结构。你必须找到两个与观测数据一致且分子数最少和最多的晶体结构。

例如，在第一个示例输入中，通过给定的风，出现了9个不同的分子。必须有一个在位置（$3, 3$）处的分子，否则（$4, 2$）将成为第三股风的边界。出于类似的原因，必须在位置（$4, 4$）和（$5, 5$）处有分子。不能再有其他分子，因为它们会导致一些风的附加观测结果。

## 输入格式

输入的第一行包含三个整数 $d_x$、$d_y$ 和 $k$，其中 $d_x$ 和 $d_y$（$1 \leq d_x, d_y \leq 10^3$）是晶体结构的最大尺寸，$k$（$1 \leq k \leq 10$）是风吹过晶体的次数。

接下来的 $k$ 行中，每一行都描述了一次吹风的数据。第一对整数 $w_x$ 和 $w_y$（$-d_x \leq w_x \leq d_x$，$-d_y \leq w_y \leq d_y$，但不能同时为零）表示风的方向。然后是一个整数 $b$（$0 \leq b \leq 10^5$），表示这股风遇到的边界数量。接下来的 $b$ 对不同的整数 $x$、$y$（$1 \leq x \leq d_x$，$1 \leq y \leq d_y$）表示每个观测到的边界。

你可以假设输入数据与至少一个晶体是一致的，并且没有分子存在于指定尺寸范围之外。

## 输出格式

输出两个晶体结构的文本表示，两个结构之间用一个空行分隔。每个结构有 $d_y$ 行，每行有 $d_x$ 个字符，左上角对应位置（$1, 1$）。第一个结构是与观测结果一致的包含最少分子数量的结构，第二个结构是包含最多分子数量的结构。使用 '#' 表示分子存在的位置，使用 '.' 表示分子不存在的位置。


title: [ICPC2021 WF] Dungeon Crawler

description:
Alice and Bob are in charge of testing a new escape room! In this escape room, customers are trapped in a dungeon and have to explore the entire area. The dungeon consists of $n$ rooms connected by exactly $n-1$ corridors. It is possible to travel between any pair of rooms using these corridors.

Two of the dungeon rooms are special. One of these rooms contains a protective idol known as the "helix key´´. A different room contains a nasty "dome trap´´, which prevents the player from moving once activated. Entering the room with the trap before acquiring the key will result in the player being trapped in the dungeon forever. The player cannot start in the same room as the key or the trap.

There are $q$ different scenarios that Alice and Bob wish to examine. In the $i^{th}$ scenario, the player starts in room $s_i$, the key is in room $k_i$, and the trap is in room $t_i$. For each scenario, compute the minimum amount of time needed to explore the entire dungeon without getting trapped.

inputFormat:
The first line of input contains two integers $n$ and $q$, where $n$ ($3 \leq n \leq 2000$) is the number of rooms and $q$ ($1 \leq q \leq 200000$) is the number of scenarios to consider. Rooms are numbered from $1$ to $n$. The next $n-1$ lines each contain three integers $u$, $v$, and $w$ indicating that there is a corridor between rooms $u$ and $v$ ($1 \leq u, v \leq n, u \neq v$) that takes time $w$ ($1 \leq w \leq 10^9$) to traverse.

Then follow $q$ lines: the $i^{th}$ of these lines contains three distinct integers $s_i$, $k_i$, and $t_i$ ($1 \leq s_i, k_i, t_i \leq n$) indicating the room where the player starts, the room with the key, and the room with the trap, respectively.

outputFormat: For each scenario, output the minimum amount of time needed to visit every room at least once. If it is impossible to visit every room at least once, output $\texttt{impossible}$.

translation:
### 题目描述
有一棵 $n$ 个结点的树，边带权。你可以从一个结点通过边移动到一个相邻的结点，花费等同于边权的时间。

其中，有两个特殊结点，一个结点里有钥匙，一个结点里有陷阱。你只有先获得钥匙，才能进入陷阱所在的结点。

现有 $q$ 组询问，在第 $i$ 组询问中，你要从第 $s_i$ 号结点出发，钥匙在第 $k_i$ 号结点，陷阱在第 $t_i$ 号结点。你需要对于每组询问回答遍历整棵树所需的最短时间。题目保证你不会在钥匙所在的结点或者陷阱所在的结点出发。如果不可能遍历整棵树，输出 `impossible`。

### 输入格式
第一行两个整数 $n,q$，含义如题目所述。

接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示有一条连接结点 $u,v$，权值为 $w$ 的边。

接下来 $q$ 行，每行三个整数 $s_i,k_i,t_i$，含义如题目所述。

$3\le n\le 2000$，$1\le q \le 2\times10^5$，$1\le u,v\le n,u\ne v$，$1\le w\le 10^9$，$1\le s_i,k_i,t_i\le n$。

### 输出格式
对于每组询问，输出一行，包含一个整数表示答案，或者输出 `impossible` 表示无解。


title: [ICPC2021 WF] Fair Division

description:
After sailing the Seven Seas and raiding many ships, Cap'n Red and his crew of fellow pirates are finally ready to divide their loot. According to ancient traditions, the crew stands in a circle ordered by a strict pirate hierarchy. Cap'n Red starts by taking a fraction $f$ of the loot and passing the remainder on to the next pirate. That pirate takes the same fraction $f$ of the loot left over by the previous pirate and passes the remainder on to the following pirate. Each pirate behaves in the same way, taking a fraction $f$ of what is left and passing on the rest. The last pirate in the hierarchy passes the remainder on to Cap'n Red, who starts another round of this "fair" division, and so on, indefinitely.

Fortunately, pirates in the 21st century can use a computer to avoid this lengthy process and constant nitpicking when the fraction $f$ does not exactly divide the loot at some step. You have been captured by the pirates and asked to come up with a suitable fraction $f$. As an incentive, Cap'n Red has promised to leave you alive if you succeed.

The fraction $f$ needs to be a rational number strictly between $0$ and $1$. It is not necessary that $f$ exactly divides the loot remaining at any step of the round-robin process described above. However, the total loot that would be assigned to each pirate by carrying out this process infinitely needs to be an integer.

inputFormat: The input contains one line with two integers $n$ and $m$, where $n$ ($6 \leq n \leq 10^6$) is the number of pirates including Cap'n Red and $m$ ($1 \leq m \leq 10^{18}$) is the total value of their loot.

outputFormat: Output one line with two positive integers $p$ and $q$, where $f = \frac{p}{q}$ as specified above. If there are multiple suitable fractions, choose one with the smallest $q$. Among multiple suitable fractions with the same smallest $q$ choose the one with the smallest $p$. If there is no suitable fraction, output $\texttt{impossible}$ instead and hope for mercy.

translation:
### 题目描述
$n$ 个人按如下的方式分 $m$ 块钱：先指定一个分数 $f$，$n$ 个人围成一圈，第一个人先拿走总钱数的 $f$，把剩下的钱给第二个人，然后第二个人拿走剩余钱数的 $f$，把剩下的钱交给第三个人...每一个人都从剩余的钱中拿走剩余钱数的 $f$，然后把钱交给下一个人。这种操作可以无限进行下去。

现在给定 $n,m$，你需要构造 $f=\dfrac{p}{q}$，使得 $0<f<1$，并且在分钱无限进行下去之后，最终每个人拿到的钱都是整数。如果有多解，你构造的解需要在 $q$ 尽可能小的情况下 $p$ 尽可能小。如果无解，输出 `impossible`。

$6\le n\le 10^6$，$1\le m\le 10^{18}$。

### 输入格式

仅一行两个整数 $n,m$，含义如题目所述。
### 输出格式
如果有解，输出一行两个整数 $p,q$，分别是你构造的分数 $f$ 的分子和分母。

如果无解，输出 `impossible`。


title: [ICPC2021 WF] Guardians of the Gallery

description:
Your local art gallery is about to host an exciting new exhibition of sculptures by world-renowned artists, and the gallery expects to attract thousands of visitors. Unfortunately, the exhibition might also attract the wrong kind of visitors, namely burglars who intend to steal the works of art. In the past, the gallery directors did not worry much about this problem, since their permanent collection is, to be honest, not really worth stealing.

The gallery consists of rooms, and each sculpture in the new exhibition will be placed in a different room. Each room has a security guard and an alarm to monitor the artwork. When an alarm sounds, the guard will run (without leaving the room) from their post to a position where they can see the sculpture directly. This is to check whether the sculpture has in fact been stolen, or whether this is yet another false alarm.

To figure out where to best station the security guard, the gallery directors would like to know how long it takes for the guard to see a given sculpture. They hope that you can help!

Every room is on a single floor, and the layout of the walls can be approximated by a simple polygon. The locations of the guard and the sculpture are distinct points strictly inside the polygon. The sculpture is circular, with a negligibly small (but positive) radius. To verify that the sculpture is still present, the guard needs to be able to see at least half of it.

Figure D.1 illustrates two examples. In each case, the guard starts at the blue square on the left, and the sculpture is located at the red circle on the right. The dotted blue line shows the optimal path for the guard to move. Once the guard reaches the location marked by the green diamond, half of the sculpture can be seen.

![](https://cdn.luogu.com.cn/upload/image_hosting/ugrzp1ry.png)

inputFormat: The first line of input contains an integer $n$ ($3 \leq n \leq 100$), the number of vertices that describe the polygon. This is followed by $n$ lines each containing two integers $x$ and $y$ ($0 \leq x,y \leq 1000$), giving the coordinates of the polygon vertices in counterclockwise order. The next line contains two integers $x_g$ and $y_g$, which specify the location of the guard. Finally, the last line contains two integers $x_s$ and $y_s$, which specify the location of the center of the sculpture. The polygon is simple, that is, its vertices are distinct and no two edges of the polygon intersect or touch, other than consecutive edges which touch at their common vertex. In addition, no two consecutive edges are collinear.

outputFormat: Output the minimum distance that the guard has to move to be able to see at least half the sculpture. Your answer must have an absolute or relative error of at most $10^{-6}$.

translation:
#### 简要题意
给定封闭的 $n$ 边形不透明墙壁和其中两个点 $A, B$. 其中，$B$ 是一个半径充分小但大于 $0$ 的透明圆的圆心, 墙壁厚度可视为 $0$. 求所有能直接观察到 $\odot B$ 的至少一半的位置中, 与点 $A$ 距离的最小值.

#### 输入格式
第一行, 一个整数 $n$.

随后 $n$ 行, 每行两个整数 $x_i, y_i$, 依次表示其顶点的坐标。

随后一行, 两个整数 $x_A, y_A$, 表示点 $A$ 的坐标.

最后一行, 两个整数 $x_B, y_B$, 表示圆心 $B$ 的坐标.

#### 输出格式
一行，一个实数，表示最小距离。与标准答案误差不超过 $10^{-6}$ 即可判为正确。


title: [ICPC2021 WF] Hand of the Free Marked

description:
![](https://cdn.luogu.com.cn/upload/image_hosting/kdojyok4.png)

Example placement of cards for $k = 5$

There is a fairly well-known mentalism trick known as the Fitch Cheney trick. From a deck of $n$ playing cards, $k$ are selected uniformly at random and given to an assistant while the magician is out of the room. The assistant places $k-1$ of the selected cards on a table, face up, and the single remaining card face down. The cards are placed in a single row with the face-down card at the end (see the picture for an example). The magician enters the room, looks at the cards on the table, and announces what the $k^{th}$ card is, although its face is hidden. The trick is typically done with $n=52$ and $k=5$.

The assistant uses two ways of passing information to the magician. First, they can pick which one of the $k$ cards to keep hidden. Second, they can rearrange the other $k-1$ cards in a specific way. For the case $n=52$ and $k=5$ both techniques are needed, since there are only $24$ ways of rearranging four cards, which is not enough to reliably signal the fifth card. It is an interesting exercise to come up with a simple, easy-to-remember strategy for executing this trick, but right now you have another concern.

You were planning to perform this trick today, but just now you have learned that the deck has more cards than you expected. The trick may be impossible! In desperation, you have decided to cheat a little. You have $m$ distinguishable ways of marking the backs of the playing cards. You have marked the backs of all $n$ cards, allowing you to narrow down the possibilities for the $k^{th}$ card. For example, if there are $6$ cards marked with a particular method, and you see that the back of the $k^{th}$ card is marked with that method, you know it must be one of those $6$ cards.

Determine the probability that you will successfully guess the $k^{th}$ card, assuming you and the assistant execute an optimal (but likely very complicated!) strategy.

inputFormat: The input contains one line with several integers. The first integer gives $k$ ($2 \leq k \leq 10$), the number of cards that will be selected. The second integer gives $m$ ($1 \leq m \leq 10$), the number of ways of marking the cards. The line is completed by $m$ positive integers, giving the number of cards marked with each distinct method. The sum of these $m$ integers is $n$ ($k \leq n \leq 10^9$), which is the size of the deck.

outputFormat: Output the highest possible probability of guessing the $k^{th}$ card correctly, accurate up to an absolute error of $10^{-9}$.

translation:
#### 简要题意
两个人 $A, B$ 玩一个游戏。规则如下 :

$A$ 有 $n$ 张互不相同的牌. 它们的**背面**有 $m$ 种不同的样式, 第 $i$ 种牌有 $a_i$ 张. 二人都对这套牌非常了解. 保证 $\sum\limits^{m}_{i=1}{a_i} = n$.

$B$ 在 $A$ 不在场的情况下从中随机抽出 $k$ 张, 然后选择一张牌倒置在桌面上. 然后 $B$ 可以以任意顺序重新排列其他牌并在桌面上依次排开, 并将倒置的牌放在序列的末尾. $A$ 和 $B$ 可以在游戏之前约定通过其他牌的排列顺序传递的信息.

随后 $A$ 需要根据桌面上牌的排列和倒置牌的背面说出倒置的牌具体是哪一张. 双方的目标都是使 $A$ 说出正确的牌。

现在给定 $m, a_i$ 和 $k$, 求二人均采取最佳策略的情况下, $A$ 的成功率是多少.

#### 输入格式
输入仅一行, 首先是两个整数 $k, m$, 然后是 $m$ 个整数 $a_i$.

#### 输出格式
一行, 一个实数, 表示答案. 答案与标准答案的差不超过 $10^{-9}$ 即判为正确.