title: [ICPC2014 WF] Maze Reduction

description:
Jay runs a small carnival that has various rides and attractions. Unfortunately, times are tough. A recent roller coaster accident, flooding in the restrooms, and an unfortunate clown incident have given Jay’s carnival a bad reputation with the public. With fewer paying customers and reduced revenue, he will need to cut some costs to stay in business.

One of the biggest carnival attractions is a large, confusing maze. It consists of a variety of circular rooms connected by narrow, twisting corridors. Visitors love getting lost in it and trying to map it out. It has come to Jay’s attention that some of the rooms might be effectively identical to each other. If that’s the case, he will be able to reduce its size without anyone noticing.

Two rooms $A$ and $B$ are effectively identical if, when you are dropped into either room $A$ or $B$ (and you know the map of the maze), you cannot tell whether you began in $A$ or $B$ just by exploring the maze. The corridor exits are evenly spaced around each room, and you cannot mark or leave anything in a room (in particular, you cannot tell whether you have previously visited it). The only identifying feature that rooms have is their number of exits. Corridors are also twisty enough to be indistinguishable from each other, but when you enter a room you know which corridor you came from, so you can navigate a little by using the order they appear around the room.

Jay has appealed to the Association for Carnival Mazery for help. That’s you! Write a program to determine all the sets of effectively identical rooms in the maze.

inputFormat: The input consists of a single test case. The first line contains an integer $n$, the number of rooms in the maze ($1 \leq n \leq 100$). Rooms are numbered from 1 to $n$. Following this are $n$ lines, describing each room in order. Each line consists of an integer $k$, indicating that this room has $k$ corridors ($0 \leq k < 100$), and then $k$ distinct integers listing the rooms each corridor connects to (in clockwise order, from an arbitrary starting point). Rooms do not connect to themselves.

outputFormat: Display one line for each maximal set of effectively identical rooms (ignoring sets of size 1) containing the room numbers in the set in increasing order. Order the sets by their smallest room numbers. If there are no such sets, display none instead.

translation:
Jay经营着一家小型游乐场，其中有各种游乐设施和景点。不幸的是，由于顾客和收入的锐减，他将需要削减成本以维持业务。

一个大型迷宫是最大的景点之一，它由不同的圆形房间组成。这些房间通过狭窄且扭曲的走廊相连，而某些游客喜欢迷失在迷宫中并试图将其绘制出来。Jay已经注意到，有些房间可能一模一样。如果出现这样的情况，他就能减小迷宫的尺寸而不会被任何人发现。

当您进入AA或是BB房间（并且您知道迷宫的地图）时，两个房间AA和BB是相同的，那么您仅通过探索迷宫就无法分辨是从AA还是BB开始行动。走廊出口在每个房间周围均等分布，您不能在房间内标记或留下任何东西（您无法判断是否进入过该房间）。房间唯一的标识是出口数量。走廊很曲折，彼此之间无法区分，但是当您进入一个房间时，您会知道您来自哪个走廊，因此您可以通过它们在房间周围出现的顺序来指引方向。

Jay向你寻求帮助，请编写程序以找出迷宫中所有相同房间的集合。

Translated by EndlIa

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

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


title: [ICPC2014 WF] Messenger

type: P

description:
Misha needs to send packages to his friend Nadia. Both of them often travel across Russia, which is very large. So they decide to hire a messenger. Since the cost of the messenger service depends on the time it takes to deliver the package, they need your help to optimize a little bit.

Assume Misha and Nadia move on a two-dimensional plane, each visiting a sequence of places and moving along straight line segments from place to place. Your task is to find the shortest possible delivery time given their two paths.

Misha hands the package to the messenger at some point along his path. The messenger moves without delay along a straight line from the pick-up to intercept Nadia, who is traveling along her path. Misha, Nadia and the messenger move with a constant speed of $1$ distance unit per time unit. The delivery time is the time between Misha handing over the package and Nadia receiving it.

inputFormat:
The input consists of a single test case. The test case contains two path descriptions, the first for Misha and the second for Nadia. Each path description starts with a line containing an integer $n$, the number of places visited ($2 \leq n \leq 50\, 000$). This is followed by $n$ lines, each with two integers $x_ i$ and $y_ i$ specifying the coordinates of a place ($0 \leq x_ i, y_ i \leq 30\, 000$). Coordinates of the places are listed in the order in which they are to be visited, and successive places do not have the same coordinates.

Misha and Nadia start their journeys at the same time, visiting the places along their paths without stopping. The length of each path is at most $10^6$. The package must be picked up at the latest when Misha reaches his final place and it must be delivered at the latest when Nadia reaches her final place.

outputFormat: Display the minimal time needed for delivery. Give the answer with an absolute error of at most $10^{-3}$ or a relative error of at most $10^{-5}$. If the package cannot be delivered, display impossible instead.

translation:
题目描述：
平面上有两个移动的点 A,B，其中 A 想要向 B 发送一条信息。两个点会同时出发，各自沿着一个折线移动到终点为止。A 会在移动的途中发送一条信息，这条信息可以视作一个点 C，它会沿一条射线匀速运动，当 C 与 B 重合时，B 即可收到该信息。

A,B,C 的移动速度都是 1 单位长度每秒，A 最晚在它到达终点时发出信息，B 最晚需要在它到达终点时收到信息。令 $t_A$ 代表发送信息的时间，$t_B$ 代表接收信息的时间，那么你需要最小化 $t_B-t_A$ 的值。特别地，如果 B 无论如何都无法收到信息，你需要输出 `impossible`。

输入格式：

第一行包含一个整数 $n$，代表 A 经过折线的点数；
下面 $n$ 行，每行输入两个整数 $x_i,y_i$，依次描述 A 所走折线的点。
下面一行包含一个整数 $m$，B 过折线的点数；
下面 $m$ 行，每行输入两个整数 $u_i,v_i$，描述 B 所走折线。

输出格式：

一行，输出一个实数，代表答案。若无法满足，则输出`impossible`。

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

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


title: [ICPC2014 WF] Metal Processing Plant

description:
Yulia works for a metal processing plant in Ekaterinburg. This plant processes ores mined in the Ural mountains, extracting precious metals such as chalcopyrite, platinum and gold from the ores. Every month the plant receives $n$ shipments of unprocessed ore. Yulia needs to partition these shipments into two groups based on their similarity. Then, each group is sent to one of two ore processing buildings of the plant.

To perform this partitioning, Yulia first calculates a numeric distance $d(i, j)$ for each pair of shipments $1 \le i \le n$ and $1 \le j \le n$, where the smaller the distance, the more similar the shipments $i$ and $j$ are. For a subset $S \subseteq \{ 1, \ldots , n\} $ of shipments, she then defines the disparity $D$ of $S$ as the maximum distance between a pair of shipments in the subset, that is,

$$ D(S) = \max _{i, j \in S} d(i, j). $$

Yulia then partitions the shipments into two subsets $A$ and $B$ in such a way that the sum of their disparities $D(A) + D(B)$ is minimized. Your task is to help her find this partitioning.

inputFormat: The input consists of a single test case. The first line contains an integer $n$ ($1 \le n \le 200$) indicating the number of shipments. The following $n - 1$ lines contain the distances $d(i,j)$. The $i^{th}$ of these lines contains $n - i$ integers and the $j^{th}$ integer of that line gives the value of $d(i, i+j)$. The distances are symmetric, so $d(j, i) = d(i, j)$, and the distance of a shipment to itself is $0$. All distances are integers between $0$ and $10^9$ (inclusive).

outputFormat: Display the minimum possible sum of disparities for partitioning the shipments into two groups.

translation:
**题目描述**

尤利娅在叶卡捷琳堡的一家金属加工厂工作。该工厂在乌拉尔山脉提取矿石中的铜、铂和金。工厂每月收到 $n$ 批未经处理的矿石。尤利娅需要对这些货物进行分割为两组。然后它们会分别被送到工厂的两个冶矿塔。

首先，尤利娅对每对货物 $i,j(1\leq i,j\leq n)$ 给出一个$d_{i,j}$，对于子集 $S$，$D(S)$ 定义为 $\max\limits_{(i,j\in S)}\{d_{(i,j)}\}$。

然后，尤利娅将货物分成 $A$ 和 $B$ 两部分，使 $D(A)+D(B)$ 最小。请你帮助她找到划分方法。

**输入格式**

输入包括多组数据。
对于每组测试数据：
第一行包含一个整数 $n(1\leq n\leq 200)$，表示发货数量。接下来 $n-1$ 行每行有 $n-i$ 个数，第 $j$ 个数表示 $d_{i,i+j}$。且 $d_{j,i}=d_{i,j},d_{i,i}=0$。

**输入格式**

对于每组测试数据，输出 $D(A)+D(B)$ 的最小值。


title: [ICPC2014 WF] Pachinko

description:
You have been hired by Addictive Coin Machines to help design the next hit in their line of eye-catching, coin-guzzling, just-one-more-try Pachinko machines for casinos around the world.

Playing a Pachinko machine involves launching balls into a rectangular grid filled with pegs, obstacles, and targets. The ball bounces around the grid until it eventually hits one of the targets. The player earns a certain number of points depending on which target is hit.

The grid pattern for the next Pachinko machine has already been designed, but point values for the targets have not been assigned. These must be set so that like all casino machines, the machine is profitable but not too profitable. Thus it is important to figure out the probability of a ball hitting any particular target. That’s your job!

For simplicity, the grid is modeled as a tall rectangle filled with mostly-open spaces (each represented by ‘.’), impassable obstacles (each represented by ‘X’), and targets (each represented by ‘T’).

A ball is launched randomly with uniform probability into one of the mostly-open spaces on the top row of the grid. From that point on, collisions with pegs cause the ball to randomly bounce up, down, left, or right, with various given probabilities. For simplicity, assume these probabilities are the same for every space in the grid. If the ball bounces into an obstacle or attempts to move off the grid, it won’t actually move from its current space. When the ball moves into a target it is removed from play.

You can safely assume that the average number of spaces visited by a ball before hitting a target will not exceed $10^{9}$. It would not make for a very enjoyable game if the ball just bounces forever!

For each target, calculate the probability that it is the one hit by a launched ball.

inputFormat:
The input consists of a single test case. The first line contains integers $w$ and $h$, which are the width and height of the Pachinko grid ($1 \leq w \leq 20$ and $2 \leq h \leq 10\, 000$). The next line contains four non-negative integers $u$, $d$, $l$, and $r$, which sum to 100 and are the percentage probabilities of the ball bouncing up, down, left, or right from any open space.

Each of the next $h$ lines contains $w$ characters, each of which is ‘.’, ‘X’, or ‘T’. These lines describe the Pachinko grid. The first line, which describes the top row of the grid, contains at least one ‘.’ and no ‘T’s.

outputFormat: Display one line for each ‘T’ in the grid, in order from top to bottom, breaking ties left to right. For each target, display the probability that a launched ball will hit it. Give the answer with an absolute error of at most $10^{-6}$.

translation:
**题目描述**

有一个宽度为 $w$ 高度为 $h$ 的方格纸， $ w \times h$ 的格子中，有一些是空的，有一些是洞，有一些是障碍物。从第一行的空的格子中随机选一个放置一个球，向上下左右移动的概率比为 $p_u : p_d : p_l : p_r$（满足 $p_u + p_d + p_l + p_r = 100$），不能移动到有障碍物的格子上。对于每个洞，输出落入该洞的概率。$w \le 20, h \le 10000$。保证第一行没有洞。

**输入格式**

第一行两个整数表示 $w, h$ 。

第二行四个整数表示 $p_u, p_d, p_l, p_r$ 。

接下来有一个 $h$ 行 $w$ 的字符矩阵，其中 `.` 表示空，`X` 表示障碍物，`T` 表示洞。

**输出格式**

若干行，每一行一个整数，按照矩阵从上到下，从左到右的顺序，输出每个洞的答案。绝对误差不超过 $10^{-6}$ 即为正确。

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

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


title: [ICPC2014 WF] Sensor Network

description:
A wireless sensor network consists of autonomous sensors scattered in an environment where they monitor conditions such as temperature, sound, and pressure.

Samantha is a researcher working on the Amazon Carbon-dioxide Measurement (ACM) project. In this project, a wireless sensor network in the Amazon rainforest gathers environmental information. The Amazon rainforest stores an amount of carbon equivalent to a decade of global fossil fuel emissions, and it plays a crucial role in the world’s oxygen-transfer processes. Because of the huge size of this forest, changes in the forest affect not only the local environment but also global climate by altering wind and ocean current patterns. The goal of the ACM project is to help scientists better understand earth’s complex ecosystems and the impact of human activities.

Samantha has an important hypothesis and to test her hypothesis, she needs to find a subset of sensors in which each pair of sensors can communicate directly with each other. A sensor can communicate directly with any other sensor having distance at most $d$ from it. In order for her experiments to be as accurate as possible, Samantha wants to choose as many sensors as possible.

As one does not simply walk into the Amazon, Samantha cannot add new sensors or move those that are currently in place. So given the current locations of the sensors, she needs your help to find the largest subset satisfying her criteria. For simplicity, represent the location of each sensor as a point in a two-dimensional plane with the distance between two points being the usual Euclidean distance.

inputFormat: The input consists of a single test case. The first line contains two integers $n$ and $d$ ($1 \le n \le 100$ and $1 \le d \le 10\, 000$), where $n$ is the number of sensors available and $d$ is the maximum distance between sensors that can communicate directly. Sensors are numbered $1$ to $n$. Each of the next $n$ lines contains two integers $x$ and $y$ ($-10\, 000\le x, y \le 10\, 000$) indicating the sensor coordinates, starting with the first sensor.

outputFormat: Display a maximum subset of sensors in which each pair of sensors can communicate directly. The first line of output should be the size of the subset. The second line of output should be the (one-based) indices of the sensors in the subset. If there are multiple such subsets, any one of them will be accepted.

translation:
无线传感器网络由分散在环境中的自主传感器组成，它们监控温度、声音和压力等条件。

萨曼莎是亚马逊二氧化碳测量 (Amazon Carbon-dioxide Measurement, ACM) 项目的研究员。在这个项目中，亚马逊雨林的无线传感器网络收集环境信息。亚马逊雨林储存了相当于十年全球化石燃料排放量的碳，它在世界的氧气转移过程中扮演着至关重要的角色。由于这片森林面积巨大，森林的变化不仅会影响当地环境，还会通过改变风和洋流模式来影响全球气候。ACM 项目的目标是帮助科学家更好地了解地球复杂的生态系统和人类活动的影响。

萨曼莎有一个重要的猜想，为了验证她的猜想，她需要找到传感器的一个子集，在这些传感器中，每对传感器都可以直接相互通信。传感器可以与距离它不超过 $d$ 的任何其他传感器直接通信。为了让她的实验尽可能准确，萨曼莎希望选择尽可能多的传感器。

因为人们不能简单地走进亚马逊，萨曼莎不能添加新的传感器，也不能移动那些目前设置好的传感器。因此，给出传感器目前的位置，她需要你的帮助来找到满足她标准的最大子集。为简单起见，每个传感器的位置被表示为二维平面中的一个点，两点之间的距离为通常的欧几里德距离。

#### 输入

第一行两个整数 $n$ 和 $d$ ($1\le n\le 100$, $1\le d\le 10\,000$)，其中 $n$ 表示传感器的个数，$d$ 表示传感器能直接通信的最大距离。传感器从 $1$ 到 $n$ 编号。接下来的 $n$ 行，每行两个整数 $x$, $y$ ($-10\,000\le x,y\le 10\,000$)，表示每个传感器的坐标，从第一个传感器开始。

#### 输出

输出满足要求的一个最大子集。第一行输出子集的大小。第二行输出子集中传感器的编号 (从 $1$ 开始编号)。如果有多个满足要求的最大子集，输出任意一个均可。


title: [ICPC2014 WF] skiing

description:
As you know, the ACM ICPC is not the only major sporting event taking place in Russia this year. Several months ago, the 2014 Winter Olympics were held in Sochi, which is about 3 000 km from Ekaterinburg.

In an increasing number of sports, it is not only the ability of the athletes that determines who wins a competition but also their equipment. For example in downhill skiing, having the latest ski technology enables athletes to increase their speeds and improve their turning ability.

You have been hired to determine the effect of the latest ski technology on the ability of skiers to navigate a downhill course. The course contains several target locations, and the skier wants to pass over as many of them as possible. Naturally, the better the ski technology, the easier it will be to do this.

For simplicity, use a two-dimensional coordinate system where the skier starts at position (0,0) and where “downhill” corresponds to the direction of the positive $y$-axis.

Assume the $y$-component of the athlete’s velocity is a constant $v_ y$. The athlete can change speed laterally (in the $x$-direction), but the skiing equipment limits this to a maximal lateral acceleration $a_{max}$. The skier starts with a lateral velocity of 0.

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

   Figure 1: Downhill ski path passing over three targets

In Figure 1 (which corresponds to the first sample input), the optimal path passes over three out of four possible targets. If $a_{max}$ were smaller, then the skier might be able to pass over only two or fewer of the targets.

inputFormat:
The input contains a single test case. The first line contains three integers $n$, $v_ y$, and $a_{max}$ ($0 \leq n \leq 250$, $0 < v_ y \leq 10^5$ and $0 \leq a_{max} \leq 10^7$), where $n$ is the number of targets, $v_ y$ is the $y$-component of the skier’s velocity, and $a_{max}$ is the maximum lateral acceleration. Here $v_ y$ is given in meters per hour and $a_{max}$ in meters per hour squared.

Following this are $n$ lines, each containing two integers $x_ i$ and $y_ i$ ($-10^5 \leq x_ i, y_ i \leq 10^5$). These give the coordinates of each target to be visited on the course. All coordinates are given in meters. Targets are numbered 1, 2, ..., $n$ in the order they are given.

outputFormat:
Display the maximal-length sequence of targets that the athlete could pass over on the course in a single run. Display the targets in the order they are visited. If there are multiple maximal-length sequences, display only the lexicographically first one. (So the sequence 2 15 would come before the sequence 10 15.) If the athlete cannot pass over any targets, print Cannot visit any targets instead.

To ensure floating-point stability, you may assume the answer will not change if $a_{max}$ is perturbed by up to 0.1.

translation:
**题目描述**

滑雪运动员进行的一次训练可以看作平面上一条从 $(0, 0)$ 出发的曲线，这条曲线在 $y$ 轴正方向上的**速度**是 $v_y$，由于装备限制，在 $x$ 轴上的**加速度**不得超过 $a_{max}$。滑雪运动员在 $x$ 轴上的速度从 $0$ 开始。

在这一次训练中，滑雪运动员需要经过所有 $n$ 个目标点 $(x_i, y_i)$ 中尽可能多的目标点，现在他希望你通过控制他每一时刻的加速度，实现这个目标。

**输入格式**

第一行三个整数 $n, v_y, a_{max}$ 分别表示目标点数，$y$ 轴速度（米每秒）以及 $x$ 轴加速度上限（米每二次方秒）。

接下来 $n$ 行每行两个整数 $x, y$ 表示目标点的横坐标（米）以及纵坐标（米）。

**输出格式**

按照目标点被经过的顺序输出最长的目标点序列。若有多个可能的答案，输出字典序最小的。若运动员不能经过任意一个目标点，输出 `Cannot visit any targets`。

为了避免浮点误差，你可以假设对 $a_max$ 进行不超过 $0.1$ 的扰动的情况下，答案不变。

**数据范围**

$0\le n\le 250, 0\le v_y\le 10^5
, 0\le a_{max}\le 10^7
, −10^5\le x, y\le 10^5$
, 目标点编号从 1 开始。

~~一句话の题意：输入一些数，输出一些数（或字符串），使输出符合要求。~~


title: [ICPC2014 WF] Surveillance

description: The International Corporation for Protection and Control (ICPC) develops efficient technology for, well, protection and control. Naturally, they are keen to have their own headquarters protected and controlled. Viewed from above, the headquarters building has the shape of a convex polygon. There are several suitable places around it where cameras can be installed to monitor the building. Each camera covers a certain range of the polygon sides (building walls), depending on its position. ICPC wants to minimize the number of cameras needed to cover the whole building.

inputFormat: The input consists of a single test case. Its first line contains two integers $n$ and $k$ ($3 \le n \le 10^6$ and $1 \le k \le 10^6$), where $n$ is the number of walls and $k$ is the number of possible places for installing cameras. Each of the remaining $k$ lines contains two integers $a_ i$ and $b_ i$ ($1 \le a_ i, b_ i \le n$). These integers specify which walls a camera at the $i^{th}$ place would cover. If $a_ i \le b_ i$ then the camera covers each wall $j$ such that $a_ i \le j \le b_ i$. If $a_ i > b_ i$ then the camera covers each wall $j$ such that $a_ i \le j \le n$ or $1 \le j \le b_ i$.

outputFormat: Display the minimal number of cameras that suffice to cover each wall of the building. The ranges covered by two cameras may overlap. If the building cannot be covered, display impossible instead.

translation:
### 题目描述
给定一个长度为 $n$ 的环，有 $k$ 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。
### 输入格式
第一行两个整数 $n$，$k$。
接下来 $k$ 行，每行两个整数表示一个区域。
### 输出格式
若环不可能被完全覆盖，输出 `impossible`；否则输出一个整数，表示最少的区域数量。

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

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


title: [ICPC2014 WF] Wire Crossing

description:
Moore’s Law states that the number of transistors on a chip will double every two years. Amazingly, this law has held true for over half a century. Whenever current technology no longer allowed more growth, researchers have come up with new manufacturing technologies to pack circuits even denser. In the near future, this might mean that chips are constructed in three dimensions instead two. But for this problem, two dimensions will be enough.

A problem common to all two-dimensional hardware design (for example chips, graphics cards, motherboards, and so on) is wire placement. Whenever wires are routed on the hardware, it is problematic if they have to cross each other. When a crossing occurs special gadgets have to be used to allow two electrical wires to pass over each other, and this makes manufacturing more expensive.

Our problem is the following: you are given a hardware design with several wires already in place (all of them straight line segments). You are also given the start and end points for a new wire connection to be added. You will have to determine the minimum number of existing wires that have to be crossed in order to connect the start and end points. This connection need not be a straight line. The only requirement is that it cannot cross at a point where two or more wires already meet or intersect.

  ![](https://vj.z180.cn/df2653f5a1b23d354dbe2e33d6438ea6?v=1602904232)

   Figure 1: First sample input

Figure 1 shows the first sample input. Eight existing wires form five squares. The start and end points of the new connection are in the leftmost and rightmost squares, respectively. The black dashed line shows that a direct connection would cross four wires, whereas the optimal solution crosses only two wires (the curved blue line).

inputFormat: The input consists of a single test case. The first line contains five integers $m, x_0, y_0, x_1, y_1$, which are the number of pre-existing wires ($m \le 100$) and the start and end points that need to be connected. This is followed by $m$ lines, each containing four integers $x_ a, y_ a, x_ b, y_ b$ describing an existing wire of non-zero length from $(x_ a, y_ a)$ to $(x_ b,y_ b)$. The absolute value of each input coordinate is less than $10^5$. Each pair of wires has at most one point in common, that is, wires do not overlap. The start and end points for the new wire do not lie on a pre-existing wire.

outputFormat: Display the minimum number of wires that have to be crossed to connect the start and end points.

translation:
#### 题意简述
给定出发点，终止点和平面上的 $m$ 条线段，线段用两个端点表示，

求从出发点到终止点的连线(形状任意)最少要与线段相交多少次，多次经过一条线段要多次计数。

数据保证任意两条线段最多只有一个交点，注意连线不能经过交点，且线段可能是斜线。

坐标的绝对值不超过 $10^5$


title: [ICPC2015 WF] Amalgamated Artichokes

description:
 ![](https://vj.z180.cn/751a8fdd9863b69e86176e87e1fd5b20?v=1600415919)

Fatima Cynara is an analyst at Amalgamated Artichokes (AA). As with any company, AA has had some very good times as well as some bad ones. Fatima does trending analysis of the stock prices for AA, and she wants to determine the largest decline in stock prices over various time spans. For example, if over a span of time the stock prices were $19$, $12$, $13$, $11$, $20$ and $14$, then the largest decline would be $8$ between the first and fourth price. If the last price had been $10$ instead of $14$, then the largest decline would have been $10$ between the last two prices.

Fatima has done some previous analyses and has found that the stock price over any period of time can be modelled reasonably accurately with the following equation:

$$ \operatorname {price}(k) = p \cdot (\sin (a \cdot k+b) + \cos (c \cdot k+d) + 2) $$

where $p$, $a$, $b$, $c$ and $d$ are constants. Fatima would like you to write a program to determine the largest price decline over a given sequence of prices. Figure 1 illustrates the price function for Sample Input 1. You have to consider the prices only for integer values of $k$.

  ![](https://vj.z180.cn/800605356b7337600d5163d2e5d7aab4?v=1600415919)

   Figure 1: Sample Input 1. The largest decline occurs from the fourth to the seventh price.

inputFormat: The input consists of a single line containing $6$ integers $p$ ($1 \le p \le 1\, 000$), $a$, $b$, $c$, $d$ ($0 \le a, b, c, d \le 1\, 000$) and $n$ ($1 \le n \le 10^6$). The first $5$ integers are described above. The sequence of stock prices to consider is $\operatorname {price(1)}, \operatorname {price(2)}, \ldots , \operatorname {price}(n)$.

outputFormat: Display the maximum decline in the stock prices. If there is no decline, display the number $0$. Your output should have an absolute or relative error of at most $10^{-6}$.

translation:
**题目背景**

法蒂玛是针对联合洋蓟果业公司 (Amalgamated Artichokes , AA) 的股票分析员。和其他的公司一样，联合洋蓟果业公司有的时候行情较好，有的时候不太行。法蒂玛对联合洋蓟果业公司的股票价格做了跟踪分析，她想确定不同时间段内股价最大跌幅是多少。比如如果一段时间内股价分别为19元，12元，13元，11元，20元，14元，则最大的跌幅为第一天和第四天之间的8。如果最后一天的价格不是14元而是10元，则最大跌幅为最后两天股价之间的10元。

法蒂玛做了些前期的分析，发现一段时间的股价可以建模精确合理地表示为以下方程式：
$$
price(k)=p⋅(sin(a⋅k+b)+cos(c⋅k+d)+2)
$$
其中$p,a,b,c,d$均为常数。法蒂玛想要你写个程序确定给定价格序列上的最大股价跌幅。

图1说明了第一组样例的价格函数，你只能考虑时间为整数$k$时的价格。

对于第一组样例，最大股价跌幅出现在第四天和第七天之间。

**一句话题意**

对于给定序列，求差值最大的逆序对

**输入格式**

输入共一行，包含六个整数$p (1 \le p \le 1000), a, b, c, d ( 0 \le a, b, c, d \le 1\, 000)$ 和$ n (1 \le n \le 10^6).$

前五个整数意义如题目所述，给定序列长度为n。

**输出格式**

输出股价最大跌幅，如果没有股价下跌则输出0。

输出最多和标准答案有$10^{-6}$的相对或绝对误差。

**说明/提示**

时间限制: 5000 ms

空间限制: 1048576 kB.

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

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

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


title: [ICPC2015 WF] Asteroids

description:
The year is 2115. The asteroid communication relay system was set up a decade ago by the Asteroid Communication Ministry. It is running fine except for one small problem – there are too many asteroids! The smaller ones not only keep interfering with the signals from the relay stations but they are also a danger to all the maintenance aircrafts that fly between the stations. These small asteroids must be destroyed! The Interplanetary Coalition to Prevent Catastrophes (ICPC) has been charged with removing these dangerous asteroids and has hired an elite team of hot-shot pilots for the job. Han Duo is the captain of this team of asteroid destroyers. Armed with his missiles, Han flies through the asteroid belt blowing up any asteroid that the ICPC deems a nuisance.

The ICPC is having some unfortunate budgetary problems. One result of this is that Han and his team do not have as many missiles as they would like, so they cannot blow up all the troublesome asteroids. But the asteroids are small and the missiles are powerful. So if two asteroids are near each other and line up properly, it is possible to take out both with a single missile.

Han’s screen displays asteroids as non-rotating two-dimensional simple convex polygons, each of which moves at a fixed velocity. He has decided that the best time to hit two asteroids is when the overlap of the two polygons is at a maximum. For example, Figure 1, which illustrates Sample Input 1, shows two asteroids and snapshots of their subsequent positions at 1-second intervals. The two asteroids start touching after $3$ seconds and the maximum overlap area occurs between $4$ and $5$ seconds.

  ![](https://vj.z180.cn/c0ee84911e97a539823bc119cb23e0d7?v=1603764626)

   Figure 1: Sample Input 1. Two asteroids with crossing paths.

Calculating when the maximum overlap occurs for two asteroids requires a bit of programming, but unfortunately Han slept through most of his coding classes at the flight academy. This is where you come in.

inputFormat: The input consists of two asteroid specifications. Each has the form $n\; x_{1}\; y_{1}\; x_{2}\; y_{2}\; \ldots \; x_{n}\; y_{n}\; v_{x}\; v_{y}$ where $n$ $(3 \le n \le 10)$ is the number of vertices, each $x_{i}, y_{i}$ ($-10\, 000 \le x_{i}, y_{i} \le 10\, 000$) are the coordinates of a vertex of the asteroid on Han’s screen given in clockwise order, and $v_{x}, v_{y}$ ($-100 \le v_{x}, v_{y} \le 100$) are the $x$ and $y$ velocities (in units/second) of the asteroid. The $x_{i}$, $y_{i}$ values specify the location of each asteroid at time $t=0$, and the polygons do not intersect or touch at this time. The maximum length of any side of an asteroid is $500$. All numbers in the input are integers.

outputFormat: Display the time in seconds when the two polygons have maximum intersection, using the earliest such time if there is more than one. If the two polygons never overlap but touch each other, treat it as an intersection where the common area is zero and display the earliest such time. If the polygons never overlap or touch, display never instead. You should consider positive times only. Your output should have an absolute or relative error of at most $10^{-3}$.

translation:
## 题目背景
今年是2115年。小行星通信中继系统是十年前由小行星通信部建立的。有一个小问题——小行星太多，它们很危险！比较小的小行星不仅不断干扰中继站的信号，而且对在中继站之间飞行的所有维修飞机也是一种危险。这些小行星必须被摧毁！防止危险的星际联盟（ICPC）已被下达移除这些危险的小行星的指令，并请了一支精英团队来完成这项工作。Han Duo 是这个小行星驱逐舰小组的队长。Han Duo 带着他的导弹飞过小行星带，炸毁了 ICPC 认为的令人讨厌的任何小行星。

ICPC 没那么多钱。后果是 Han Duo 和他的团队没有他们想要的那么多导弹，因此他们无法炸毁所有麻烦的小行星。但是小行星很小，导弹也很强大。因此，如果两颗小行星彼此靠近并正确排列，就有可能用一枚导弹将两者都摧毁。

Han Duo 的屏幕将小行星显示为非旋转的二维简单凸多边形，每个多边形都以固定速度移动。他认为撞击两颗小行星的最佳时间是两个多边形的重叠达到最大值时。例如，图1演示了样例输入1，显示了两颗小行星及其后续的位置，间隔1秒。两颗小行星在33秒后开始接触，最大重叠区域出现在44到55秒之间。

图1：样例输入1。两颗有交叉路径的小行星。

计算两颗小行星的最大重叠时间需要计算机来完成，但不幸的是，Han Duo 在飞行学院的大部分程序设计课中都在睡大觉。现在把这个任务交由你。

## 输入格式

输入包括两个小行星规格。每个形式为 $n, x_1, y_1 ,x_2，y_2  $ $… $ $x_n ,y_n ,v_x, v_y$ 其中 $n$$(3$$\le n \le10)$  是顶点的数量，每个 $x_i,y_i(-10000$$\leq x_i,y_i \leq$$1000)$ 在屏幕上按顺时针顺序给出的小行星顶点的坐标，$v_x，v_y(-100 \le v_x,v_y \le 100)$ 是小行星的$x$和$y$速度（单位/秒）$x,y$ 值代表 $t=0$ 时每个小行星的位置，此时多边形不相交或接触。小行星任意一侧的最大长度为 $500$。输入中的所有数字都是整数。

## 输出格式

以秒为单位输出两个多边形具有最大相交的时间，如果存在多个多边形，则使用最早的时间。如果两个多边形从不重叠，而是彼此接触，则将其视为公共面积为零的交点，并输出最早的时间。如果多边形从不重叠或接触，则输出“never”。你应该只考虑确定的时候。输出的绝对或相对的误差应不超过$10^{-3}$。

## 说明/提示

时间限制：2000毫秒，内存限制：1048576 kB。

2015年国际大学生编程大赛（ACM-ICPC）世界总决赛

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

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

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


title: [ICPC2015 WF] Catering

description:
 ![](https://vj.z180.cn/c3c77c406a120e9e6c632a7a3d0cfeac?v=1603344926)

Paul owns a catering company and business is booming. The company has $k$ catering teams, each in charge of one set of catering equipment. Every week, the company accepts $n$ catering requests for various events. For every request, they send a catering team with their equipment to the event location. The team delivers the food, sets up the equipment, and instructs the host on how to use the equipment and serve the food. After the event, the host is responsible for returning the equipment back to Paul’s company.

Unfortunately, in some weeks the number of catering teams is less than the number of requests, so some teams may have to be used for more than one event. In these cases, the company cannot wait for the host to return the equipment and must keep the team on-site to move the equipment to another location. The company has an accurate estimate of the cost to move a set of equipment from any location to any other location. Given these costs, Paul wants to prepare an Advance Catering Map to service the requests while minimizing the total moving cost of equipment (including the cost of the first move), even if that means not using all the available teams. Paul needs your help to write a program to accomplish this task. The requests are sorted in ascending order of their event times and they are chosen in such a way that for any $i < j$, there is enough time to transport the equipment used in the $i^{th}$ request to the location of the $j^{th}$ request.

inputFormat: The first line of input contains two integers $n$ ($1 \le n \le 100$) and $k$ ($1 \le k \le 100$) which are the number of requests and the number of catering teams, respectively. Following that are $n$ lines, where the $i^{th}$ line contains $n-i+1$ integers between $0$ and $1\, 000\, 000$ inclusive. The $j^{th}$ number in the $i^{th}$ line is the cost of moving a set of equipment from location $i$ to location $i+j$. The company is at location $1$ and the $n$ requests are at locations $2$ to $n+1$.

outputFormat: Display the minimum moving cost to service all requests. (This amount does not include the cost of moving the equipment back to the catering company.)

translation:
有一家装备出租公司收到了按照时间顺序排列的 $n$ 个请求。

这家公司有 $k$ 个搬运工。每个搬运工可以搬着一套装备**按时间顺序**去满足一些请求。

一个搬运工从第 $i$ 个请求的位置把东西搬到第 $j$ 个请求的位置需要一些费用。公司的编号是 1，请求的编号是 $2\sim n+1$。所有搬运工必须从公司出发。

求满足所有请求所需的最小搬运费用.

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

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


title: [ICPC2015 WF] Cutting Cheese

description:
 ![](https://vj.z180.cn/5f637f1053193ffad543787cd8bc5b2a?v=1601501213)

Of course you have all heard of the International Cheese Processing Company. Their machine for cutting a piece of cheese into slices of exactly the same thickness is a classic. Recently they produced a machine able to cut a spherical cheese (such as Edam) into slices – no, not all of the same thickness, but all of the same weight! But new challenges lie ahead: cutting Swiss cheese.

Swiss cheese such as Emmentaler has holes in it, and the holes may have different sizes. A slice with holes contains less cheese and has a lower weight than a slice without holes. So here is the challenge: cut a cheese with holes in it into slices of equal weight.

By smart sonar techniques (the same techniques used to scan unborn babies and oil fields), it is possible to locate the holes in the cheese up to micrometer precision. For the present problem you may assume that the holes are perfect spheres.

Each uncut block has size $100 \times 100 \times 100$ where each dimension is measured in millimeters. Your task is to cut it into $s$ slices of equal weight. The slices will be $100$ mm wide and $100$ mm high, and your job is to determine the thickness of each slice.

inputFormat:
The first line of the input contains two integers $n$ and $s$, where $0 \leq n \leq 10\, 000$ is the number of holes in the cheese, and $1 \le s \le 100$ is the number of slices to cut. The next $n$ lines each contain four positive integers $r$, $x$, $y$, and $z$ that describe a hole, where $r$ is the radius and $x$, $y$, and $z$ are the coordinates of the center, all in micrometers.

The cheese block occupies the points $(x,y,z)$ where $0 \le x,y,z \le 100\, 000$, except for the points that are part of some hole. The cuts are made perpendicular to the $z$ axis.

You may assume that holes do not overlap but may touch, and that the holes are fully contained in the cheese but may touch its boundary.

outputFormat: Display the $s$ slice thicknesses in millimeters, starting from the end of the cheese with $z=0$. Your output should have an absolute or relative error of at most $10^{-6}$.

translation:
# 题目背景

当然，你们都已经听说过国际奶酪加工公司。他们将一块奶酪切成完全相同厚度的薄片的机器是一个经典。最近，他们生产了一种能将球形奶酪（比如荷兰球形干酪）切成薄片的机器——不，不是所有的厚度都一样，而是所有的质量都一样！但是新的挑战摆在面前：切瑞士奶酪。

瑞士奶酪，比如瑞士多孔奶酪，在其中有很多洞，并且这些洞大小可能不同。一片有空洞的奶酪比一片没有洞的奶酪含量更少，质量更轻。所以这是一个挑战：将一块有空洞的奶酪切成质量相同的薄片。

通过智能声呐技术（与过去常常探测未出生的婴儿和油田的技术一样），可以将空洞定位精确到微米级别。对于目前的问题，你可以认为这些洞是完美球体。

每一个未切割的奶酪块尺寸为 $100\times100\times100$，其中单位为毫米。你的任务是把它切成 $s$ 个质量相等的薄片。这些薄片宽度和高度都应当是 $100\operatorname{mm}$，然后你的工作是求出每个薄片的厚度。

## 简化题意

有一个 $100 \text{mm} \times 100 \text{mm} \times 100 \text{mm}$ 的质地均匀的正方体，垂直于 $z$ 轴的切成 $s$ 个薄片，使得每一片质量相等。每一薄片宽度和高度都是 $100 \text{mm}$，请从奶酪底端 $z=0$ 开始依次输出每一片的厚度。

# 输入格式

输入的第一行包含两个整数 $n$ 和 $s$，其中 $0 \leq n \leq 10000$ 表示奶酪中洞的个数，然后 $1 \le s \le 100$ 表示要切割的薄片数。接下来的 $n$ 行分别包含四个描述空洞的正整数 $r,x,y,z$，其中 $r$ 表示半径，$x$、$y$ 和 $z$ 表示空洞中心坐标，都以微米为单位。

奶酪的圆心 $(x,y,z)$ 中 $0 \le x,y,z \le 100000$，除了某个孔的部分点（即某个孔的部分点可能超出该范围，但是圆心一定在这之内）。刀切的方向垂直于 $z$ 轴。

你可以认为这些洞没有重叠但是可能接触，并且这些孔完全包含在奶酪里，但可能接触奶酪的边界。

# 输出格式

输出保留 $9$ 位小数。从奶酪底端 $z=0$ 开始，以毫米为单位输出 $s$ 个薄片厚度。相对误差或绝对误差不能超过 $10^{-6}$。

# 说明/提示

时间限制：$3000 \text{ms}$，空间限制：$1048576\text{kB}$。

2015年国际大学生编程大赛（ACM-ICPC）世界总决赛

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

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


title: [ICPC2015 WF] Evolution in Parallel

description:
It is 2178, and alien life has been discovered on a distant planet. There seems to be only one species on the planet and they do not reproduce as animals on Earth do. Even more amazing, the genetic makeup of every single organism is identical!

The genetic makeup of each organism is a single sequence of nucleotides. The nucleotides come in three types, denoted by ‘A’ (Adenine), ‘C’ (Cytosine), and ‘M’ (Muamine). According to one hypothesis, evolution on this planet occurs when a new nucleotide is inserted somewhere into the genetic sequence of an existing organism. If this change is evolutionarily advantageous, then organisms with the new sequence quickly replace ones with the old sequence.

It was originally thought that the current species evolved this way from a single, very simple organism with a single-nucleotide genetic sequence, by way of mutations as described above. However, fossil evidence suggests that this might not have been the case. Right now, the research team you are working with is trying to validate the concept of “parallel evolution” – that there might actually have been two evolutionary paths evolving in the fashion described above, and eventually both paths evolved to the single species present on the planet today. Your task is to verify whether the parallel evolution hypothesis is consistent with the genetic material found in the fossil samples gathered by your team.

inputFormat:
The input begins with a number $n$ ($1\le n\le 4\, 000$) denoting the number of nucleotide sequences found in the fossils. The second line describes the nucleotide sequence of the species currently living on the planet. Each of the next $n$ lines describes one nucleotide sequence found in the fossils.

Each nucleotide sequence consists of a string of at least one but no more than $4\, 000$ letters. The strings contain only upper-case letters A, C, and M. All the nucleotide sequences, including that of the currently live species, are distinct.

outputFormat:
Display an example of how the nucleotide sequences in the fossil record participate in two evolutionary paths. The example should begin with one line containing two integers $s_1$ and $s_2$, the number of nucleotide sequences in the fossil record that participate in the first path and second path, respectively. This should be followed by $s_1$ lines containing the sequences attributed to the first path, in chronological order (from the earliest), and then $s_2$ lines containing the sequences attributed to the second path, also in chronological order. If there are multiple examples, display any one of them. If it is possible that a sequence could appear in the genetic history of both species, your example should assign it to exactly one of the evolutionary paths.

If it is impossible for all the fossil material to come from two evolutionary paths, display the word impossible.

translation:
### 题目背景

公元2178年，人类在一颗遥远的行星上发现了外星生命。但是似乎这颗行星上只有单一物种而且它们并不像地球上的动物一样繁殖。更神奇的是，每个生物的基因构成是完全相同的！

每个生物的基因构成是单一核苷酸序列。在它们基因中有三种核苷酸，表示为‘A’  (腺嘌呤，Adenine), ‘C’ (胞嘧啶，Cytosine), and ‘M’ (膜嘌呤，Muamine)。根据某种假说，在这颗星球上只有某个新的核苷酸插入现存的生物基因序列某处时才会出现进化。如果这个改变是对进化有利的，这个带有新基因序列的生物会迅速取代没有变异的旧生物。

我们起初认为这种生物是从基因序列只含有单一核苷酸的生物经过多次上述的变异进化而来。然而化石证据表明可能并不是一直是这种情况。目前，与你协作的科研团队正在尝试证实“平行进化”的概念。“平行进化”指可能事实上有两条如同上述的进化路径，最终他们都进化成了这颗行星如今的物种。你的任务是证实平行进化假说是否与你的团队在化石中发现的遗传物质样本一致。

( TRANSLATED by  [@MolotovM](https://www.luogu.com.cn/user/99461))

### 题目含义

给定1个字符串，n个字符串，求不多于两个的字符串的子串包含其他所有字符串，且这不多于两个的字符串都是给定字符串的子串。

### 输入格式

第一行输入为一个整数$n (1\le n\le 4\, 000)$，表示化石中发现的遗传物质样本数量

第二行输入为给定字符串表示当前生物的基因序列

接下来n行，每行输入一个字符串，表示化石中发现的遗传物质样本

每个遗传物质样本由不超过4000个字母构成，且只包含大写字母A,C和M。

包括当前生物基因序列的所有基因序列都是独特的。

### 输出格式

输出每个化石中的遗传物质样本是怎样参与两条进化路径的。

第一行包含两个整数$s_1,s_2$为两条进化路径的化石数量。

接下来$s_1$行每行包含一个字符串表示第一条进化路径中的遗传物质样本

接下来$s_2$行每行包含一个字符串表示第二条进化路径中的遗传物质样本

样本按年代顺序输出(从最早的开始)，如果一个样本可以同时出现在两条进化路径中，你需要表明它具体参与了哪种进化。

如果不可能满足有不多于两条进化路径，输出"impossible"。

### 时空限制

时间限制: 2000 ms

空间限制: 1048576 kB

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

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


title: [ICPC2015 WF] Keyboarding

description:
How many keystrokes are necessary to type a text message? You may think that it is equal to the number of characters in the text, but this is correct only if one keystroke generates one character. With pocket-size devices, the possibilities for typing text are often limited. Some devices provide only a few buttons, significantly fewer than the number of letters in the alphabet. For such devices, several strokes may be needed to type a single character. One mechanism to deal with these limitations is a virtual keyboard displayed on a screen, with a cursor that can be moved from key to key to select characters. Four arrow buttons control the movement of the cursor, and when the cursor is positioned over an appropriate key, pressing the fifth button selects the corresponding character and appends it to the end of the text. To terminate the text, the user must navigate to and select the Enter key. This provides users with an arbitrary set of characters and enables them to type text of any length with only five hardware buttons.

In this problem, you are given a virtual keyboard layout and your task is to determine the minimal number of strokes needed to type a given text, where pressing any of the five hardware buttons constitutes a stroke. The keys are arranged in a rectangular grid, such that each virtual key occupies one or more connected unit squares of the grid. The cursor starts in the upper left corner of the keyboard and moves in the four cardinal directions, in such a way that it always skips to the next unit square in that direction that belongs to a different key. If there is no such unit square, the cursor does not move.

  ![](https://vj.z180.cn/4393d80e3f068a496c9b906fdca621d9?v=1603457188)

   Figure 1: Sample Input 1. An example virtual keyboard and hardware buttons.

Figure 1, illustrating Sample Input 1, shows a possible way to type CONTEST using 30 strokes on an example virtual keyboard. The red dots represent the virtual keys where the select button was pressed.

inputFormat: The first line of the input contains two integers $r$ and $c$ ($1 \leq r, c \leq 50$), giving the number of rows and columns of the virtual keyboard grid. The virtual keyboard is specified in the next $r$ lines, each of which contains $c$ characters. The possible values of these characters are uppercase letters, digits, a dash, and an asterisk (representing Enter). There is only one key corresponding to any given character. Each key is made up of one or more grid squares, which will always form a connected region. The last line of the input contains the text to be typed. This text is a non-empty string of at most $10\, 000$ of the available characters other than the asterisk.

outputFormat: Display the minimal number of strokes necessary to type the whole text, including the Enter key at the end. It is guaranteed that the text can be typed.

translation:
给定一个 $r$ 行 $c$ 列的在电视上的「虚拟键盘」，通过「上，下，左，右，选择」共 $5$ 个控制键，你可以移动电视屏幕上的光标来打印文本。一开始，光标在键盘的左上角，每次按方向键，光标总是跳到下一个在该方向上与当前位置不同的字符，若不存在则不移动。每次按选择键，则将光标所在位置的字符打印出来。
现在求打印给定文本（要在结尾打印换行符）的最少按键次数。

samples:
4 7
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST

samples:
5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015

samples:
2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ


title: [ICPC2015 WF] Pipe Stream

description:
 ![](https://vj.z180.cn/ba87a214c6b94e2e93a88f7b226c2064?v=1602042036)

Your hometown has hired some contractors – including you! – to manage its municipal pipe network. They built the network, at great expense, to supply Flubber to every home in town. Unfortunately, nobody has found a use for Flubber yet, but never mind. It was a Flubber network or a fire department, and honestly, houses burn down so rarely, a fire department hardly seems necessary.

In the possible event that somebody somewhere decides they want some Flubber, they would like to know how quickly it will flow through the pipes. Measuring its rate of flow is your job.

You have access to one of the pipes connected to the network. The pipe is $l$ meters long, and you can start the flow of Flubber through this pipe at a time of your choosing. You know that it flows with a constant real-valued speed, which is at least $v_1$ meters/second and at most $v_2$ meters/second. You want to estimate this speed with an absolute error of at most $\frac{t}{2}$ meters/second.

Unfortunately, the pipe is opaque, so the only thing you can do is to knock on the pipe at any point along its length, that is, in the closed real-valued range $[0,l]$. Listening to the sound of the knock will tell you whether or not the Flubber has reached that point. You are not infinitely fast. Your first knock must be at least $s$ seconds after starting the flow, and there must be at least $s$ seconds between knocks.

Determine a strategy that will require the fewest knocks, in the worst case, to estimate how fast the Flubber is flowing. Note that in some cases the desired estimation might be impossible (for example, if the Flubber reaches the end of the pipe too quickly).

inputFormat: The input consists of multiple test cases. The first line of input contains an integer $c$ ($1 \leq c \leq 100$), the number of test cases. Each of the next $c$ lines describes one test case. Each test case contains the five integers $l$, $v_1$, $v_2$, $t$ and $s$ ($1 \leq l, v_1, v_2, t, s \leq 10^9$ and $v_1 < v_2$), which are described above.

outputFormat: For each test case, display the minimal number of knocks required to estimate the flow speed in the worst case. If it might be impossible to measure the flow speed accurately enough, display impossible instead.

translation:
### **题目描述**

你的家乡雇了一些承包商——包括你！—— 来管理市政管道网络。他们花费巨资建设了该网络，以向城镇中的每个家庭供应弹力胶。不幸的是，目前还没有人找到弹力胶的用途，但没关系。这要么是一个弹力胶网络，要么是一个消防部门。但老实说，房屋很少烧毁，似乎并不需要消防部门。

假设某个地方有人决定要制作一些弹力胶，他们希望知道它会在管道中以多快的速度流动。测量它的流动速度就是你的工作。

你可以访问与网络连接的其中一根管道。该管道长度为 $l$ 米，并且你可以在选择的时间开始通过此管道传输弹力胶。你知道它以恒定的实数速度流动，该速度至少为 $v_1$ 米/秒，最多为 $v_2$ 米/秒。你希望以至多 $\frac{t}{2}$ 米/秒的绝对误差估计此速度(即绝对误差不大于 $\frac {t}{2}$)。

不幸的是，管道是不透明的，所以你唯一能做的事就是在管道的任意一点敲打，即在闭合的实数范围 $[0,l]$ 内。通过听到敲打声，你可以知道弹力胶是否到达了那个点。你的速度并不是无限快的。你第一次敲打必须在开始流动后至少 $s$ 秒，并且敲打之间必须有至少 $s$ 秒的间隔。

你的任务是确定一种策略，需要在最坏情况下用最少的敲击来估算弹力胶的流速。注意，在某些情况下，所需的估计可能是不可能的（例如，弹力胶可能过快地到达管道的末端）。

### **输入格式**

输入包含多组数据。输入的第一行包含一个整数 $c$ $(1 \le c \le 100)$，表示数据组数。接下来的 $c$ 行描述了每组数据。每组数据包含五个整数 $l$，$v_1$，$v_2$ ，$t$ 和 $s$ $（1 \le l, v_1, v_2, t, s \le 10^9 \text{并且}v_1<v_2)$，含义如上所述。

### **输出格式**

对于每组数据，输出在最坏情况下估计流速所需的最小敲击次数。如果无法准确测量流速，则输出 "$impossible$"(不含引号)。

### 说明/提示

时间限制：$1000$ ms，空间限制：$1048576$ kB。

### 题目来源

> International Collegiate Programming Contest (ACM-ICPC) World Finals 2015

> [icpc2015.pdf](https://icpc.global/worldfinals/problems/2015-ICPC-World-Finals/icpc2015.pdf)

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

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


title: [ICPC2015 WF] Qanat

description:
A qanat is an irrigation system widely used to deliver water in hot, arid climates. The technology was originally developed by Persians over 2000 years ago. In Morocco, qanats are known as khettara and are still used today in the southern part of the country.

The basic feature of a qanat is an essentially horizontal channel that brings water from an underground water source to an outlet near a civilization. There is also a shaft known as a mother well that rises vertically from the underground water source to the surface of a mountain or hill. Creating such a system is extremely expensive, and was especially so in ancient times, since all of the materials excavated from the channel and mother well must be carried above ground, either through the channel outlet or the top of the mother well. To aid in the construction, there are often one or more additional vertical shafts placed at strategic locations above the underground channel. Although these shafts must also be excavated, they provide a means for lifting additional dirt from the horizontal channel as illustrated in Figure 1.

  ![](https://vj.z180.cn/4dea3d690f1497e79acad3985c8a9915?v=1603314265)

   Figure 1: An illustration of a qanat.

For this problem, model the cross-section of a qanat as shown in Figure 2, with the channel outlet at $(0,0)$, the water source at $(w,0)$, and the top of the mother well at $(w,h)$ with $w > h$. The surface of the mountain extends along a straight line from $(w,h)$ to $(0,0)$.

  ![](https://vj.z180.cn/a58cc42544b91877083973369ca77d3c?v=1603314265)

   Figure 2: A simplified model of a qanat cross-section.

Every qanat must have a vertical mother well from the water source to the mountain surface above, along with $n$ additional vertical shafts. The channel and all shafts are modeled as line segments. Your goal is to determine the placement for those additional shafts so as to minimize the overall excavation cost. This cost is equal to the sum of the distances that each piece of excavated dirt must be transported to reach the surface (using any combination of horizontal and vertical movement). For example, the cost of excavating a continuous section of dirt starting from the surface and going along a path of length $\ell $ (possibly including turns) is $\int _0^{\ell } x \, dx = \frac{1}{2} \ell ^2$.

inputFormat: The input consists of a single line containing three integers $w$ ($1 \le w \le 10\, 000$), $h$ ($1 \le h < w$), and $n$ ($1 \le n \le 1\, 000$). The value $w$ is the horizontal distance from the water source to the qanat outlet. The value $h$ is the vertical distance from the water source to the mountain surface. The value $n$ is the number of vertical shafts that must be used in addition to the mother well.

outputFormat: First, display the minimum overall excavation cost. Next, display the $x$-coordinates, in increasing order, for $n$ optimally placed vertical shafts. If $n > 10$, display only the first $10$ $x$-coordinates. Answers within an absolute or relative error of $10^{-4}$ will be accepted. You may assume that there is a unique solution. No test case will result in a shaft within $0.001$ units from the outlet of the qanat channel or from another shaft.

translation:
[原题面链接](https://icpc.global/worldfinals/problems/2015-ICPC-World-Finals/icpc2015.pdf)

### **题目描述**

qanat 是一种广泛用在气候炎热、干旱的地区中供水的灌溉系统。这项技术最初由波斯人在 $2000$ 多年前发明。在摩洛哥，qanat 被称为 khettara。至今该系统在该国南部地区仍然被使用。

qanat 的基本特点是用一个基本上是水平的沟渠，把水从地下水源带到靠近城市的出水口。还有一个被称为母井的轴垂直向上延升，从地下水源上升到山脉或山丘的地表。建设这样的系统非常昂贵，在古代更加如此，因为从沟渠和母井中挖出的所有材料都必须在地表运输。这可以通过沟渠出口或母井顶部来进行。为了帮助施工，通常在地下沟渠上方的关键位置还会放置一个或多个额外的垂直井口。尽管这些井口也必须需要被挖掘，但它们提供了一种从水平沟渠中运输额外泥土的手段，如图 $1$ 所示。

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

对于这个问题，模拟一个 qanat 的横截面，如图 $2$ 所示，其中通道出口在 $(0,0)$，水源在 $(w,0)$，母井顶部在 $(w,h)$，其中 $w > h$。山的表面沿着一条直线延伸，从 $(w,h)$ 到 $(0,0)$。

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

每个 qanat 必须从水源到山体表面上有一个垂直的母井，还需要 $n$ 个额外的垂直井。水道和所有垂直井都被建模为线段。你的目标是确定这些额外井的位置，以最小化整体的挖掘成本。这个成本等于每块挖掘的土壤必须被运输到表面的距离的总和（任何水平和垂直运动的组合）。例如，从表面开始并沿着长度为 $l$ 的路径挖掘连续的土壤的成本为 $\int_0^l x \ \mathop{}\!\mathrm{dx}=\frac{1}{2}l^2$。

### **输入格式**

输入是一行，包含三个整数 $w$ $(1\le w\le 10000)$， $h$ $(1\le h<w)$，和 $n$ $(1\le n\le 1000)$，分别表示水源到 qanat 出口的水平距离，水源到山体表面的垂直距离和除了母井之外必须使用的垂直井口的数量。

### **输出格式**

首先，输出最小开挖成本。接下来，按照递增顺序输出 $n$ 个最优放置的竖井的 $x$ 坐标。如果 $n > 10$，则仅输出前 $10$ 个 $x$ 坐标。相对误差可以在 $10^{-4}$ 之内。你可以假设存在唯一解决方案。没有数据会导致竖井距离 qanat 渠道出口或其他竖井小于0.001单位。

### **说明/提示**

时间限制：$2000$ ms，空间限制：$1048576$ kB。

来源：

> International Collegiate Programming Contest (ACM-ICPC) World Finals 2015


title: [ICPC2015 WF] Ship Traffic

description:
Ferries crossing the Strait of Gibraltar from Morocco to Spain must carefully navigate to avoid the heavy ship traffic along the strait. Write a program to help ferry captains find the largest gaps in strait traffic for a safe crossing.

Your program will use a simple model as follows. The strait has several parallel shipping lanes in east-west direction. Ships run with the same constant speed either eastbound or westbound. All ships in the same lane run in the same direction. Satellite data provides the positions of the ships in each lane. The ships may have different lengths. Ships do not change lanes and do not change speed for the crossing ferry.

The ferry waits for an appropriate time when there is an adequate gap in the ship traffic. It then crosses the strait heading northbound along a north-south line at a constant speed. From the moment a ferry enters a lane until the moment it leaves the lane, no ship in that lane may touch the crossing line. Ferries are so small you can neglect their size. Figure 1 illustrates the lanes and ships for Sample Input 1. Your task is to find the largest time interval within which the ferry can safely cross the strait.

  ![](https://vj.z180.cn/186da23b465c6f0f9a3f8b946eb2e17d?v=1601909422)

   Figure 1: Sample Input 1.

inputFormat:
The first line of input contains six integers: the number of lanes $n$ ($1 \leq n \leq 10^5$), the width $w$ of each lane ($1 \leq w \leq 1\, 000$), the speed $u$ of ships and the speed $v$ of the ferry ($1 \leq u, v \leq 100$), the ferry’s earliest start time $t_1$ and the ferry’s latest start time $t_2$ ($0 \leq t_1 < t_2 \leq 10^6$). All lengths are given in meters, all speeds are given in meters/second, and all times are given in seconds.

Each of the next $n$ lines contains the data for one lane. Each line starts with either E or W, where E indicates that ships in this lane are eastbound and W indicates that ships in this lane are westbound. Next in the line is an integer $m_ i$, the number of ships in this lane ($0 \leq m_ i \leq 10^5$ for each $1 \leq i \leq n$). It is followed by $m_ i$ pairs of integers $l_{ij}$ and $p_{ij}$ ($1 \leq l_{ij} \leq 1\, 000$ and $-10^6 \leq p_{ij} \leq 10^6$). The length of ship $j$ in lane $i$ is $l_{ij}$, and $p_{ij}$ is the position at time $0$ of its forward end, that is, its front in the direction it moves.

Ship positions within each lane are relative to the ferry’s crossing line. Negative positions are west of the crossing line and positive positions are east of it. Ships do not overlap or touch, and are sorted in increasing order of their positions. Lanes are ordered by increasing distance from the ferry’s starting point, which is just south of the first lane. There is no space between lanes. The total number of ships is at least $1$ and at most $10^5$.

outputFormat: Display the maximal value $d$ for which there is a time $s$ such that the ferry can start a crossing at any time $t$ with $s \leq t \leq s+d$. Additionally the crossing must not start before time $t_1$ and must start no later than time $t_2$. The output must have an absolute or relative error of at most $10^{-3}$. You may assume that there is a time interval with $d > 0.1$ seconds for the ferry to cross.

translation:
从摩洛哥穿越直布罗陀海峡到西班牙的渡轮必须小心地航行，以避免海峡沿岸的繁忙船只交通。编写一个程序，帮助渡轮船长找到海峡交通中两艘船最大的差距，以便安全穿越。

您的程序将使用一个简单的模型，如下所示：海峡有几条东西方向的平行航道。船舶以相同的恒定速度向东或向西行驶。同一航道上的所有船只都朝同一方向行驶。卫星数据提供了每条水道上船只的位置。这些船可能有不同的长度。船舶不会改变航道，也不会改变过境渡轮的速度。

当船舶交通有足够的间隙时，渡轮会等待适当的时间。然后它以恒定的速度沿着南北线向北行驶穿过海峡。从渡轮进入水道的那一刻起，直到它离开水道的那一刻，该水道上的船只都不得触碰过界线。渡轮很小，所以你可以忽略它们的长度。您的任务是找到渡轮可以安全穿越海峡的最大时间间隔。

输入的第一行包含六个整数：水道数$n$($1≤n≤10^5$)，每条水道的宽度$w$($1≤w≤1000$)，船速$u$和渡船速度$v$ ($1≤u,v≤100$)，渡轮的最早开始时间$t1$和渡轮的最晚开始时间$t2$($0≤t1<t2≤10^6$)。所有长度均以米为单位，所有速度均以米/秒为单位，所有时间均以秒为单位。

接下来的$n$行中的每一行都包含一条水道的数据。每行以 E 或 W 开头，其中 E 表示此车道中的船舶向东行驶，W 表示此水道中的船舶向西行驶。行中的下一个是整数$m_i$，表示这条航线上的船只数量($0≤m_i≤10^5$ for each $1≤i≤n$)。 紧随其后的是$m_i$对$l_{ij}$和 $p_{ij}$($1≤l_{ij}≤1000$ and $-10^6≤p_{ij}≤10^6$)。$l_{ij}$表示船$j$在车道$i$上的长度，$p_{ij}$是其前端在时间$0$的位置，即其前方在其移动方向上的位置。

每条车道内的船舶位置相对于渡轮的交叉线。负仓位位于交叉线以西，正仓位位于交叉线以东。船只不重叠或接触，并按其位置的递增顺序排序。车道的顺序是增加与渡轮起点的距离，该起点位于第一条车道的南边。车道之间没有空间。船舶总数至少为
$1$，最多$10^5$。

输出存在于时间$s$的最大值$d$，以便渡船可以在任何时间t开始穿越海峡且$s≤t≤s+d$.
此外，横渡不得在时间$t1$之前开始，并且不得晚于时间$t2$开始。输出的绝对或相对误差必须最多为$10^{-3}$。您可以假设渡轮通过的时间间隔为$d$（$d>0.1$） 秒。

时间限制：3000ms，内存限制：1048576KB。


title: [ICPC2015 WF] Tile Cutting

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

Youssef is a Moroccan tile installer who specializes in mosaics like the one shown on the right. He has rectangular tiles of many dimensions at his disposal, and the dimensions of all his tiles are integer numbers of centimeters. When Youssef needs parallelogram-shaped tiles, he cuts them from his supply on hand. To make this work easier, he invented a tile cutting machine that superimposes a centimeter grid on the cutting surface to guide the cuts on the tiles. Due to machine limitations, aesthetic sensibilities, and Youssef’s dislike of wasted tiles, the following rules determine the possible cuts.

The rectangular tile to be cut must be positioned in the bottom left corner of the cutting surface and the edges must be aligned with the grid lines.

The cutting blade can cut along any line connecting two different grid points on the tile boundary as long as the points are on adjacent boundary edges.

The four corners of the resulting parallelogram tile must lie on the four sides of the original rectangular tile.

No edge of the parallelogram tile can lie along an edge of the rectangular tile.

Figure 1 shows the eight different ways in which a parallelogram tile of area $4$ square centimeters can be cut out of a rectangular tile, subject to these restrictions.

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

   Figure 1: The eight different ways for cutting a parallelogram of area 4.

Youssef needs to cut tiles of every area between $a_{\text {lo}}$ and $a_{\text {hi}}$. Now he wonders, for which area $a$ in this range can he cut the maximum number of different tiles?

inputFormat: The input consists of multiple test cases. The first line of input contains an integer $n$ ($1 \le n \le 500$), the number of test cases. The next $n$ lines each contain two integers $a_{\text {lo}}, a_{\text {hi}}$ ($1 \le a_{\text {lo}} \le a_{\text {hi}} \le 500\, 000$), the range of areas of the tiles.

outputFormat: For each test case $a_{\text {lo}}$, $a_{\text {hi}}$, display the value $a$ between $a_{\text {lo}}$ and $a_{\text {hi}}$ such that the number of possible ways to cut a parallelogram of area $a$ is maximized as well as the number of different ways $w$ in which such a parallelogram can be cut. If there are multiple possible values of $a$ display the smallest one.

translation:
Youssef是一名专业贴瓷砖的修墙工，并且擅长用瓷砖贴出马赛克图案（如上图所示）。所有的瓷砖的尺寸长度均为整数，单位为$cm$。在马赛克图案中，平行四边形是不可或缺的。因此，Youssef会使用切割机，将矩形的瓷砖进行切割。在切割过程中，Youssef选择使用网格辅助切割机进行切割（在瓷砖上布上$cm$的网格方便切割）。

	切割过程有以下要求：
1.	可以从两个不同端点的连线切割（可以斜着切割）
2.	新平行四边形的四个角必须在矩形瓷砖的最外侧边上
3.	平行四边形的边不能与矩形的任意一条边边重叠

现在给出切割的面积的两个边界值$a_{lo}$和$a_{hi}$，求出Youssef能够最多切割掉的小矩形瓷砖数量。

**输入格式：**

给出测试样例数量$n$($1≤n≤500$)。下面$n$行给出切割面积的两个边界值$a_{lo}$和$a_{hi}$（$1≤a_{lo}≤a_{hi}≤500 000$）

**输出格式：**

每行先输出平行四边形面积$a$，再输出小矩形最多切割数量$w$。如果$a$有不同值的时候，输出最小的即可。

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

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


title: [ICPC2015 WF] Tours

description:
The Arca Carania Mountain national park is opening up for tourist traffic. The national park has a number of sites worth seeing and roads that connect pairs of sites. The park commissioners have put together a set of round tours in the park in which visitors can ride buses to view various sites. Each round tour starts at some site (potentially different sites for different tours), visits a number of other sites without repeating any, and then returns to where it started. At least 3 different sites are visited in each round tour. At least one round tour is possible in the national park.

The park commissioners have decided that, for any given road, all buses will be operated by a single company. The commissioners do not want to be accused of favoritism, so they want to be sure that each possible round tour in the park has exactly the same number of roads assigned to each bus company. They realize this may be difficult to achieve. Thus, they want to learn what numbers of bus companies allow for a valid assignment of companies to roads.

Consider Sample Input 1, which is illustrated in Figure 1. There are a total of three round tours for these sites. Some company is assigned road 1-3. It must also be assigned some road on the round tour 1-2-3-4-1, say 2-3. But then it is assigned to two of the three roads on the round tour 1-2-3-1, and no other company can match this – so there can be no other companies. In Sample Input 2 there is only one round tour, so it is enough to assign the roads of this tour equally between companies.

  ![](https://vj.z180.cn/17b3ab5defe058e1bc8649098ddaa63e?v=1603764959)

   Figure 1: Sample Input 1.

inputFormat: The first line of input contains two integers $n$ ($1 \le n \le 2\, 000$), which is the number of sites in the park, and $m$ ($1 \le m \le 2\, 000$), which is the number of roads between the sites. Following that are $m$ lines, each containing two integers $a_ i$ and $b_ i$ ($1 \leq a_ i < b_ i \leq n$), meaning the sites $a_ i$ and $b_ i$ are connected by a bidirectional road. No pair of sites is listed twice.

outputFormat: Display all integers $k$ such that it is possible to assign the roads to $k$ companies in the desired way. These integers should be in ascending order.

translation:
### 题目描述

给定一张 $n$ 个点 $m$ 条边的无向图，你需要选择一个颜色种类数 $k$，然后用这 $k$ 种颜色给每条边染色，要求对于图中任意一个简单环，每种颜色的边的数量都相同。求所有可行的 $k$。

保证图无重边，无自环。

### 输入格式

第一行两个正整数 $n, m$（$1\leq n, m\leq 2\times 10 ^ 3$）。

接下来 $m$ 行，每行两个正整数 $x, y$（$1\leq x < y \leq n$），表示一条无向边。

### 输出格式

一行按递增顺序输出所有可行的 $k$，用空格隔开。


title: [ICPC2015 WF] Weather Report

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

You have been hired by the Association for Climatological Measurement, a scientific organization interested in tracking global weather trends over a long period of time. Of course, this is no easy task. They have deployed many small devices around the world, designed to take periodic measurements of the local weather conditions. These are cheap devices with somewhat restricted capabilities. Every day they observe which of the four standard kinds of weather occurred: Sunny, Cloudy, Rainy, or Frogs. After every $n$ of these observations have been made, the results are reported to the main server for analysis. However, the massive number of devices has caused the available communication bandwidth to be overloaded. The Association needs your help to come up with a method of compressing these reports into fewer bits.

For a particular device’s location, you may assume that the weather each day is an independent random event, and you are given the predicted probabilities of the four possible weather types. Each of the $4^ n$ possible weather reports for a device must be encoded as a unique sequence of bits, such that no sequence is a prefix of any other sequence (an important property, or else the server would not know when each sequence ends). The goal is to use an encoding that minimizes the expected number of transmitted bits.

inputFormat: The first line of input contains an integer $1 \le n \le 20$, the number of observations that go into each report. The second line contains four positive floating-point numbers, $p_{\text {sunny}}$, $p_{\text {cloudy}}$, $p_{\text {rainy}}$, and $p_{\text {frogs}}$, representing the respective weather probabilities. These probabilities have at most 6 digits after the decimal point and sum to 1.

outputFormat: Display the minimum expected number of bits in the encoding of a report, with an absolute or relative error of at most $10^{-4}$.

translation:
给定4种天气情况出现的概率，你需要将n天的所有可能的 $4^{n}$ 种情况已某种方式编码为01串，使得：
- 编码长度的期望最短
- 任何一个编码不是另一个编码的前缀

求期望长度。


title: [ICPC2015 WF] Window Manager

description:
The past few years have seen a revolution in user interface technology. For many years, keyboards and mice were the tools used to interact with computers. But with the introduction of smart phones and tablets, people are increasingly using their computers by tapping and moving their fingers on the screen. Naturally this has led to new paradigms in user interface design. One important principle is that objects on the display obey “physical” laws. In this problem, you will see an example of this.

You have been hired to build a simulator for the window manager to be used in the next generation of smart phones from Advanced Cellular Manufacturers (ACM). Each phone they produce will have a rectangular screen that fully displays zero or more rectangular windows. That is, no window exceeds the boundaries of the screen or overlaps any other window. The simulator must support the following commands.

OPEN $x$ $y$ $w$ $h$ — open a new window with top-left corner coordinates $(x,y)$, width $w$ pixels and height $h$ pixels.

CLOSE $x$ $y$ — close an open window that includes the pixel at $(x,y)$. This allows a user to tap anywhere on a window to close it.

RESIZE $x$ $y$ $w$ $h$ — set the dimensions of the window that includes the pixel at $(x,y)$ to width $w$ and height $h$. The top-left corner of the window does not move.

MOVE $x$ $y$ $d_ x$ $d_ y$ — move the window that includes the pixel at $(x,y)$. The movement is either $d_ x$ pixels in the horizontal direction or $d_ y$ pixels in the vertical direction. At most one of $d_ x$ and $d_ y$ will be non-zero.

The OPEN and RESIZE commands succeed only if the resulting window does not overlap any other windows and does not extend beyond the screen boundaries. The MOVE command will move the window by as many of the requested pixels as possible. For example, if $d_ x$ is 30 but the window can move only 15 pixels to the right, then it will move 15 pixels.

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

   Figure 1: MOVE example

ACM is particularly proud of the MOVE command. A window being moved might “bump into” another window. In this case, the first window will push the second window in the same direction as far as appropriate, exactly as if the windows were physical objects. This behavior can cascade – a moving window might encounter additional windows which are also pushed along as necessary. Figure 1 shows an example with three windows, where window A is moved to the right, pushing the other two along.

inputFormat: The first line of input contains two positive integers $x_{\max }$ and $y_{\max }$, the horizontal and vertical dimensions of the screen, measured in pixels. Each is at most $10^9$ (ACM is planning on building displays with very high resolution). The top-left pixel of the screen has coordinates $(0,0)$. Each of the following lines contains a command as described above. One or more spaces separate the command name and the parameters from each other. The command parameters are integers that satisfy these conditions: $0 \leq x < x_{\max }$, $0 \leq y < y_{\max }$, $1 \leq w,h \leq 10^9$, and $|d_ x|,|d_ y| \leq 10^9$. There will be at most 256 commands.

outputFormat:
The output must follow the format illustrated in the sample output below.

Simulate the commands in the order they appear in the input. If any errors are detected during a command’s simulation, display the command number, command name, and the first appropriate message from the following list, and ignore the results of simulating that command (except as noted).

no window at given position — for the CLOSE, RESIZE, and MOVE commands — if there is no window that includes the pixel at the specified position.

window does not fit — for the OPEN and RESIZE commands — if the resulting window would overlap another window or extend beyond the screen boundaries.

moved $d’$ instead of $d$ — for the MOVE command — if the command asked to move a window $d$ pixels, but it could only move $d’$ pixels before requiring a window to move beyond the screen boundaries. The values $d$ and $d’$ are the absolute number of pixels requested and moved, respectively. The window is still moved in this case, but only for the smaller distance.

After all commands have been simulated and any error messages have been displayed, indicate the number of windows that are still open. Then for each open window, in the same order that they were opened, display the coordinates of the top-left corner $(x,y)$, the width, and the height.

translation:
过去几年，用户界面技术发生了一场革命。多年来，键盘和鼠标一直是与计算机交互的工具。但随着智能手机和平板电脑的推出，人们越来越多地通过在屏幕上敲击和移动手指来使用电脑。这自然导致了用户界面设计的新范式。一个重要的原则是显示器上的对象遵守“物理”定律。在这个问题中，您将看到一个例子。

您已被聘请为window manager构建一个模拟器，用于高级手机制造商（ACM）的下一代智能手机。他们生产的每款手机都有一个矩形屏幕，可以完全显示零个或多个矩形窗口。也就是说，没有窗口超出屏幕边界或与任何其他窗口重叠。模拟器必须支持以下命令。

OPEN x y w h——打开一个具有左上角坐标（x，y）、宽度w像素和高度h像素的新窗口

CLOSE x y——关闭一个打开的窗口，其中包括（x，y）处的像素。这允许用户点击窗口上的任意位置以关闭窗口。

RESIZE x y w h——将包含（x，y）处像素的窗口尺寸设置为宽度w和高度h。窗口的左上角不移动。

MOVE x y dx dy——移动包含（x，y）处像素的窗口。移动是水平方向上的dx像素或垂直方向上的dy像素。dx和dy中最多有一个为非零。

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

图1：移动示例

ACM对MOVE命令特别自豪。正在移动的窗口可能会“撞上”另一个窗口。在这种情况下，第一个窗口将以相同的方向尽可能远地推动第二个窗口，就像这些窗口是物理对象一样。此行为可能会层叠–移动的窗口可能会遇到其他窗口，这些窗口也会根据需要被推送。图1显示了一个有三个窗口的示例，其中窗口A向右移动，推动其他两个窗口。

输入格式

第一行输入包含两个正整数x_max和y_max，即屏幕的水平和垂直尺寸，以像素为单位。每个显示器的最大分辨率为10^9（ACM正计划建造具有极高分辨率的显示器）。屏幕左上角的像素具有坐标（0,0）。下面的每一行都包含一个如上所述的命令。命令名和参数之间用一个或多个空格分隔。命令参数是满足这些条件的整数：0≤x<x_max，0≤y<y_max，1≤w，h≤10^9，|d_x|、|d_y|≤10^9。最多有256条命令。

输出格式

输出必须遵循以下示例输出中所示的格式。

按照命令在输入中出现的顺序模拟命令。如果在命令模拟过程中检测到任何错误，请显示命令编号、命令名称和下表中的第一条适当消息，并忽略模拟该命令的结果（除非另有说明）。

如果在指定位置没有包含像素的窗口，则在给定位置没有窗口（用于关闭、调整大小和移动命令）。

如果生成的窗口与另一个窗口重叠或超出屏幕边界，则窗口不适用于“打开”和“调整大小”命令。

如果命令要求移动窗口d个像素，则移动d'而不是d-对于MOVE命令，但在要求窗口移动到屏幕边界之外之前，它只能移动d'个像素。值d和d’分别是请求和移动的像素的绝对数量。在这种情况下，窗口仍会移动，但仅移动较小的距离。

模拟所有命令并显示任何错误消息后，指示仍打开的窗口数。然后，对于每个打开的窗口，按照打开的顺序显示左上角（x，y）的坐标、宽度和高度。

输入输出样例

输入 #1

320 200

OPEN 50 50 10 10

OPEN 70 55 10 10

OPEN 90 50 10 10

RESIZE 55 55 40 40

RESIZE 55 55 15 15

MOVE 55 55 40 0

CLOSE 55 55

CLOSE 110 60

MOVE 95 55 0 -100

输出 #1

Command 4: RESIZE - window does not fit

Command 7: CLOSE - no window at given position

Command 9: MOVE - moved 50 instead of 100

2 window(s):

90 0 15 15

115 50 10 10

说明/提示

时间限制：1000毫秒，内存限制：1048576 kB。

该题出自：2015年国际大学生编程大赛（ACM-ICPC）世界总决赛


title: [ICPC2016 WF] Balanced Diet

description:
Every day, Danny buys one sweet from the candy store and eats it. The store has $m$ types of sweets, numbered from $1$ to $m$. Danny knows that a balanced diet is important and is applying this concept to his sweet purchasing. To each sweet type $i$, he has assigned a target fraction, which is a real number $f_ i$ ($0 < f_ i \le 1$). He wants the fraction of sweets of type $i$ among all sweets he has eaten to be roughly equal to $f_ i$. To be more precise, let $s_ i$ denote the number of sweets of type $i$ that Danny has eaten, and let $n = \sum _{i=1}^ m s_ i$. We say the set of sweets is balanced if for every $i$ we have

\[ n f_ i - 1 < s_ i < n f_ i + 1. \]

Danny has been buying and eating sweets for a while and during this entire time the set of sweets has been balanced. He is now wondering how many more sweets he can buy while still fulfilling this condition. Given the target fractions $f_ i$ and the sequence of sweets he has eaten so far, determine how many more sweets he can buy and eat so that at any time the set of sweets is balanced.

inputFormat:
The input consists of three lines. The first line contains two integers $m$ ($1 \le m \le 10^5$), which is the number of types of sweets, and $k$ ($0 \le k \le 10^5$), which is the number of sweets Danny has already eaten.

The second line contains $m$ positive integers $a_1, \ldots , a_ m$. These numbers are proportional to $f_1, \ldots , f_ m$, that is, $\displaystyle f_ i = \frac{a_ i}{\sum _{j = 1}^ m a_ j}$. It is guaranteed that the sum of all $a_ j$ is no larger than $10^5$.

The third line contains $k$ integers $b_1, \ldots , b_ k$ ($1 \le b_ i \le m$), where each $b_ i$ denotes the type of sweet Danny bought and ate on the $i^\text {th}$ day. It is guaranteed that every prefix of this sequence (including the whole sequence) is balanced.

outputFormat: Display the maximum number of additional sweets that Danny can buy and eat while keeping his diet continuously balanced. If there is no upper limit on the number of sweets, display the word forever.

translation:
## 题目描述

每天，Danny 都会从糖果店买一颗糖并吃掉它。糖果店中有 $m$ 种糖，编号为 $1 \dots m$ 。

Danny 知道均衡饮食很重要，他正在尝试在购买糖果时有一个均衡的饮食。因此他给每种糖 $i$ 分配了一个目标分数 $f_i (0 \le f_i \le 1, f_i$ 为一个实数 $) $, 。他希望他所吃的所有糖中，第 $i$ 种糖的数量占比大概为 $f_i$ 。

准确的说， 令 $s_ i$ 表示 Danny 已经吃掉的第 $i$ 种糖的数量,  $n = \sum _{i=1}^ m s_ i$, 我们认为一种吃糖的方法是均衡的仅当对于所有的 $i$，满足：

$$n f_ i - 1 < s_ i < n f_ i + 1$$

Danny 已经购买并吃掉了一些糖，并且他保证每个前缀的饮食都是均衡的。他想知道在保证每个前缀均衡饮食的条件下，他最多还能吃多少颗糖。

给定目标分数 $f_i$
和他已经吃过的糖果序列，请你确定在保证每个前缀均衡饮食的条件下，Danny 最多还能购买并吃掉多少颗糖果。

## 输入格式

输入包含三行。第一行包括两个整数 m $1 \le m \le 10^5$ 表示糖果的种类, $k(0 \le k \le 10^5)$ 表示 Danny 已经吃掉的糖果数量。

第二行包括 $m$ 个正整数 $a_1 \dots a_m$, 有   $ \displaystyle f_ i = \frac{a_ i}{\sum _{j = 1}^ m a_ j}$, 保证
$\sum_{i=1}^m a_i \le 10^5$ 。

第三行包括 $k$ 个正整数 $b_1 \dots b_k (1 \le b_i \le m)$, 表示 Danny 在第 $i$ 天购买并吃掉的糖的种类。保证序列的每个前缀（包括整个序列）是饮食均衡的。

## 输出格式
输出在保证每个前缀饮食均衡的条件下，Danny 最多还能购买并吃掉多少颗糖。

如果糖果的数量没有上限（即 Danny 能一直买下去），输出 `forever`。

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

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


title: [ICPC2016 WF] Branch Assignment

description:
The Innovative Consumer Products Company (ICPC) is planning to start a top-secret project. This project consists of $s$ subprojects. There will be $b \ge s$ branches of ICPC involved in this project and ICPC wants to assign each branch to one of the subprojects. In other words, the branches will form $s$ disjoint groups, with each group in charge of a subproject.

At the end of each month, each branch will send a message to every other branch in its group (a different message to each branch). ICPC has a particular protocol for its communications. Each branch $i$ has a secret key $k_ i$ known only to the branch and the ICPC headquarters. Assume branch $i$ wants to send a message to branch $j$. Branch $i$ encrypts its message with its key $k_ i$. A trusted courier picks up this message from this branch and delivers it to the ICPC headquarters. Headquarters decrypts the message with key $k_ i$ and re-encrypts it with key $k_ j$. The courier then delivers this newly encrypted message to branch $j$, which decrypts it with its own key $k_ j$. For security reasons, a courier can carry only one message at a time.

Given a road network and the locations of branches and the headquarters in this network, your task is to determine the minimum total distance that the couriers will need to travel to deliver all the end-of-month messages, over all possible assignments of branches to subprojects.

inputFormat: The first line of input contains four integers $n$, $b$, $s$, and $r$, where $n$ ($2 \le n \le 5\, 000$) is the number of intersections, $b$ ($1 \le b \le n-1$) is the number of branches, $s$ ($1 \le s \le b$) is the number of subprojects, and $r$ ($1 \le r \le 50\, 000$) is the number of roads. The intersections are numbered from $1$ through $n$. The branches are at intersections $1$ through $b$, and the headquarters is at intersection $b + 1$. Each of the next $r$ lines contains three integers $u$, $v$, and $\ell $, indicating a one-way road from intersection $u$ to a different intersection $v$ ($1 \leq u,v \leq n$) of length $\ell $ ($0 \leq \ell \leq 10\, 000$). No ordered pair $(u,v)$ appears more than once, and from any intersection it is possible to reach every other intersection.

outputFormat: Display the minimum total distance that the couriers will need to travel.

translation:
题目描述

给定一个 $n$ 个点，$r$ 条边的有向强连通图，正整数 $s,b$ 满足 $1\le s\le b \le n-1$。第 $b+1$ 个点称为总部。点 $x$ 向点 $y$ 发送信息的代价是 $dis(x,b+1)+dis(b+1,y)$。
现将点集 $\{1,2,\cdots,b\}$ 划分为 $s$ 个不相交的子集 $S_1,S_2,\cdots,S_s$。同一个子集内的点两两之间会互相发送信息。求最小化总代价。

数据范围

$2\le n \le 5000$，$1\le s\le b\le n-1$，$1\le r\le 50000$，边权非负且不大于 $10000$。


title: [ICPC2016 WF] Ceiling Function

description:
Advanced Ceiling Manufacturers (ACM) is analyzing the properties of its new series of Incredibly Collapse-Proof Ceilings (ICPCs). An ICPC consists of $n$ layers of material, each with a different value of collapse resistance (measured as a positive integer). The analysis ACM wants to run will take the collapse-resistance values of the layers, store them in a binary search tree, and check whether the shape of this tree in any way correlates with the quality of the whole construction. Because, well, why should it not?

To be precise, ACM takes the collapse-resistance values for the layers, ordered from the top layer to the bottom layer, and inserts them one-by-one into a tree. The rules for inserting a value $v$ are:

If the tree is empty, make $v$ the root of the tree.

If the tree is not empty, compare $v$ with the root of the tree. If $v$ is smaller, insert $v$ into the left subtree of the root, otherwise insert $v$ into the right subtree.

ACM has a set of ceiling prototypes it wants to analyze by trying to collapse them. It wants to take each group of ceiling prototypes that have trees of the same shape and analyze them together.

For example, assume ACM is considering five ceiling prototypes with three layers each, as described by Sample Input 1 and shown in Figure 1. Notice that the first prototype’s top layer has collapse-resistance value 2, the middle layer has value 7, and the bottom layer has value 1. The second prototype has layers with collapse-resistance values of 3, 1, and 4 – and yet these two prototypes induce the same tree shape, so ACM will analyze them together.

Given a set of prototypes, your task is to determine how many different tree shapes they induce.

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

   Figure 1: The four tree shapes induced by the ceiling prototypes in Sample Input 1.

inputFormat:
The first line of the input contains two integers $n$ ($1 \le n \le 50$), which is the number of ceiling prototypes to analyze, and $k$ ($1 \le k \le 20$), which is the number of layers in each of the prototypes.

The next $n$ lines describe the ceiling prototypes. Each of these lines contains $k$ distinct integers (between $1$ and $10^6$, inclusive), which are the collapse-resistance values of the layers in a ceiling prototype, ordered from top to bottom.

outputFormat: Display the number of different tree shapes.

translation: 给出 $n$ 组数，每组 $k$ 个，求这些数每组分别按顺序插入构成的不同二叉搜索树的数量。

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

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


title: [ICPC2016 WF] Clock Breaking

description:
After numerous unfortunate freak fatalities and the lawsuits, settlements, protests, and boycotts that naturally followed, the beleaguered executives at ACME Clock Manufacturers have decided they need to finally fix their disastrous quality control issues. It has been known for years that the digital clocks they manufacture have an unacceptably high ratio of faulty liquid-crystal display (LCD) screens, and yet these heartless souls have repeatedly failed to address the issue, or even warn their hapless consumers!

You have been called in as a quality consultant to finally put a stop to the madness. Your job is to write an automated program that can test a clock and find faults in its display.

These clocks use a standard 7-segment LCD display for all digits (shown on the left in Figure 1), plus two small segments for the ‘:’, and show all times in a 24-hour format. The minute before midnight is 23:59, and midnight is 0:00. The ‘:’ segments of a working clock are on at all times. The representation of each digit using the seven segments is shown on the right in Figure 1.

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

   Figure 1: LCD display of each digit.

Your program will be given the display of a clock at several consecutive minutes, although you do not know exactly what time these displays start. Some of the LCD segments are burnt out (permanently off) and some are burnt in (permanently on). Your program must determine, where possible, which segments are definitely malfunctioning and which are definitely in working order.

inputFormat:
The first input line contains a single integer $n$ ($1 \leq n \leq 100$), which is the number of consecutive minutes of a clock’s display. The next $8n-1$ lines contain $n$ ASCII images of these clock displays of size $7 \times 21$, with a single blank line separating the representations.

All digit segments are represented by two characters, and each colon segment is represented by one character. The character ‘X’ indicates a segment that is on. The character ‘.’ indicates anything else (segments that are off or non-segment portions of the display). See the sample input/output for details; the first output shows every possible LCD segment along with the smaller segments used to represent the ‘:’. No clock representation has an ‘X’ in a non-segment position or only half of a segment showing.

outputFormat: Display a $7 \times 21$ ASCII image with a ‘0’ for every segment that is burnt out, a ‘1’ for every segment that is burnt in, a ‘W’ for every segment that is definitely working, and a ‘?’ for every segment for which the status cannot be determined. Use ‘.’ for non-segments. If the given displays cannot come from consecutive minutes, display impossible.

translation:
### 题目描述

在无数不幸的畸形死亡事件以及随之而来的诉讼、和解、抗议和抵制之后，ACME时钟制造商的高管们决定最终解决灾难性的质量控制问题。多年来，人们都知道，他们制造的数字钟的液晶显示屏故障率高得令人无法接受，然而，这些无情的人们却一再未能解决这个问题，甚至未能警告他们不幸的消费者！

你被邀请担任质量顾问，最终制止了这种疯狂。你的工作是编写一个自动程序，可以测试时钟并发现其显示中的故障。

这些时钟使用标准的7段LCD显示屏显示所有数字（如图1左侧所示），加上两个小段显示`：`，并以24小时计时法显示所有时间。午夜前一分钟是23:59，午夜是0:00。工作时钟的`：`段始终打开。图1右侧显示了使用七段表示的`0~9`每个数字。

![图1：每个数字的LCD显示。](https://cdn.luogu.com.cn/upload/image_hosting/3ornshtp.png)

图1：每个数字的LCD显示。

### 输入格式

第一行有一个数$n(1\ \le\ n\ \le\ 100)$，这是时钟显示的连续分钟数。

接下来$8n-1$行包括$n$个时钟显示的$7\times 21$的ASCII图像，每两个之间会有一行的空白用于间隔

所有表示数字的段由两个连续的字符表示，每个表示冒号的段由一个字符表示。字符`X`表示打开的段。字符`.`指示其他任何内容（显示的分段或非分段部分）。详见样本输入、输出；第一个输出显示每个可能的LCD段以及用于表示`：`的较小段。没有时钟表示在非段位置有`X`，或仅显示段的一半。

### 输出格式

显示一个$7\times 21$ASCII图像，每个烧坏的段显示一个`0`，每个烧进的段显示`1`，每个正常工作的段显示为`W`，以及一个`？`对于无法确定状态的每个段。使用`.`对于非分段。如果给定的显示不能来自连续分钟，则显示`impossible`。

### 输入输出样例

### 说明/提示

时间限制：3000ms=3s

空间限制：1048576KB=1024MB=1GB

出处:2016年国际大学生编程大赛（`ACM-ICPC`）世界总决赛

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

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


title: [ICPC2016 WF] Forever Young

description:
My birthday is coming up. Alas, I am getting old and would like to feel young again. Fortunately, I have come up with an excellent way of feeling younger: if I write my age as a number in an appropriately chosen base $b$, then it appears to be smaller. For instance, suppose my age in base $10$ is $32$. Written in base $16$ it is only $20$!

However, I cannot choose an arbitrary base when doing this. If my age written in base $b$ contains digits other than $0$ to $9$, then it will be obvious that I am cheating, which defeats the purpose. In addition, if my age written in base $b$ is too small then it would again be obvious that I am cheating.

Given my age $y$ and a lower bound $\ell $ on how small I want my age to appear, find the largest base $b$ such that $y$ written in base $b$ contains only decimal digits, and is at least $\ell $ when interpreted as a number in base $10$.

inputFormat: The input consists of a single line containing two base 10 integers $y$ ($10 \le y \le 10^{18}$ – yes, I am very old) and $\ell $ ($10 \le \ell \le y$).

outputFormat: Display the largest base $b$ as described above.

translation:
# 题目大意
我的生日快到了！唉，但如今我已经老了，我想重新获得年轻的感觉。

幸运的是，我想出了一个让人感觉更年轻的好方法：如果我把我的年龄以适当选择的$b$进制书写，那么它看起来会更小。例如，假设我以$10$进制书写的年龄是$32$岁；以$16$进制书写，它只有$20$($0x20$)！

然而，在这样做时，我不能选择任意进制数。如果以$b$进制为数写的我的年龄包含$0-9$以外的数字，那么很明显我在作弊，这违背了目的。此外，如果我的年龄的进制数$b$太小，那么很明显我在作弊。

在我希望我的年龄看起来有多小的问题上,考虑到我的年龄$y$和下限$l$，找到最大的进制数$b$，这样写在基数$b$中的$y$只包含十进制数字，并且当将其看做一个十进制数字时至少是$l$。
# 输入格式
输入由一行组成，其中包含两个$10$进制的整数$y$ ($10\le y\le10^{18}$ –是的,我很老）和$l$($10\le l \le y$)
# 输出格式
如上所述，输出最大进制数$b$。
# 说明/提示
时间限制：$1s$，内存限制：$1GB$

(洛谷这里实际是$512MB$,但原题是$1GB$)

$2016年$国际大学生编程大赛$ACM$-$ICPC$世界总决赛

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

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


title: [ICPC2016 WF] Longest Rivers

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

The Chao Phraya River System is the main river system of Thailand. Its six longest rivers listed by decreasing length are:

Tha Chin ($765$ km)

Nan ($740$ km)

Yom ($700$ km)

Ping ($658$ km)

Pa Sak ($513$ km)

Wang ($335$ km)

A simplified model of this river system is shown in Figure 1, where the smaller red numbers indicate the lengths of various sections of each river. The point where two or more rivers meet as they flow downstream is called a confluence. Confluences are labeled with the larger black numbers. In this model, each river either ends at a confluence or flows into the sea, which is labeled with the special confluence number $0$. When two or more rivers meet at a confluence (other than confluence $0$), the resulting merged river takes the name of one of those rivers. For example, the Ping and the Wang meet at confluence $1$ with the resulting merged river retaining the name Ping. With this naming, the Ping has length $658$ km while the Wang is only $335$ km. If instead the merged river had been named Wang, then the length of the Wang would be $688$ km while the length of the Ping would be only $305$ km.

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

   Figure 1: The river system in Sample Input 1. Same-colored edges indicate a river.

The raised awareness of this phenomenon causes bitter rivalries among the towns along the rivers. For example, the townspeople along the Wang protest that maybe with a proper naming scheme, their river could actually be the longest, or maybe the second longest (or at least not last!). To end all the guessing, your task is to validate all such claims.

The rank of a river is its position in a list of all rivers ordered by decreasing length, where the best rank is $1$ for the longest river. For each river, determine its best possible rank over all naming schemes. At any confluence, the name of a new, larger river in any naming scheme must be one of the names of the smaller rivers which join at that confluence. If two or more rivers have equal lengths in a naming scheme, all the tied rivers are considered to have the best possible ranking. For example, if one river is the longest and all other rivers are equal, those rivers all have rank $2$.

inputFormat:
The first line of input contains two integers $n$ $(1 \le n \le 500\, 000)$, which is the number of river sources in the system, and $m$ $(0 \le m \le n - 1)$, which is the number of confluences with positive labels. These confluences are numbered from $1$ to $m$.

The next $n$ lines describe the rivers. Each of these lines consists of a string, which is the name of the river at the source, and two integers $c$ $(0 \leq c \leq m)$ and $d$ $(1 \leq d \leq 10^9)$, where $c$ is the identifier of the nearest confluence downstream, and $d$ is the distance from the source to that confluence in kilometers. River names use only lowercase and uppercase letters a–z, and consist of between $1$ and $10$ characters, inclusive.

The final $m$ lines describe confluences $1$ to $m$ in a similar fashion. The $k^\text {th}$ of these lines describes the confluence with identifier $k$ and contains two integers: the identifier of the nearest confluence downstream and the distance from confluence $k$ to this confluence in kilometers.

It is guaranteed that each confluence $1$ through $m$ appears as “the nearest downstream” at least twice, confluence $0$ appears at least once, and all sources are connected to confluence $0$.

outputFormat: Display one river per line in the same order as in the input. On that line, display the name of the river and its best possible rank.

translation:
有 $n$ 条河和 $m+1$ 个交汇处构成一棵以 $0$ 号点（即大海） 为根的树。

每条河有各自的名称。对于一个交汇处，从它流出的干流的名称是流入这个交汇处的各个支流的名称之一。一条河流的长度是以它为名称的河流的长度之和。对于一个可能的命名方案，一条河流的排名等于长度大于它的河流数 $+1$ 。

对于每条河，求出它在所有命名方案中，最小的排名。

samples:
PaSak 5
Nan 2
Yom 1
Wang 3
Ping 4
ThaChin 1

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

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


title: [ICPC2016 WF] Polygonal Puzzle

description:
During last year’s ACM ICPC World Finals in Marrakesh, one of the judges bought a pretty wooden puzzle depicting a camel and palm trees (see Figure 1). Unlike traditional jigsaw puzzles, which are usually created by cutting up an existing rectangular picture, all the pieces of this puzzle have been cut and painted separately. As a result, adjacent pieces often do not share common picture elements or colors. Moreover, the resulting picture itself is irregularly shaped. Given these properties, the shape of individual pieces is often the only possible way to tell where each piece should be placed.

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

   Figure 1: The judge’s wooden puzzle.

The judge has been wondering ever since last year whether it is possible to write a program to solve this puzzle. An important part of such a program is a method to evaluate how well two puzzle pieces “match” each other. The better the match, the more likely it is that those pieces are adjacent in the puzzle.

Pieces are modeled as simple polygons. Your task is to find a placement of two given polygons such that their interiors do not overlap but the polygons touch with their boundaries and the length of the common boundary is maximized. For this placement, polygons can be translated and rotated, but not reflected or resized. Figure 2 illustrates the optimal placement for Sample Input 1.

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

   Figure 2: Sample Input 1 and its optimal placement.

inputFormat:
The input contains the description of two polygons, one after the other. Each polygon description starts with a line containing an integer $n$ ($3 \leq n \leq 50$) denoting the number of vertices of the polygon. This is followed by $n$ lines, each containing two integer coordinates $x$, $y$ of a polygon vertex ($|x|, |y| \leq 100$). The vertices of each polygon are given in clockwise order, and no three consecutive vertices are collinear.

The input data is chosen so that even if the vertices were moved by a distance of up to $10^{-7}$, the answer would not increase by more than $10^{-4}$.

outputFormat: Display the maximum possible length of the common boundary of these polygons when they are optimally placed. Your answer should have an absolute or relative error of less than $10^{-3}$.

translation:
## 题意简述
有两个多边形，可以平移旋转（但不能对称、缩放等），求这两个多边形贴在一起但不重合的情况下贴贴部分的最大总长度。

## 输入格式
第一行一个数字$n_1$，表示第一个多边形是$n_1$边形。

接下来$n_1$行，每行两个数字，表示第一个多边形每个端点的横、纵坐标。

接下来一个数字$n_2$，表示第二个多边形是$n_2$边形。

最后$n_2$行，每行两个数字，表示第二个多边形每个端点的横、纵坐标。

## 输出格式
一行，最大的贴贴部分长度，绝对误差或相对误差任一小于$10^{-3}$即可通过。

## 数据范围
$3 \leq n_1, n_2 \leq 50$,
横纵坐标均为整数且绝对值不超过100。

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

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


title: [ICPC2016 WF] Road Times

description:
5s,1024MB

Ubol Narongdid is the founder of a brash new startup company called Special D-Liver-E. She wants to corner the market on overnight deliveries of organs between hospitals in the Phuket area. For scheduling purposes it is important to have accurate estimates for the times to perform such deliveries. Several trips between various hospitals have already been performed, so delivery times between those pairs of hospitals are known. The company currently has software to estimate times for other (as yet untraveled) trips, but so far all the estimates have been woefully inaccurate.

You have been asked to come up with a method to improve these estimates. You have at your disposal the following information: 1) the length (in kilometers) of the roads connecting each pair of cities in the Phuket area, and 2) a set of times (in minutes) for various previously executed deliveries.

You know that roads are one-way, and each road has a fixed speed limit that lies between $30$ and $60$ kilometers per hour. Speed limits are real-valued and need not be integers. You also know that delivery trucks always take the route that minimizes distance traveled, and on each road will always travel at a constant speed equal to that road’s speed limit. Thus you know, for example, that if a given trip is $50$ kilometers, the time it will take is between $50$ and $100$ minutes inclusive, in the absence of any other information. Ah, but you do have other information, namely the times of previous deliveries. It is up to you to use it to produce the best possible estimates.

inputFormat:
The input starts with a line containing an integer $n$ ($1 \le n \leq 30$) indicating the number of cities, numbered $0$ to $n-1$. After that are $n$ lines each containing $n$ integers specifying the distance in kilometers between cities: the $j^{\text {th}}$ value on the $i^{\text {th}}$ line indicates the distance when traveling directly from city $i$ to city $j$. A value of $-1$ indicates there is no road directly connecting the two cities, and the distance from any city to itself is always $0$; all other distances are positive and at most $1\, 000$. There are at most $100$ roads.

Following this is a line with a single integer $r$ ($1 \le r \leq 100$) indicating the number of previously executed routes. The next $r$ lines each contain three integers $s$, $d$, and $t$, where $s$ and $d$ are the source and destination cities and $t$ is how long the delivery from $s$ to $d$ took, in minutes.

Finally there is a line containing a single integer $q$ ($1 \le q \leq 100$) indicating the number of future delivery queries. The next $q$ lines each contain two integers $s$ and $d$ giving the source and destination cities for the query.

You may assume that for each of the $r+q$ source/destination pairs in the input there is a unique minimum-distance route.

outputFormat: Display a single line for each query containing the source and destination cities for that query, followed by the best low and high bounds on the estimate for the travel time, accurate to within an absolute or relative error of $10^{-6}$.


title: [ICPC2016 WF] Spin Doctor

description:
As an employee of the world’s most respected political polling corporation, you must take complex, real-world issues and simplify them down to a few numbers. It isn’t always easy. A big election is coming up and, at the request of Candidate X, you have just finished polling $n$ people. You have gathered three pieces of information from each person, with the values for the $i^\text {th}$ person recorded as:

$a_ i$ – the number of digits of $\pi $ they have memorized

$b_ i$ – the number of hairs on their head

$c_ i$ – whether they will vote for Candidate X

Unfortunately, you are beginning to wonder if these are really the most relevant questions to ask. In fact, you cannot see any correlation between $a$, $b$, and $c$ in the data. Of course, you cannot just contradict your customer – that is a good way to lose your job!

Perhaps the answer is to find some weighting formula to make the results look meaningful. You will pick two real values $S$ and $T$, and sort the poll results $(a_ i, b_ i, c_ i)$ by the measure $a_ i \cdot S + b_ i \cdot T$. The sort will look best if the results having $c_ i$ true are clustered as close to each other as possible. More precisely, if $j$ and $k$ are the indices of the first and last results with $c_ i$ true, you want to minimize the cluster size which is $k-j+1$. Note that some choices of $S$ and $T$ will result in ties among the $(a_ i,b_ i,c_ i)$ triples. When this happens, you should assume the worst possible ordering occurs (that which maximizes the cluster size for this $(S, T)$ pair).

inputFormat: The input starts with a line containing $n$ ($1 \leq n \leq 250\, 000$), which is the number of people polled. This is followed by one line for each person polled. Each of those lines contains integers $a_ i$ ($0 \leq a_ i \leq 2\, 000\, 000$), $b_ i$ ($0 \leq b_ i \leq 2\, 000\, 000$), and $c_ i$, where $c_ i$ is $1$ if the person will vote for Candidate X and $0$ otherwise. The input is guaranteed to contain at least one person who will vote for Candidate X.

outputFormat: Display the smallest possible cluster size over all possible $(S, T)$ pairs.

translation:
大选要到了，受候选人X的要求，你调查了 $n$ 个人，并记录了每个人的 $3$ 个信息：

+ $a_i$ 他们能记忆 $\pi$ 的多少位
+ $b_i$ 他们的头发数量
+ $c_i$ 他们是否会给候选人X投票

你需要找到某个公式使这些结果看起来有意义。你要选择 $2$ 个实数 $S$ 和 $T$，将所有调查结果按 $a_i\times S+b_i\times T$ 排序。如果 $c_i$ 为 `true` 的人聚集在了一起，你会觉得这个排序看起来不错。更准确地说，如果 $j$ 和 $k$ 分别是第一个和最后一个 $c_i$ 为 `true` 的人的下标，你想要最小化 $k-j+1$。注意有些 $S$ 和 $T$ 会让排序时出现相等的情况，这时你应该假设最坏情况发生，即排序使得 $k-j+1$ 最大。


title: [ICPC2016 WF] String Theory

description:
Nested quotations are great not only for writing literature with a complex narrative structure, but also in programming languages. While it may seem necessary to use different quotation marks at different nesting levels for clarity, there is an alternative. We can display various nesting levels using $k$-quotations, which are defined as follows.

A $1$-quotation is a string that begins with a quote character, ends with another quote character and contains no quote characters in-between. These are just the usual (unnested) quotations. For example, 'this is a string' is a $1$-quotation.

For $k > 1$, a $k$-quotation is a string that begins with $k$ quote characters, ends with another $k$ quote characters and contains a nested string in-between. The nested string is a non-empty sequence of $(k-1)$-quotations, which may be preceded, separated, and/or succeeded by any number of non-quote characters. For example, ''All 'work' and no 'play''' is a $2$-quotation.

Given a description of a string, you must determine its maximum possible nesting level.

inputFormat: The input consists of two lines. The first line contains an integer $n$ ($1 \le n \le 100$). The second line contains $n$ integers $a_1, a_2, \ldots , a_ n$ ($1 \le a_ i \le 100$), which describe a string as follows. The string starts with $a_1$ quote characters, which are followed by a positive number of non-quote characters, which are followed by $a_2$ quote characters, which are followed by a positive number of non-quote characters, and so on, until the string ends with $a_ n$ quote characters.

outputFormat: Display the largest number $k$ such that a string described by the input is a $k$-quotation. If there is no such $k$, display no quotation instead.

translation:
定义 $1$ 级引用是一个以引号字符 ' 开头和结尾，中间不包含引号字符的字符串。定义 $k$ 级引用为两端各有连续 $k(k>1)$ 个引号，中间有若干个 $k-1$ 级引用的字符串，其中第一个 $k-1$ 级引用前，最后一个 $k-1$ 级引用后，相邻两个 $k-1$ 级引用之间都可以添加任意个非引用字符。

现给定一个字符串中极长连续引号段的个数 $n(n\le100)$，和这 $n$ 个极长连续引号段的长度 $a_1,...,a_n$，求最大的 $k$，使得这个字符串是一个 $k$ 级引用。
若这样的 $k$ 不存在，输出 `no quotation`。

translated by @Starlight237