title: [NEERC2015] Iceberg Orders

description:
You are working for Metagonia stock exchange. Recently traders in Metagonia had heard about Iceberg orders traded on London stock exchange and asked your employer to add such functionality as well. A stock exchange is an engine that receives orders and generates trades.

An iceberg order is a quintuple of integers (ID, $T , P , V$ , TV). Each order has an identifier ID (unique among all orders), type $T$ (which is equal to either BUY $= 1$ or SELL $= 2)$ , price $P$ , total remaining volume $V$ and tip volume TV. For each order, exchange additionally keeps track of its current volume CV and priority PR. There is also a global priority counter of the exchange GP. An order book of the exchange is a set of orders.

Trades that are generated by the exchange are quadruples of integers (BUY ID, SELL ID, $P , V)$ . Each trade has BUY ID and SELL ID -- identifiers of matching BUY and SELL orders, trade price $P$ , and trade volume $V$ .

When an order is received by the exchange it is matched against orders currently on the order book. This is done as follows. Suppose an order a is received with $T_{a} =$ SELL. Among all orders currently on the order book we look for an order $b$ such that $T_{b} =$ BUY and $P_{b} \ge P_{a}.$ We select such an order $b$ with the largest price, and if there are several -- one with the smallest priority. If there is such an order $b$ , then a trade $t$ is generated with BUY $ID_{t} = ID_{b}$ and SELL $ID_{t} = ID_{a}$ at trade price $P_{t} = P_{b}$ with trade volume $V_{t} = mi_n(V_{a}, CV_{b}). V_{a}, V_{b},$ and $CV_{b}$ are all decreased by trade volume. If $V_{b} = 0$ after this, then the order $b$ is removed from the order book. If $CV_{b} = 0$ (but $V_{b} > 0)$ then we set current volume of order $b$ to $CV_{b} = mi_n(V_{b}, TV_{b}),$ set $PR_{b} =$ GP, and increment GP. We continue these operations of selecting $b$ and generating trades until either $V_{a} = 0$ or there are no more orders $b$ on the order book which satisfy the condition. In the latter case, we add order a to the order book with $CV_{a} = mi_n(V_{a}, TV_{a})$ and $PR_{a} =$ GP, and then increment GP. When the process of matching the order a is finished with several trades between the same pair of orders a and $b$ (and there can be lots of them!), they are all united into a single trade with the volume equal to the sum of individual trade volumes.

If $T_{a} =$ BUY we are looking for an order $b$ with $T_{b} =$ SELL and $P_{b} \le P_{a}$ and select such an order $b$ with the smallest price and the smallest priority among those. The rest of the matching process is as described above, with trades having BUY $ID_{t} = ID_{a},$ SELL $ID_{t} = ID_{b}, P_{t} = P_{b},$ and $V_{t} = mi_n(V_{a}, CV_{b}).$

Initially the order book is empty. You are presented with several orders that are received by the exchange one by one. You need to print generated trades and the order book state after all orders are processed.

Hint: The priority and GP are introduced in the problem statement only for the purpose of a formal description of the algorithm. The actual implementation does not have to keep track of priority. Typically, an exchange simply keeps a priority-ordered list of orders of each type at each price in its order book.

inputFormat: The first line of the input contains the number of orders $n (1 \le n \le 50 000)$ . Each of the following $n$ lines represent an order. Each order is given by a space-separated quintuple ID $T P V$ TV , where $1 \le $ ID $ \le 1 000 000 , T = 1$ for BUY and $T = 2$ for SELL, $1 \le P \le 100 000$ and $1 \le $ TV $ \le V \le 1 000 000 000$ .

outputFormat: For each order print all trades generated by processing this order, in ascending order of pairs (BUY ID, SELL ID), each trade on its own line. Each trade shall be printed as a space-separated quadruple of integers BUY ID SELL ID $P V$ . It is guaranteed that the total number of trades would not exceed $100 000$ . Print a blank line after all trades, followed by the order book. Each order that is still on the book shall be printed as a space-separated sextuple ID $T P V$ TV CV, sorted first by $P$ and then by PR.


title: [NEERC2015] Jump

type: P

background: 这是一道 IO 交互题。

description: 暂无英文题面。

translation:
给定长度为 $n$（$n$ 为偶数） 的 01 字符串 $S$。

你可以向交互库进行询问。你可以向交互库输出一个长度为 $n$ 的 01 字符串 $Q$。设 $S$ 和 $Q$ 有 $k$ 个对应的位置上的字符相同。若 $k=n$ 或 $k=\frac n 2$，则交互库将返回 $k$，否则交互库将返回 $0$。

你最多向交互库询问 $n+500$ 次，要求求出 $S$。你只需要使最后一次询问的返回值为 $n$ 即可。此时你应立即结束程序，否则将得到不可预料的结果。

若你的字符串长度不为 $n$ 或出现 01 以外的字符，或者你的询问次数超过上限，则交互库会返回 $-1$。此时你应立即结束程序，否则将得到不可预料的结果。

$1\leq n\leq 1000$。


title: [NEERC2015] King’s Inspection

description:
King Karl is a responsible and diligent ruler. Each year he travels across his country to make certain that all cities are doing well.

There are $n$ cities in his country and $m$ roads. In order to control the travelers, each road is unidirectional, that is a road from city a to city $b$ can not be passed from $b$ to a .

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

Karl wants to travel along the roads in such a way that he starts in the capital, visits every non-capital city exactly once, and finishes in the capital again.

As a transport minister, you are obliged to find such a route, or to determine that such a route doesn't exist.

inputFormat:
The first line contains two integers $n$ and $m (2 \le n \le 100 000 , 0 \le m \le n + 20)$ -- the number of cities and the number of roads in the country.

Each of the next $m$ lines contains two integers $a_{i}$ and $b_{i} (1 \le a_{i}, b_{i} \le n)$ , meaning that there is a one-way road from city $a_{i}$ to city $b_{i}.$ Cities are numbered from $1$ to $n$ . The capital is numbered as $1$ .

outputFormat:
If there is a route that passes through each non-capital city exactly once, starting and finishing in the capital, then output $n + 1$ space-separated integers -- a list of cities along the route. Do output the capital city both in the beginning and in the end of the route.

If there is no desired route, output `There is no route, Karl!` (without quotation marks).

translation:
国王 Karl 是一个负责并且勤奋的统治者。每年他都会游览并视察他的国家来保证每个城市都欣欣向荣。

他的国家有$n$个城市$m$条道路。每条道路是单向的，一条$a$到$b$的道路不能由$b$到$a$
经过。

Karl 想要游览他的国家，并且路线为由首都开始，经过每个非首都城市恰好一次，最终回到首都。

作为运输大臣，你有义务找到这样的一条路线，或者确定其不存在。

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


title: [NEERC2015] Landscape Improved

description:
Louis $L$ Le Roi-Univers has ordered to improve the landscape that is seen from the royal palace. His Majesty prefers to see a high mountain.

The Chief Landscape Manager is going to raise a mountain for Louis. He represents a landscape as a flat picture on a grid of unit squares. Some of the squares are already filled with rock, while others are empty. This greatly simplifies the design. Unit squares are small enough, and the landscape seems to be smooth from the royal palace.

The Chief Landscape Manager has a plan of the landscape -- the heights of all rock-filled columns for each unit of width. He is going to add at most $n$ square units of stones atop of the existing landscape to make a mountain with as high peak as possible. Unfortunately, piles of stones are quite unstable. A unit square of stones may be placed only exactly on top of the other filled square of stones or rock, moreover the squares immediately to the bottom-left and to bottom-right of it should be already filled.

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

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

Existing landscape

Improved landscape

Your task is to help The Chief Landscape Manager to determine the maximum height of the highest mountain he can build.

inputFormat:
The first line of the input file contains two integers $w$ -- the width of the existing landscape and $n$ -- the maximum number of squares of stones to add $(1 \le w \le 100 000 , 0 \le n \le 10^{18}).$

Each of the following $w$ lines contains a single integer $h_{i}$ -- the height of the existing landscape column $(1 \le h_{i} \le 10^{9}).$

outputFormat: The output file shall contain the single integer -- the maximum possible landscape height after at most $n$ unit squares of stones are added in a stable way.

translation:
给定序列 $\{h_i\}(i\in[1,w])$ 和常数 $n$。

$\forall i\in(1,w)$ ，仅当 $h_{i-1} \geq h_i$ 且 $h_{i+1} \geq h_i$ 时可使 $h_i$ 变为 $h_i+1$ ，且操作次数不能多于 $n$ 次。

求所有合法方案下，$\max\{h_i\}$ 的最大值。

$1\leq w\leq 10^5,1\leq h_i \leq 10^9,1\leq n\leq 10^{18}.$

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


title: [NEERC2014] Alter Board

description:
Little Dima gave his little brother Petya interactive chess board of size $n \times m$ as a present. There are many awesome features of this board but one is Petya's favorite. He can choose any rectangle formed by board squares and perform an inversion. Every white cell in the inverted rectangle becomes black and every black one becomes white.

In the initial state the board is colored in chess style, namely every cell is either black or white and every two cells that share a side have different colors. Little Petya wants to perform several inversions described above to turn all cells into the same color. He is impatient, so he asks you to provide him with instructions to do it with the minimal number of inversions.

inputFormat: Contains two integers $n$ and $m (1 \le n , m \le 50) -$ the number of rows and columns on the board, respectively.

outputFormat:
The first line must contain the number of inversions $k$ required to transform the board.

The following $k$ lines must describe inversions, one per line. Each line must contains $4$ integers $-$ row and column of one of the corners of the corresponding rectangle and row and column of the opposite corner. Any two opposite corners can be used to specify a rectangle.

Rows of the board are numbered from $1$ to $n$ . Columns of the board are numbered from $1$ to $m$ .

translation: 给出了一个 $n$ 行 $m$ 列的国际象棋棋盘。每次可以选择一个矩形区域，将里面的所有格子的颜色翻转。问最少需要多少次才能让所有格子变成同色？请输出一组合法的翻转方案。

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

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


title: [NEERC2014] Burrito King（征集SPJ）

description:
Two friends Albert and Barney came to the newly opened restaurant `Burrito King`. The restaurant had opened just yesterday, and Albert has got a special gift card, which allows the friends to get a free burrito. However, there is a constraint on the amount of ingredients -- the burrito can contain at most $g_i$ grams of ingredient $\(i\)$ for all $\(i\)$ from $1$ to $\(n\).$

There are two satisfaction parameters $\(a_i\)$ and $\(b_i\)$ for each ingredient -- the amount of Albert's joy per gram of the corresponding ingredient, and the amount of Barney's unhappiness per gram, correspondingly.

Therefore, the total Albert's joy from the burrito is equal to:

$\[\su_m_{i=1}^{n}{s_i \cdot a_i}\]$

The total Barney's unhappiness from the burrito is equal to:

$\[\su_m_{i=1}^{n}{s_i \cdot b_i}\]$

Here $\(s_i\)$ is the number of grams of the $\(i\)-th$ ingredient in the burrito. Note, that $\(s_i\)$ is not necessarily an integer, and $0 \le \(s_i\) \le \(g_i\).$

Albert wants to make his total joy from the burrito to be at least $\(A\).$ Barney is his best friend, so Albert wants Barney's total unhappiness to be no more than $\(B\).$ Among all possible burritos that satisfy the above constrains, Albert wants to choose one that maximises his total joy.

Your task is to help Albert to choose $\(s_i\)$ to satisfy these conditions or to find out that there is no solution.

inputFormat: The first line contains three integers $\(n\), \(A\),$ and $\(B\) (1 \le \(n\) \le 100 000 , 0 \le \(A\), \(B\) \le 10^{9}),$ the number of ingredients, the least amount of Albert's joy and the maximal amount of Barney's unhappiness. Each of the following $\(n\)$ lines contains a description of an ingredient: three integers $\(g_i\), \(a_i\), \(b_i\) (0 \le \(g_i\), \(a_i\), \(b_i\) \le 100)$ -- the maximal number of grams allowed, the amount of Albert's joy per gram and the amount of Barney's unhappiness per gram.

outputFormat:
The first line of the output must contain two real numbers -- the maximal amount of his joy and the amount of Barney's unhappiness that Albert can obtain, satisfying the conditions in the problem statement, or $`−1 −1`,$ if Albert cannot satisfy the conditions.

If the conditions are satisfiable the second line must contain $\(n\)$ real numbers -- the amount of each ingredient in grams.

Your output must have an absolute or relative error of at most $10−8$ .

Any way to reach maximal Albert's joy that satisfies the given conditions can be printed.

translation:
## 题目描述
两个朋友阿尔伯特和巴尼来到新开的 Burrito King 厅。这家餐厅昨天刚刚开业，阿尔伯特收到了一张特殊的礼品卡，可以让他们免费得到一份墨西哥卷饼。然而，配料的数量是有限制的。第 $i$ 种配料最多可以含有 $g_i$ 克（$1\le i\le n$）。

每种成分都有两个满意度参数 $a_i$ 和 $b_i$。分别指每克相应成分的阿尔伯特获得的快乐量和每克巴尼获得的不快乐量。因此，阿尔伯特从墨西哥卷饼中获得的全部快乐等于：
$$\sum_{i=1}^{n}s_i\cdot a_i$$
巴尼对墨西哥卷饼的全部不快乐等于：
$$\sum_{i=1}^{n}s_i\cdot b_i$$
这里 $s_i$ 是墨西哥卷饼中第 $i$ 种配料分的克数。注意，$s_i$ 不一定是整数，并且 $0\le s_i\le g_i$。

阿尔伯特想让他从墨西哥卷饼中获得的全部快乐至少是 $A$。巴尼是他最好的朋友，所以阿尔伯特希望巴尼的全部不快乐不超过 $B$。在所有可能满足上述限制的卷饼中，阿尔伯特想选择一种能最大限度地增加他全部快乐的卷饼。

您的任务是帮助阿尔伯特选择 $s_i$ 来满足这些条件，或者发现没有解决方案。
## 输入格式
第一行包含三个整数 $N$、$A$ 和 $B$（$1\le N \le 10^{5},0\le A,B\le 10^{9}$）。

以下 $N$ 行都包含一种配料的描述：三个整数 $g_i$、 $a_i$、 $b_i$（$0\le g_i,a_i,b_i\le 100$），分别指第 $i$ 种配料的最大含有克数、每克阿尔伯特获得的快乐的量和每克巴尼获得的不快乐的量。
## 输出格式
输出的第一行必须包含两个实数，指满足问题陈述中的条件时，阿尔伯特能获得的最大快乐量和巴尼的不快乐量，或者 `-1`（如果阿尔伯特不能满足条件）。

如果条件可以满足，第二行包含 $N$ 个实数  $s_i$，单位为克。

**您的输出必误差最多为 $10^{-8}$。任何满足给定条件的方法都判为正确。**


title: [NEERC2014] Cactus Generator（征集SPJ）

description:
NEERC featured a number of problems about cactuses -- connected undirected graphs in which every edge belongs to at most one simple cycle. Intuitively, cactus is a generalization of a tree where some cycles are allowed.

In $2005$ , the first year where a problem about cactuses appeared, the problem was called simply `Cactus`. In $2007$ it was `Cactus Reloaded`, in $2010$ it was called `Cactus Revolution`, and in $2013$ it was called `Cactus Automorphisms`. Here is an example of cactus that was used in those problems:

![](/upload/images2/cactus.png)

For four years judges had to generate test files for cactuses with thousands of vertices. Of course, a number of test generators of ever-increasing complexity were built, culminating with a domain-specific language called CGL -- Cactus Generator Language. CGL can compactly define a big cactus for purposes of a test. In this problem you have to parse a simplified version of this language, which we call SCGL -- Simple Cactus Generator Language, and output a resulting cactus.

A cactus has to be output by listing the minimal set of edge-distinct paths that cover the whole graph.

The syntax of SCGL cactus definition is represented by the graph non-terminal in the grammar that is given below using the Extended Backus-Naur Form:

graph $=$ `c`

$|$ `c(` list `)`

$|$ `loop(` list `)`

$|$ `t(` list `)`

list $=$ graph ${$ `,` graph $}$

$|$ (number $|$ range $|$ variable ) $[$ `,` graph $]$

number $=$ nzdig ${$ `0` $|$ nzdig $}$

nzdig $=$ `1` $|$ `2` $| \cdots |$ `8` $|$ `9`

range $=$ `range(` variable `,` numvar `,` numvar `)`

variable $=$ `A` $|$ `B` $| \cdots |$ `Y` $|$ `Z`

numvar $=$ number $|$ variable

A graph production rule denotes a graph with two labeled vertices -- the first and the last. Graphs definition rules have the following semantics:

The basic building block $c$ denotes a graph with just two vertices (one is the first and the other one is the last) and one edge.

The $c(σ)$ rule connects a specified list of graphs $σ$ from left to right into a chain, merging the last vertex of the first graph in the list with the first vertex of the second graph in the list, the last vertex of the second graph with the first of the third one, and so on. The resulting graph's first vertex is the first vertex of the first graph in the list, and the resulting graph's last vertex is the last vertex of the last graph in the list.

The $loo_p(σ)$ rule connects a specified list of graphs $σ$ from left to right, merging the last vertex of the first graph in the list with the first vertex of the second graph in the list, and so on like in $c(σ),$ while the last vertex of the last graph in the list is merged with the first vertex of the first graph in the list to form a loop. The resulting graph's first and last vertices are the first and the last vertices of the first graph in the list. Loop can be applied only to lists with more than one graph.

The $t(σ)$ rule connects a specified list of graphs $σ,$ merging their first vertices. The resulting graph's first and last vertices are the first and the last vertices of the first graph in the list.

The list of graphs is either specified explicitly, by a comma-separated list, or using a list repetition with a number, a range, or a variable, optionally followed by a comma and a graph. When a graph is not explicitly specified in a list repetition, then the given graph is assumed to be $c$ .

The simplest list repetition is defined using a number non-terminal. It denotes a list of graphs with the specified integer number of copies of the given graph.

A range list repetition is defined by $range(ν, α, β)$ rule which has three components -- a variable $ν,$ and numbers $α$ and $β.$ If $ξ$ character sequence is a graph, then $c|loo_p|t(range(ν, α, β), ξ)$ are called rangeenabled rules and the variable $ν$ is called a bound variable in $ξ.$ In the context of a range-enabled rule, $ξ$ is repeated $|β − α| + 1$ times to form a list. Every occurrence of variable $ν$ in $ξ$ is replaced by consecutive integer numbers between $α$ and $β$ inclusive in ascending order. That produces a list of $|β −α|+ 1$ graphs, which are then connected according the specification of the corresponding range-enabled rule. The $α$ and $β$ themselves might refer to variables that are bound in the outer range-enabled rule.

In a well-formed graph:

each variable non-terminal (a letter from A to $Z)$ occurs at most once as $ν$ in $range(ν, α, β)$ rules;

all other occurrences of variable non-terminal that are allowed by the grammar are bound.

Note, that if a character sequence $ξ$ is a graph, then $ξ, c(ξ),$ c(1 , $ξ), t(ξ),$ and t(1 , $ξ)$ all denote the same graph. On the other hand, neither $loo_p(ξ)$ nor loop(1 , $ξ)$ are allowed.

The following examples illustrate these basic rules. The graphs have their first and last vertices marked with letters $F$ and $L$ correspondingly.

![](/upload/images2/cactus1.png)

![](/upload/images2/cactus2.png)

inputFormat:
The input file contains a single line with a well-formed cactus definition in SCGL. While the syntax and semantics of SCGL themselves do not guarantee that the resulting graph is a cactus, the input file for this problem always defines a cactus -- every edge belongs to at most one simple cycle and there are no multiple edges between vertices. For example, neither loop(3 , $loo_p(3))$ nor $loo_p(2)$ are possible.

The line in the input file is at most $1000$ characters long and defines a cactus with at most $50 000$ vertices. Integer numbers represented by number non-terminals do not exceed $50 000$ .

outputFormat:
The first line of the output file must contain two integer numbers $n$ and $m$ . Here $n$ is the number of vertices in the graph. Vertices are numbered from $1$ to $n$ , where $1$ is the number of the first vertex of the graph and $n$ is the number of the last vertex of the graph. The other vertices can be numbered arbitrarily. Edges of the graph are represented by a set of edge-distinct paths, where $m$ is the minimal number of such paths.

Each of the following $m$ lines must contain a path in the graph. A path starts with an integer number $k_{i} (k_{i} \ge 2)$ followed by $k_{i}$ integers from $1$ to $n$ . These $k_{i}$ integers represent vertices of a path. A path can go to the same vertex multiple times, but every edge must be traversed exactly once in the whole output file.

translation:
### 题目描述

NEERC 以大量关于仙人掌的题目为特色——每条边属于至多一个简单环连通的无向图。直观的说，仙人掌是一种一些环被允许的广义树。

2005年，第一个有关仙人掌的问题出现，这个问题被简单的叫做[“仙人掌”](https://codeforces.com/gym/101334)。在2007年是[“仙人掌再来”](https://codeforces.com/gym/100273)，在2010年叫做[“仙人掌变革”](https://codeforces.com/gym/101309)，以及2013年是[“仙人掌自同构”](https://codeforces.com/gym/100307)。以下是这些问题中使用的仙人掌例子：

![](/upload/images2/cactus.png)

四年来评测必须为顶点以千数的仙人掌生成测试文件。当然，复杂性日益增加的大量数据发生器被建立，最终有一个被称为 CGL（Cactus Generator Language，仙人掌发生器语言）的领域特定语言。CGL 可以为测试的目的简洁地定义一个大仙人掌。本题中你要解析该语言的我们称为 SCGL（Simple Cactus Generator Language，简单仙人掌发生器语言）的一个简化版本，输出一个仙人掌作结果。

一个仙人掌要以列出边的极小集（覆盖全图的不同路径）输出。

SCGL 仙人掌定义的语法由语法中的指定的用下面的扩展巴科斯-诺尔范式的非终止图表示：

$$
\begin{aligned}
graph &= “\texttt{\textup{c}}”&&&&&&&&&&&&&&&&&&&&&&&&&&&\\
&| “\texttt{\textup{c(}}” list “\texttt{\textup{)}}”\\
&| “\texttt{\textup{loop(}}” list “\texttt{\textup{)}}”\\
&| “\texttt{\textup{t(}}” list “\texttt{\textup{)}}”\\
\end{aligned}
$$

$$
\begin{aligned}
list &= graph \{ “\texttt{\textup{,}}” graph \}&&&&&&&&&&&&\\
&|(number | range | variable ) [ “\texttt{\textup{,}}” graph ]\\
\end{aligned}
$$

$$
\begin{aligned}
&number = nzdig \{ “\texttt{\textup{0}}” | nzdig \}\\
&nzdig = “\texttt{\textup{1}}” | “\texttt{\textup{2}}” | \cdots | “\texttt{\textup{8}}” | “\texttt{\textup{9}}”\\
&range = “\texttt{\textup{range(}}” variable “\texttt{\textup{,}}” numvar “\texttt{\textup{,}}” numvar “\texttt{\textup{)}}”\\
&variable = “\texttt{\textup{A}}” | “\texttt{\textup{B}}” | \cdots | “\texttt{\textup{Y}}” | “\texttt{\textup{Z}}”\\
&numvar = number | variable
\end{aligned}
$$

一个图的制造规则表示一个有两个点标记的图——首和尾。图定义规则有以下语义：

- 基本建立块 $c$ 列表示一个仅有两个点（一首一尾）标记与一边的图。

- $c(σ)$ 规则对于含有 $n$ 个图的指定图列表 $σ$ 将第 $i$ 图尾顶点与第 $i+1$ 图首顶点合并，加入列表。（$i\in\mathbb{N}^*,1\le i< n$）结果图的首顶点为第一图首顶点，尾顶点为第 $n$ 图尾顶点。

- $loop(σ)$ 规则与 $c(σ)$相似，但第 $n$ 图尾顶点与第一图首顶点合并,加入列表。结果图的首尾顶点为列表中第一图首尾顶点。环仅可被应用于一图以上的列表。

- $t(σ)$ 规则连接一个指定图列表 $σ$，合并他们的首顶点。结果图的首尾顶点为列表中第一图首尾顶点。

图列表不是以一逗号分隔列表明确指定，就是用一个有一个数字、范围或变量的选择性地跟随一个逗号或图的可重列表指定。当一图非于一可重列表中明确指定，则该指定图被假定为 $c$。

最简单的可重列表用一个非终止数定义。它表示一个有指定整数个指定图的副本的列表。

一个可重范围列表由有三个组件（变量 $ν$，数字 $α$ 与 $β$）的 $range(ν, α, β)$ 规则定义。若 $ξ$ 字符序列为一图，则 $c|loop|t(range(ν, α, β), ξ)$ 被称为范围启用规则，变量 $ν$ 被称为 $ξ$ 中的一个约束变量。在一个范围启用规则的语境中，$ξ$ 被重复 $|β − α| + 1$ 次以建立列表。变量 $ν$ 于 $ξ$ 中的每次出现按升序由连续的 $α$ 与 $β$ 之间的整数（包括 $α$ 与 $β$）取代。 那产出一个包括 $|β −α|+ 1$ 个图的列表，通过相应的范围启用规则的规范连接。$α$ 与 $β$ 自身可能指被约束于外范围启用规则的变量。

在一个语法正确的图中：

- 每一个非终止变量（一个从 A 到 Z 的字母）作为 $range(ν, α, β)$ 规则中的 $ν$ 至多存在一次；

- 非终止变量的语法允许的所有其他事件被绑定。

注意，若一字符序列 $ξ$ 为一图，那么 $ξ, c(ξ), c(1 , ξ), t(ξ),$ 与 $t(1 , ξ)$ 都指此一图。另一方面，不论 $loop(ξ)$ 还是 $loop(1 , ξ)$ 都不被允许。

下列例子说明这些基本规则。这些图有以 F 与 L 相应标记的始末点。

![](/upload/images2/cactus1.png)

![](/upload/images2/cactus2.png)

### 输入格式

输入文件包含一行，含有一个 SCGL 定义。定义格式正确，总描述一仙人掌，每条边属于至多一个简单环，无重边。比如，$loop(3 , loop(3))$ 与 $loop(2)$ 都不可能。

输入文件中该行至多长 $1000$ 字符，定义的仙人掌至多 $50000$ 个顶点。由非终止数代列表的整数不超过 $50000$。
### 输出格式

输出文件第一行必须包含两个整数 $n$ 与 $m$。$n$ 为图顶点数。顶点由 $1$ 到 $n$ 编号，$1$ 为首点编号，$n$ 为图尾点编号。其他点可随意编号。图中边由一个边不重路径集代表，$m$为该集合最小路径数。

后 $m$ 行，每行必须包含图中一条路径。一条路径以一个整数 $k_{i} (k_{i} \ge 2)$ 开始，后随 $k_{i}$ 个整数从 $1$ 到 $n$。这 $k_{i}$ 个整数代列表一条路径的顶点。一条路径可经过同一顶点多次，但每条边必须在整个输出文件中刚好经过一次。

### 注释
此题中出现的的EBNF：

非终端符号为被定义的语言的句法部分。

终端符号为由一个或多个字符组成的序列，是构成语言的不可约元素。

本题中一条语法规则形如$元标识符=定义列表$

定义列表形如$主要句法|主要句法|\cdots$。

其中主要句法为可选序列、重复序列、分组序列、元标识符、终端字符串、空序列之一。

可选序列形如[定义列表]，重复序列形如{定义列表}，分组序列形如(定义列表)。

元标识符是以字母开头的字母数字序列，即非终端符号的名称。

由语法定义的语言的终端符号由终端字符串表示，终端字符串形如“一个或多个除该引号符号以外的任何终端字符的序列” 。

EBNF的终端符号称为终端字符，是字母、数字, 与`=|{}“()[]`字符之一。

需要注意的是，这里给出的EBNF不完整，但足以解决题目。


title: [NEERC2014] Damage Assessment

description:
A tank car that transports gasoline via rail road has a shape of cylinder with two spherical caps at the sides. The cylinder has a diameter $\(d\)$ and a length $\(l\).$ The spherical caps have a radius $\(r\) (\(2r\) \ge \(d\)).$ There was the rail road accident and the tank car had derailed. It now lies on the ground and some of the stored gasoline had flown out. The damage assessment must be performed. The location of the tank on the ground was established by measuring its tilt as the height difference $\(t\)$ from the bottom points of the cylinder on its left and right sides $(0 \le \(t\) \le \(l\)).$ The level of gasoline in the tank was established by measuring the height difference $\(h\)$ from the bottom point of the cylinder and the top level of gasoline. For the purpose of this problem, the top level of gasoline always intersects the cylinder part of the tank $(0 \le \(h\) \le \(t + d \sqrt{1 - (t/l)^2}).$

Your task is to figure out how much gasoline was left in the tank.

![](/upload/images2/dmaage.png)

inputFormat: The input file consists of a single line with five integer numbers -- $\(d\), \(l\), \(r\), \(t\)$ and $\(h\),$ which represent the diameter and the length of the tank's cylinder part, the radius of its spherical caps, tilt and gasoline level measurements. They are all expressed in millimeters ($1$ millimeter $= 10^{−3}$ meters), they satisfy all constraints expressed in the problem statement and $\(d\), \(l\) \ge 100 , \(d\), \(l\), \(r\) \le 10 000$ .

outputFormat: Write a single real number to the output file -- the volume of gasoline in the tank in liters ($1$ liter $= 10^{−3}$ cubic meters). The absolute error of the answer must not exceed $0$ . $1$ liters.

translation:
有一个由一个长度为 $l$，底面直径为 $d$ 的圆柱和两个半径均为 $r\ (2r\ge d)$ 的球形盖组成的油箱。由于一个交通事故，该油箱现在倾斜了一个角度，有一些汽油被洒了出来。现在给定圆柱底部的左右两个端点的高度差 $t\ (0\le t\le l)$ 以及剩余汽油的水平面到圆柱底端的距离 $h$，保证汽油的水平面一定与油箱的圆柱部分有交，即 $(0\le h\le t+d\sqrt {1-(t/l)^2})$。所有长度单位均用毫米给出。

求还剩下多少汽油（升），精确到 $0.1$。

$d,l\ge 100$，$d,l,r\le 10^4$。

下图为原题图。

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


title: [NEERC2014] Epic Win!

description:
A game of rock-paper-scissors is played by two players who simultaneously show out their moves: Rock, Paper , or Scissors. If their moves are the same, it's a draw. Otherwise, Rock beats Scissors, Paper beats Rock, and Scissors beat Paper .

The described procedure can be repeated many times. In this problem, two Finite State Machines (FSMs) will compete in a series of rounds. (Formally speaking, by FSMs we mean Moore machines in this problem. )

An FSM for playing rock-paper-scissors has finitely many states. Each state is described by the following: what move the FSM will make in the upcoming round, and what will be the new state in case of its opponent playing Rock, Paper , and Scissors.

![](/upload/images2/epic.png)

Fortunately, you know your opponent FSM -- the entire scheme except for one thing: you do not know the initial state of that FSM.

Your task is to design your own FSM to fight the given one. Your FSM must beat the opponent in at least $99\%$ of the first $1$ billion rounds. That's what we call an epic win!

inputFormat:
The input file contains a description of the opponent FSM in the following format.

The first line contains an integer $n (1 \le n \le 100)$ -- the number of states in the FSM. States are numbered from $1$ to $n$ . Each of the following $n$ lines contains a description of the state: a character $c_{i}$ denoting the move made by FSM and integers $r_{i}, p_{i}, s_{i}$ denoting the next state in case of seeing Rock, Paper, or Scissors respectively $(c_{i}$ can be `R`, `P`, or `S`; $1 \le r_{i}, p_{i}, s_{i} \le n$

outputFormat:
Write to the output the description of your FSM in the same format.

The initial state of your FSM is the first state.

The number of states may not exceed $50 000$ .

translation:
**【题目描述】**

在游戏「石头、剪子、布」中，两名玩家分别同时出示自己的行动：*石头*、*剪子*、或*布*。如果两人的行动一致，则平局。否则*石头*打败*剪子*、*布*打败*石头*、*剪子*打败*布*。

上述过程可以重复多次。在本题中，两台有限状态自动机（Finite State Machines，FSM）将游玩多轮「石头、剪子、布」（准确地说，本题中的 FSM 特指 Moore 状态机）。

一台被设计用来游玩「石头、剪子、布」的 FSM 有着有限的状态。每个状态由以下信息描述：下一轮中本台自动机将会出示怎样的行动，以及当下一轮中对手出示了*石头*、*剪子*、或*布*时应该转移到的新状态。

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

幸运的是，你知道对手的 FSM：你知道它所有的结构，但唯独不知道它的初始状态。

你的任务是设计一台你自己的 FSM 去和对手的进行对战。你的 FSM 必须在前十亿（${10}^9$）轮中打败对手至少 $99 \%$ 轮。这就是所谓的史诗般的胜利（epic win）！

**【输入格式】**

从标准输入中读入对对手的 FSM 的描述，按如下格式：

第一行一个正整数 $n$，表示 FSM 中的状态数。所有状态从 $1$ 到 $n$ 编号。

接下来 $n$ 行，每行描述一个状态：一个字符 $c_i$ 以及三个正整数 $r_i, p_i, s_i$，分别表示该状态的行动、以及当对手出示了*石头*、*布*、或*剪子*后应该转移到的新状态的编号，其中 $c_i$ 只可能为 $\{\texttt{R}, \texttt{P}, \texttt{S}\}$ 之一，如果为 $\texttt{R}$ 则意味着行动为出示*石头*，如果为 $\texttt{P}$ 则意味着行动为出示*布*，如果为 $\texttt{S}$ 行动为出示*剪子*。

**【输出格式】**

将你设计的 FSM 以相同格式输出到标准输出中。

你的 FSM 的初始状态是 $1$ 号状态。

你的 FSM 的状态数量不应超过 $50000$。

**【样例解释】**

题目描述中的图片显示了样例输入中给出的对手的 FSM，以及样例输出中给出的一个你的 FSM。

对手的 FSM 持续出示*石头*或*布*（取决于初始状态）直到它接收到*剪子*：接收到*剪子*将导致它的行为改变。

一种打败这样的 FSM 的方法是出示*布*。如果对手持续出示*石头*，只需继续出示*布*即可胜利。如果对手出示了*布*，通过出示一次*剪子*让它的行为改变，接下来它就会持续出示*石头*，然后你就可以用*布*打败它了。

**【数据范围】**

对于全部数据，$1 \le n \le 100$，$c_i \in \{\texttt{R}, \texttt{P}, \texttt{S}\}$，$1 \le r_i, p_i, s_i \le n$。

**翻译来源**：IOI 2021 集训队第一部分作业，PinkRabbit。


title: [NEERC2014] Filter

description:
You are working on a new high-performance database engine -- Instant Compression and Processing Codec $(ICPC).$ ICPC stores user activity records. Each user activity record has an integer user identifier. The records are stored in a number of data files. Each data file is compressed and can contain records from multiple users, however ICPC has to process queries that look for a specific subsets of users. In order to do so, there has to be a way to quickly determine which data files may contain records for a specific user before attempting to decompress them, which may be a long and CPU-consuming process.

ICPC uses an algorithm called Bloom Filter. The way it is implemented in ICPC is described below. For each ICPC database the following integer parameters are chosen:

$m$ is the number of bits in the filter;

$f$ is the number of hash functions in the filter;

$a_{i}$ are the parameters for hash functions for $0 \le i$

A value of the bloom filter is computed for each data file. The data file's bloom filter is a vector of $m$ bits. A bit number $j (0 \le j < m)$ is set to one if and only if there is a record in this data file for some user identifier $u_{k},$ such that for some hash function $i (0 \le i < f)$ the following equality holds:

$j = (u_{k} · a_{i})$ mod $m$ (1)

Your task is to implement ICPC filtering logic. You are given filter parameters and values for a number of data files and a set of user identifiers. Your task is determine which data files may contain record with at least one user identifier from the specified set. A data file may contain a record with a user identifier $u_{k}$ if and only if for all $i (0 \le i < f)$ all the bits $j$ given by equality (1) in its filter value are set to one.

inputFormat:
The first line of the input file contains filter parameters -- integer numbers $m , f$ , and $a_{i}$ for $0 \le i < f (1 \le m \le 1000 , 1 \le f \le 100 , 1 \le a_{i} < 2^{31}).$

The second line of the input file contains an integer $n$ -- the number of data files $(1 \le n \le 1000)$ . Each of the following $n$ lines contains bloom filter value of the corresponding file in hexadecimal form. Each value is represented by a string of $⌈m/4⌉$ hexadecimal digits (one of $0123456789abcdef).$ The first digit of the string represents bits $0-3$ of the value (stored in order from the least significant bit of a hexadecimal digit to the most significant bit), the second digit -- bits $4-7$ , the third -- $8-11$ , etc. When $m$ mod $4 ≠ 0$ , then the last hexadecimal digit represents the last $m$ mod $4$ bits of the value in its least significant bits.

The following line of the input file contains an integer $q$ -- the number of user identifiers in a query $(1 \le q \le 1000)$ , followed by $q$ integers $u_{k}$ -- the set of distinct user identifiers in the query $(1 \le u_{k} < 2^{31}).$

outputFormat: Write a line with the integer number $s$ to the output file -- the number of data files that may contain a record with at least one user identifier from the specified set, followed by $s$ numbers $d_{t} (0 \le d_{t} < n)$ -- the $0-based$ numbers of the corresponding data files in ascending order.


title: [NEERC2014] Gomoku

background: 这是一道 IO 交互题。

description:
This is an interactive problem.

Gomoku is a two-player game on a two-dimensional grid. Each cell of the grid can be either empty, contain the first player's mark $(black),$ or contain the second player's mark $(white),$ but not both. Initially the entire grid is empty. Two players make alternating moves, starting with the first player. At each move, a player can put her mark into exactly one empty cell. The first player to have her five adjacent marks in a single row wins. The winning row can be either vertical, horizontal or diagonal.

![](https://upload.acmicpc.net/23c94254-2783-405a-907b-7b66bea5514b/-/preview/)

Position where the second player (white marks) had won.

The players use a $19 \times 19$ grid in this problem. If the entire grid gets filled with marks but no player has won, the game is declared a draw.

The first player uses the following strategy: as the first move, she puts her mark into the center cell of the grid. At every other move, she picks such a move that maximizes the score of the resulting position.

In order to find the score of a position, the first player considers all possible places where the winning combination might eventually form -- in other words, all horizonal, vertical and diagonal rows of five consecutive cells on the board (of course, they may overlap each other). If such a row contains both the first player's marks and the second player's marks, it is disregarded. If such a row contains no marks, it is disregarded as well. For each row with exactly $k (1 \le k \le 5)$ marks of the first player and no marks of the second player, add $50^{2k−1}$ to the score of the position. For each row with exactly $k$ marks of the second player and no marks of the first player, subtract $50^{2k}$ from the score of the position. Finally, add a random integer number between $0$ and $50^{2} − 1$ to the score. This random number is chosen uniformly.

In case when several moves of the first player have equal scores (such ties are quite rare because of the random addition mentioned above), the first player picks the one with the smallest x-coordinate, and in case of equal x-coordinates, the one with the smallest y-coordinate.

Your task is to write a program that plays the second player and beats this strategy.

Your program will play $100$ games against the strategy described above, with different seeds of random generator. Your program must win all these games.

translation:
这是一道交互题。

五子棋是一种两个人在二维棋盘上玩的游戏。棋盘上的每个格子可以为空，放有第一名玩家的棋子（黑），或者放有第二名玩家的棋子（白），但是不能都有。初始时所有的格子都是空的。两个玩家轮流操作，从第一名玩家开始。每次操作，一名玩家可以把他的棋子放进恰好一个空格子里。首先在一行中放下五个相邻棋子的玩家获胜。一行可以是横行、竖行或对角线。

![1.png](https://upload.acmicpc.net/23c94254-2783-405a-907b-7b66bea5514b/-/preview/)

*第二名玩家（白子）获胜的一种情况。*

在这个问题中，玩家们使用 $19 \times 19$ 的棋盘。如果整个棋盘都放满了棋子但无人获胜，游戏平局。

第一名玩家将会使用下面的策略：第一次操作时，她会把她的棋子放到棋盘的正中间。在后面的每次操作中，她会选择一个下子后局面分数最大的位置下子。

为了计算一个局面的分数，第一名玩家会考虑能组成胜利组合的所有地方——换句话说，棋盘上所有横行、竖行、对角线上五个连续的格子（当然，它们会互相重叠）。如果这一行同时包括了第一名玩家的棋子和第二名玩家的棋子，就无视它。如果这一行包括了恰好 $k\ (1\le k\le 5)$ 个第一名玩家的棋子而没有第二名玩家的棋子，给该局面的分数加上 $50^{2k-1}$。如果这一行包括了恰好 $k$ 个第二名玩家的棋子而没有第一名玩家的棋子，给该局面的分数减去 $50^{2k}$。最后，给分数加上一个 $0$ 到 $50^2-1$ 的随机数。随机数是均匀分布的。

如果第一名玩家有多个分数相同的格子可选（因为上面提到的随机分数的原因，这是非常罕见的），第一名玩家选择 X 坐标最小的位置，如果仍有多个格子有相同的 X 坐标，就选择 Y 坐标最小的位置。

你的任务是，写一个程序扮演第二名玩家，并打败上述的策略。

你的程序将会与上述策略对局 $100$ 局，每局的随机数种子不同。你的程序必须在每局中都获胜。

### 交互格式

每一步你的程序需要做：

1. 从标准输入读入两个整数 $x,y$。
2. 如果都是 $-1$，那么游戏结束，你的程序必须退出。
3. 否则这两个整数描述了第一名玩家下子的坐标，$1\le x,y\le 19$。
4. 输出第二名玩家下子的坐标，然后换行。别忘了清空缓冲区。

### 样例

在下面的样例中，第一名玩家**没有**使用题目描述中所述的策略。这个样例只是为了说明交互格式。

![2.png](https://s1.ax1x.com/2020/10/29/B8voct.png)

*样例最终的棋盘状态。*

### 说明

世界上有很多种不同的五子棋规则。请只考虑题目描述中说明的这一种规则。

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


title: [NEERC2014] Hidden Maze

description:
Helen and Henry are fans of the TV show `Hidden Maze`, which is very popular in Hiddenland. During this show two participants (usually a married couple) are rushing through the maze consisting of $n$ halls connected by some tunnels. Each tunnel connects two different halls and there can't be more than one tunnel connecting any pair of halls.

In the beginning of the show, two participants are placed in two different halls. Then they need to move very quickly to meet each other before the time runs out. To pass through each tunnel, the participant needs to find a clue which is some positive integer number written on a small piece of paper.

If the participants finally meet in some tunnel before the time runs out, and successfully find a clue contained in the tunnel where they met, they are considered winners. The value of their prize is calculated by sorting all the clues found by them and taking the median value. The game is always set up in such a way, that the number of clues they find is odd.

Helen and Henry saw a large number of episodes of the show, and now they understand a lot about the mechanics of it. They noticed that the maze doesn't change between episodes, and they drew a complete map of the maze. Shortly after, Helen and Henry have discovered that the maze is built in such a manner that if you visit any tunnel at most once, then there is exactly one path between any two halls.

Helen and Henry have been wondering how this great maze is created, and not so long time ago they have seen an interview with Hillary, who worked for the company which had built the maze. Hillary has told that to make the show fair, the maze had been created using the following randomized algorithm:

Pick the number of halls $n$ . Build $n$ halls enumerated from $1$ to $n$ .

Choose at random two integers $i$ and $j$ , each of them uniformly distributed between $1$ and $n$ .

If halls $i$ and $j$ are the same or are already connected with some path of tunnels, then go to step $2$ .

Build the tunnel between $i$ and $j$ . If there is a path of tunnels from any hall to any other one, stop the process, otherwise go to step $2$ .

Helen and Henry have also noticed that each tunnel contains exactly one clue and its value never changes from episode to episode. However, they don't know what algorithm was used to generate clue values. Helen and Henry have written on their map the value of the clue for each tunnel.

It always takes $1$ minute to find a clue and to run through the tunnel from one hall to another. It takes half a minute to run from the hall to the center of the tunnel when the participants meet in the center of the tunnel at the end. The time given to participants is only enough to meet each other if they act optimally, that is they just run to each other via the shortest possible path, never make mistakes when finding clues, and never turn into any other tunnels that do not belong to the shortest path. To make the participants meet in the center of some tunnel, they are placed in the beginning of the show in such a way that the length of the shortest path between the halls where they are placed is odd.

Helen and Henry want to participate in the show. They know the maze by heart and they are pretty sure that they will succeed in moving optimally to each other and finding all clues in time. Provided that the pair of initial halls is selected uniformly from all pairs with an odd-length shortest path between them, they need to know the expected value of the prize they win. Your task is to help them find this expected value.

inputFormat: The first line of the input contains an integer number $n (2 \le n \le 30 000)$ -- the number of halls. Each of the following $n − 1$ lines contains three integers: $u_{i}, v_{i}, c_{i} (1 \le u_{i}, v_{i} \le n , 1 \le c_{i} \le 10^{6}),$ describing the i-th tunnel connecting the halls $u_{i}$ and $v_{i},$ containing the clue with the value $c_{i}.$ The maze is always created by the randomized algorithm that is specified in the problem statement.

outputFormat: Write to the output file a single real number -- the expected value of the prize. The absolute or relative error of the answer must not exceed $10^{−9}.$

translation:
给定一个 $n$ 个点的随机生成的无根树，每条边有正整数边权。每次随机两个最短路径边数为奇数的点，将这两点间路径上边权的中位数作为贡献。求这个贡献的期望。

by a___


title: [NEERC2014] Improvements

description:
Son Halo owns $n$ spaceships numbered from $1$ to $n$ and a space station. They are initially placed on one line with the space station so the spaceship $i$ is positioned $x_i$ meters from the station and all ships are on the same side from the station $(x_i > 0)$ . All $x_i$ are distinct. Station is considered to have number $0$ and $x_0$ is considered to be equal to $0$ .

Every two spaceships with consequent numbers are connected by a rope, and the first one is connected to the station. The rope number $i$ (for $1 \le i \le n)$ connects ships $i$ and $i-1.$ Note, that the rope number $1$ connects the first ship to the station.

Son Halo considers that the rope $i$ and the rope $j$ intersect when the segments $[x_{i}^{min}, x_{i}^{max}]$ and $[x_{j}^{min}, x_{j}^{max}]$ have common internal point but neither one of them is completely contained in the other, where $x_{k}^{min} = \min(x_{k−1}, x_k)$, $x_{k}^{max} = max(x_{k−1}, x_k).$ That is:

$$\begin{cases} x_{i}^{min} < x_{j}^{min} \sim \& \sim x_{j}^{min} < x_{i}^{max} \sim \& \sim x_{i}^{max} < x_{j}^{max} \\ x_{j}^{min} < x_{i}^{min} \sim \& \sim x_{i}^{min} < x_{j}^{max} \sim \& \sim x_{j}^{max} < x_{i}^{max}  \end{cases}$$

Son Halo wants to rearrange spaceships in such a way, that there are no rope intersections. Because he is lazy, he wants to rearrange the ships in such a way, that the total number of ships that remain at their original position $x_i$ is maximal. All the ships must stay on the same side of the station and at different positions $x_i$ after rearrangement. However, ships can occupy any real positions $x_i$ after rearrangement.

Your task is to figure out what is the maximal number of ships that can remain at their initial positions.

inputFormat: The first line of the input file contains $\(n\) (1 \le \(n\) \le 200 000)$ -- the number of ships. The following line contains $\(n\)$ distinct integers $\(x_i\) (1 \le \(x_i\) \le \(n\))$ -- the initial positions of the spaceships.

outputFormat: The output file must contain one integer -- the maximal number of ships that can remain at their initial positions in the solution of this problem.

translation:
一个数轴上有 $n$ 个位置互异的点，第 $i$ 个点的坐标为 $x_i\ (x_i \gt 0)$，第 $i$ 个点和第 $i - 1$ 个点连了一根绳子（第 $1$ 个点和原点连了根绳子）定义两根绳子有交当且仅当它们跨越的区间有交且不是包含关系。你可以改变若干个点的坐标到一个任意的正实数位置，使得最后不存在任何两根绳子有交。最大化不动的点的个数。

$n\le 2\times 10^5$，$x_i$ 构成一个 $1,2,\cdots,n$ 的排列。


title: [NEERC2014] Joke with permutation

description:
Joey had saved a permutation of integers from $1$ to $n$ in a text file. All the numbers were written as decimal numbers without leading spaces.

Then Joe made a practical joke on her: he removed all the spaces in the file.

Help Joey to restore the original permutation after the Joe's joke!

inputFormat:
The input file contains a single line with a single string -- the Joey's permutation without spaces.

The Joey's permutation had at least $1$ and at most $50$ numbers.

outputFormat:
Write a line to the output file with the restored permutation. Don’t forget the spaces!

If there are several possible original permutations, write any one of them.

translation:
给出数字之间无分隔符的 $1\dots n$ 的排列构成的字符串，将其还原为合法的排列。

保证 $n\leq 50$，输入数据均保证有解。如有多解输出任一即可。

样例可能有助于你更好理解题意。

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

Thanks to checker provider:@[Arcturus1350
](/user/57699).


title: [NEERC2014] Knockout Racing

description:
The races became more popular than ever at Pandora planet. But these races are quite unusual. There are $n$ cars participating in a race on the long straight track. Each car moves with a speed of $1$ meter per second. Track has coordinates in meters.

The car number $i$ moves between two points on the track with coordinates $a_{i}$ and $b_{i}$ starting at the second $0$ in the point $a_{i}.$ The car moves from $a_{i}$ to $b_{i},$ then from $b_{i}$ to $a_{i},$ then from $a_{i}$ to $b_{i}$ again, and so on.

Handsome Mike wants to knock some cars out of the race using dynamite. Thus he has $m$ questions. The question number $j$ is: what is the number of cars in the coordinates between $x_{j}$ and $y_{j}$ inclusive after $t_{j}$ seconds from the start?

Your task is to answer Mike's questions.

inputFormat:
The first line of the input file contains two integers $n$ and $m (1 \le n , m \le 1000)$ -- the number of cars in the race and the number of questions.

Each of the following $n$ lines contains a description of the car: two integers $a_{i}$ and $b_{i} (0 \le a_{i}, b_{i} \le 10^{9}, a_{i} ≠ b_{i})$ -- the coordinates of the two points between which the car $i$ moves.

Each of the following $m$ lines contains a description of the question: three integers $x_{j} , y_{j}$ , and $t_{j} (0 \le x_{j} \le y_{j} \le 10^{9}, 0 \le t_{j} \le 10^{9})$ -- the coordinate range and the time for the question $j$ .

outputFormat: Write $m$ lines to the output file. Each line must contain one integer -- the answer to the corresponding question in order they are given in the input file.

translation:
# 题目简述
有$N$辆车在很长的直线赛道（可看作数轴）上行驶，每辆车在区间$[A_i,B_i]$间往返行驶，速度相同，有$M$个询问，每次询问一个区间$[X_i,Y_i]$在$T_i$时刻有多少辆车


title: [NEERC2013] ASCII Puzzle

description:
Fili and Floi play a puzzle game. Fili takes a rectangular piece of paper that is lined with a $W \times H$ grid of square cells, cuts it into pieces on its grid lines, and carefully shuffles the pieces so that pieces do not rotate. Floi has to recombine the pieces back into the rectangle without rotating them.

Fili observes a number of constraints while cutting an original paper into pieces to make sure that the resulting puzzle is well-formed. First of all, Fili picks three integer numbers $w , h$ , and $n$ , so that an original rectangular paper has a width of $W = w_n$ cells and a height of $H = h_n$ cells. Here $w$ and $h$ are known to Floi, but $n , W$ , and $H$ are not. This way, the original rectangular piece of paper can be cut into a trivial puzzle of $k = n^{2}$ rectangles with a width of $w$ cells and a height of $h$ cells each. However, this trivial puzzle for $k > 1$ is not considered a well-formed puzzle for this game. Instead, the pieces int which the original rectangle is cut are based on these trivial $w \times h$ cell rectangles with the jagged edges between the adjacent pieces. Formally, the pieces into which the original $W \times H$ paper is cut satisfy the following constraints of a well-formed puzzle:

There are $k = n^{2}$ pieces.

Each piece is a simple $4-connected$ region of cells without holes.

Each cell of the original rectangular $W \times H$ paper is a part of exactly one piece.

Each piece contains four corners of the corresponding $w \times h$ rectangle in the trivial puzzle for the original paper.

The cells of each piece can come only from the corresponding $w \times h$ rectangle in the trivial puzzle, from the cells adjacent to this rectangle, and from the interior cells of the adjacent rectangles in the trivial puzzle.

The cut between two adjacent pieces cannot be straight. Only pieces that lie on the border of the original $W \times H$ paper have straight sides.

The corollary of these constraints is that each piece of a well-formed puzzle fits into a rectangle of (3w $− 2) \times $ (3h $− 2)$ cells. Moreover, the description of each piece will be given as a (3w $− 2) \times $ (3h $− 2)$ grid of cells in such a way, that the corresponding $w \times h$ rectangle of the trivial puzzle is exactly in the center.

The picture below to the left shows a sample rectangular piece of paper that is lined with a $W \times H = 12 \times 9$ square grid of cells and is cut into a trivial puzzle of $k = 9$ rectangles with a width of $w = 4$ cells and a height of $h = 3$ cells each with bold dashed lines. The corners of the central $3 \times 4$ piece of this trivial puzzle are shown in black. They have to be a part of the central piece of any well-formed puzzle. The other potential cells of the central piece of a well-formed puzzle are shown in gray. The bold black line shows (3w $− 2) \times $ (3h $− 2) = 10 \times 7$ rectangular region that will be describing this central piece. The picture to the right shows the same for the piece in the upper-right corner of the puzzle.

![](/upload/images2/neerc_a.png)

Your task is to help Floi solve the puzzle.

inputFormat:
The first line of the input file contains there integers $k , w$ and $h$ . Here $k$ is the number of pieces in the puzzle, $w$ is a width and $h$ is a height of a trivial puzzle piece $(k = n^{2}$ for $1 \le n \le 4 , 3 \le w , h \le 5)$ . The rest of the input file contains descriptions of $k$ pieces of a well-formed puzzle. Each piece is described by 3h $− 2$ lines that contain 3w $− 2$ characters each. Pieces are labeled with a consecutive English letters in uppercase (1st piece -- $‘A', 2nd$ piece -- $‘B',$ and etc). Each piece description uses only two characters on its 3h $− 2$ lines of 3w $− 2$ characters. The English letter corresponding to the piece denotes a cell that is a part of this piece, while $‘. '$ (dot) character denotes a cell that is not.

Empty lines separate different pieces.

outputFormat: The first line of the output file shall contain $W$ and $H$ -- the size of the original piece of paper that was cut into the puzzle pieces. The following $H$ lines shall contain $W$ English letters each, describing the solution of the puzzle. Letters denote the cells that belong to the corresponding puzzle pieces. If there are multiple ways to solve the puzzle, then print any solution.

translation:
Fili 和 Floi 在玩一个拼图游戏。Fili 准备了一个被划分为 $W\times H$ 个格子的矩形纸片，并沿着格子的边缘将纸片剪成了若干个小片，然后小心地重排这些纸片使得纸片没有被旋转。

Fili 观察到满足一些限制的裁剪方案会产生一个**良好**的拼图游戏：首先，Fili 选择了三个整数 $w,h,n$，使得原先矩形的长宽分别满足 $W = wn$ 和 $H = hn$。此处 $w,h$ 是 Floi 知道的。这样最初的拼图游戏就可以变为 $k=n^2$ 个 $w\times h$ 的矩形构成的**平凡的拼图**。然而，平凡的拼图游戏不被认为是良好的。一个良好的游戏被定义为在拼图间有着参差不齐的边界（译者注：即有缺口和凸起的拼图）的游戏。更形式化地，一个将 $W\times H$ 纸片裁剪成拼图游戏的裁剪方案被认为是良好的当且仅当它满足以下性质：

- 有 $k=n^2$ 片拼图，且该拼图的每一块与平凡的拼图中的 $n^2$ 个 $w\times h$ 矩形一一对应。
- 每片拼图是一个没有洞的四联通区域。
- 每个原 $W\times H$ 纸片的格子属于恰好一片拼图。
- 每片拼图都包含了其对应的 $w\times h$ 矩形的四个角落处的格子。
- 每片拼图只能包含有：其对应的 $w\times h$ 矩形中的格子，与该矩形相邻的格子，以及与该矩形相邻矩形的内部格子。
- 两个相邻的拼图的边界不是直的。只有恰好贴着纸片边界的拼图的边界是直的。

注意到每块拼图必然包含于以其对应的 $w\times h$ 矩形为中心的一个 $(3w-2)(3h-2)$ 大小的矩形，于是输入文件以此方式给出。

你需要找到拼图的一种拼法。

$k=n^2$，$1\le n\le 4$，$3\le w,h\le 5$。

samples:
8 6
AAAABBBB
AAAAAABB
ADAABBBB
DDDDCBBC
DDDCCCBC
DDDDCCCC

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


title: [NEERC2013] Bonus Cards

description:
Dmitry loves programming competitions very much. The Finals of the famed Champions League are taking place in Dmitry's home city, so he wants to visit the competition. The competition is very popular, but most tickets to the competition are reserved for VIPs and for sponsors.

For the general public tickets to the Champions League Finals are distributed in the following way. Spectators, that want to see the competition, submit their request that states the payment method they want to use to pay for their ticket. Suppose there are $n$ seats available. Several draw round are conducted. In each round every request that is not yet fulfilled receives some number of slots depending on the payment method. Then one of those slots is selected uniformly at random. The request to which this slot belongs is considered fulfilled and does not take part in subsequent drawing rounds. Draw ends after $n$ rounds or when there are no more unfulfilled requests, whichever occurs first. An International Card Processing Corporation (ICPC) is a sponsor of the Champions League. Those who chose ICPC card as a payment method receive two slots in each draw round, while users of other payment methods receive only one.

Dmitry has a card from ICPC, but he also has a card from Advanced Credit Merchandise $(ACM),$ which offers him a bonus on all his spendings. His brother Petr works in a company that conducts draw to distribute tickets, so he told Dmitry in advance how many people had already decided to use ICPC card and how many had decided to use other methods. Now Dmitry want to know the probabilities he would get a ticket if he would use his ICPC card or if he would use his ACM card, so that he can make an informed choice. His request is going to be in addition to the number of requests Petr had told him about.

Can you help?

inputFormat: The first and the only line of the input contains $3$ integer numbers -- the number of seats available for a draw $n (1 \le n \le 3000)$ , the number of requests with ICPC card as a payment method a , and the number of requests with other payment methods $b (0 \le $ a , $b \le 10^{9}).$

outputFormat: On the first line output the probability of getting a ticket using ICPC card. On the second line output the probability of getting a ticket using ACM card. Answers should have an absolute error of no more than $10^{-9}.$

translation:
一个比赛有 $n$ 张比赛门票，门票用随机抽选的方式决定。有 $a$ 个人参与一类抽选，$b$ 个人参与二类抽选，其中一类抽选选中的概率是二类抽选的两倍。共进行 $n$ 次抽选，第 $i$ 次随机抽选在前 $i-1$ 次没有选出的名额中选出一个人。也就是说，这个人获得了比赛门票，接下来第 $i+1$ 到 $n$ 次的抽选集合不包括他。

Dmitry 现在如果要参加门票抽选，请你求出他分别参与一类抽选名额和二类抽选名额时，能够获得比赛门票的概率。（$a,b$ 个人不包括 Dmitry）


title: [NEERC2013] Cactus Automorphisms

description:
NEERC had featured a number of problems in previous years about cactuses -- connected undirected graphs in which every edge belongs to at most one simple cycle. Intuitively, cactus is a generalization of a tree where some cycles are allowed.

In $2005$ , the first year where problems about cactuses had appeared, the problem was called simply `Cactus`. In $2007$ it was `Cactus Reloaded` and in $2010$ it was called `Cactus Revolution`. An example of cactus from NEERC $2007$ problem is given on the picture below.

![](/upload/images2/cac.png)

The challenge that judges face when preparing test cases for those problems is that some wrong solutions may depend on the numbering of vertices in the input file. So, for the most interesting test cases judges typically include several inputs with the same graph, but having a different numbering of vertices. However, some graphs are so regular that the graph remains the same even if you renumber its vertices. Judges need some metric about the graph that tells how regular the given graph is in order to make an objective decision about the number of test cases that need to be created for this graph.

The metric you have to compute is the number of graph automorphisms. Given an undirected graph $(V , E)$ , where $V$ is a set of vertices and $E$ is a set of edges, where each edge is a set of two distinct vertices ${v_{1}, v_{2}} (v_{1}, v_{2} ∈ V ),$ graph automorphism is a bijection $m$ from $V$ onto $V$ , such that for each pair of vertices $v_{1}$ and $v_{2}$ that are connected by an edge (so ${v_{1}, v_{2}} ∈ E)$ the following condition holds: ${m(v_{1}), m(v_{2})} ∈ E$ .

Each graph has at least one automorphism (one where $m$ is an identity function) and may have up to $n$ ! automorphisms for a graph with $n$ vertices. Because the number of automorphisms may be a very big number, the answer must be presented as a prime factorization $∏^{k}_{i=1} p_{i}^{q_{i}},$ where $p_{i}$ are prime numbers in ascending order $(p_{i} \ge 2 , p_{i} 0)$ .

inputFormat:
The first line of the input file contains two integer numbers $n$ and $m (1 \le n \le 50 000 , 0 \le m \le 50 000)$ . Here $n$ is the number of vertices in the graph. Vertices are numbered from $1$ to $n$ . Edges of the graph are represented by a set of edge-distinct paths, where $m$ is the number of such paths.

Each of the following $m$ lines contains a path in the graph. A path starts with an integer number $k_{i} (2 \le k_{i} \le 1000)$ followed by $k_{i}$ integers from $1$ to $n$ . These $k_{i}$ integers represent vertices of a path. Adjacent vertices in a path are distinct. Path can go to the same vertex multiple times, but every edge is traversed exactly once in the whole input file. There are no multiedges in the graph (there is at most one edge between any two vertices).

The graph in the input file is a cactus.

outputFormat: On the first line of the output file write number $k$ -- the number of prime factors in the factorization of the number of graph automorphisms. Write $0$ if the number of graph automorphisms is $1$ . On the following $k$ lines write prime numbers $p_{i}$ and their powers $q_i$ separated by a space. Prime numbers must be given in ascending order.

translation:
- **仙人掌**是满足如下条件的无向简单连通图：每条边被包含于至多一个简单环中。
- 设有无向图 $G=(V,E)$。称双射 $f:V\rightarrow V$ 是 $G$ 的**自同构**，当且仅当 $\forall v_1,v_2\in V$，都有 $(v_1,v_2)\in E\Leftrightarrow (f(v_1),f(v_2))\in E$。称两个自同构 $f_1,f_2$ 相同，当且仅当 $\forall v\in V$ 均有 $f_1(v)=f_2(v)$。
- 给定有 $n$ 个节点的仙人掌，求它的不同的自同构数。由于结果可能很大，你需要输出它的质因子分解的结果。
- 输入仙人掌的方式为：给定 $m$ 条路径，这些路径所覆盖的边即为仙人掌的全部边。保证这些路径不会重复经过一条边两次，且输入的图是仙人掌。
- $n,m\leq 5\times 10^4$。

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


title: [NEERC2013] Dictionary

description:
Petr and Dmitry are working on a novel data compression scheme. Their task is to compress a given set of words. To compress a given set of words they have to build a rooted tree. Each edge of the tree is marked with exactly one letter.

Let us define a dictionary that is produced by this kind of tree as a set of words that can be constructed by concatenating letters on edges on any path from any vertex in the tree (not necessarily root) and going away from root down to the leaves (but not necessarily finishing on a leaf).

Boys have to construct such a tree with a dictionary that is a superset of the set of words that they are given to compress. This tree should have the smallest number of vertices between trees that satisfy the above condition. Any tree with the same number of vertices will do. Your task is to help them.

![](/upload/images2/dict.png)

For example, in a tree on the picture above with the root marked as $1$ , a path from $7$ to $5$ reads `north`, a path from $16$ to $12$ reads `eastern`, a path from $29$ to $2$ reads `european`, a path from $3$ to $25$ reads `regional`, and a path from $1$ to $31$ reads `contest`.

inputFormat: The first line of the input file contains the number of words in a given set $n (1 \le n \le 50)$ . The following $n$ lines contain different non-empty words, one word per line, consisting of lowercase English letters. The length of each word is at most $10$ characters.

outputFormat: On the first line output the number of vertices in the tree $m$ . The following $m$ lines shall contain descriptions of tree vertices, one description per line. Vertices are indexed from $1$ to $n$ in the order of their corresponding description lines. If the corresponding vertex is a tree root, then its description line shall contain a single integer number $0$ , otherwise its description line shall contain an index of its parent node and a letter on the edge to its parent node, separated by a space.

translation:
## 题目描述

Petr和Dmitry正在研究一种新的数据压缩方案。他们的任务是压缩一组给定的单词。为了压缩给定的一组单词，他们必须建立一个有根的树。这棵树的每一个边缘都有一个字母。

让我们定义一个由这种树生成的字典，它是一组单词，可以通过在树的任何顶点（不一定是根节点）的任何路径上的边上连接字母，从根向下到叶子（但不一定在叶节点上完成）来构造。

男孩们必须用字典来构造这样一棵树，字典是一组单词的超集，他们被给予压缩。满足上述条件的树之间的顶点数应该最小。任何具有相同顶点数的树都可以。你的任务是帮助他们。

例如，上图中的一棵树的根标记为1，从7到5的路径表示north，从16到12的路径表示eastern，从29到22的路径表示european，从3到25的路径表示regional，从1到31的路径表示contest。

## 输入格式
第一行是一个数字n（0<n<50）
接下来n行都是一个长度小于10的字符串

## 输出格式
在第一行输出树中的顶点数m。每行树应包含一行描述的顶点。顶点按其相应描述行的顺序从1索引到n。如果对应的顶点是树根，则其描述行应包含单个整数0，否则其描述行应包含其父节点的索引和父节点边缘上的字母，用空格隔开。

samples:
5
north
eastern
european
regional
contest


title: [NEERC2013] Easy Geometry

description:
Eva studies geometry. The current topic is about convex polygons, but Eva prefers rectangles. Eva's workbook contains drawings of several convex polygons and she is curious what is the area of the maximum rectangle that fits inside each of them.

![](/upload/images2/eg.png)

Help Eva! Given the convex polygon, find the rectangle of the maximum possible area that fits inside this polygon. Sides of the rectangle must be parallel to the coordinate axes.

inputFormat:
The first line contains a single integer $n$ -- the number of sides of the polygon $(3 \le n \le 100 000)$ . The following $n$ lines contain Cartesian coordinates of the polygon's vertices -- two integers $x_{i}$ and $y_{i} (-10^{9} \le x_{i}, y_{i} \le 10^{9})$ per line. Vertices are given in the clockwise order.

The polygon is convex.

outputFormat:
Output four real numbers $x_{mi_n}, y_{mi_n}, x_{max}$ and $y_{max}$ -- the coordinates of two rectangle's corners $(x_{mi_n} < x_{max}, y_{mi_n} < y_{max}).$ The rectangle must fit into the polygon and have the maximum possible area.

The absolute precision of the coordinates should be at least $10-^{5}.$

The absolute or relative precision of the rectangle area should be at least $10^{-5}.$ That is, if $A'$ ; is the actual maximum possible area, the following must hold: $mi_n(|A-A'|,|A−A'|/A') ) \le 10^{-5}.$

translation:
**一句话题意：**

给你一个凸 $n$ 边形，并按顺时针给出每一个顶点的坐标，求出在这个凸 $n$ 边形之内的面积最大的一个边平行坐标轴的矩形的四个顶点。

**输入格式：**

第一行是一个正整数 $n$ ，且 $3\le n \le 100000$ 。

接下来 $n$ 行，每行两个整数 $x$ ， $y$ ，代表一个顶点的 $x$ 坐标和 $y$ 坐标。 $-10^9 \le x,y \le 10^9$ 。

**输出格式：**

输出四个整数 $x_{min},y_{min},x_{max},y_{max}$ ，代表你给出的这个面积最大的矩形。其中 $x_{min} \le x_{max} $ ， $y_{min} \le y_{max} $ 。

精度要求：如果 $A$ 是你算出的值， $A'$ 是真实的最大面积，那么你需要保证 $min( |A-A'|,|A-A'|/A') \le10^{-5}$ 。


title: [NEERC2013] Fraud Busters

description:
The number of cars in Default City that travel to the city center daily vastly exceeds the number of available parking spots. The City Council had decided to introduce parking fees to combat the problem of overspill parking on the city streets. Parking fees are enforced using an automated vehicle registration plate scanners that take a picture of the vehicle registration plate, recognize the sequence of digits and letters in the code on the plate, and check the code against a vehicle registration database to ensure that parking fees are dutifully paid or to automatically issue a fine to the vehicle owner otherwise.

As soon as parking fees were introduced, a parking fee fraud had appeared. Some vehicle owners had started to close one or several digits or letters on their vehicle registration plate with pieces of paper while they park, thus making it impossible for the current version of the automated scanner to recognize their vehicle's registration code and to issue them a fine.

The Default City Council had instituted the Fraud Busters Initiative (FBI) to design a solution to prevent this kind of fraud. The overall approach that FBI had selected is to expand the number of vehicle features that scanners recognize (including features like vehicle type and color), as well as excluding from the list any vehicles that are detected to be elsewhere at this time. This information should help to identify the correct vehicle by narrowing down the search in the vehicle registration database.

You are working for FBI. Your colleagues had already written all the complex pieces of the recognition software that analyses various vehicle features and provides you with a list of registration codes that might potentially belong to a scanned car. Your task it to take this list and a recognized code from the license plate (which may be partially unrecognized) and find all the registration codes that match.

inputFormat:
The first line of the input file contains $9$ characters of the code as recognized by the scanner. Code that was recognized by the the scanner is represented as a sequence of $9$ digits, uppercase English letters, and characters $` \times ` (star).$ Star represents a digit or a letter that scanner could not recognize.

The second line of the input file contains a single integer number $n (1 \le n \le 1000)$ -- the number of vehicle registration codes from the vehicle registration database.

The following $n$ lines contain the corresponding registration codes, one code per line. Vehicle registration codes are represented as a sequence of $9$ digits and uppercase English letters. All codes on these $n$ lines of the input file are different.

outputFormat:
On the first line of the output file write a single integer $k (0 \le k \le n)$ -- the number of codes from the input file that match the code that was recognized by the scanner. The code from the scanner matches the code from the database if the characters on all the corresponding positions in the codes are equal or the character from the scanner code is $` \times `.$

On the following $k$ lines write the matching codes, one code per line, in the same order as they are given in the input file.

translation:
给定一个含未知字符的长度为9字符串，未知字符用'*'表示（不含引号）。下面给出n个长度为9字符串，如果下面输入的字符串与一开始输入的字符串除未知部分的其他部分完全相同，则该字符串符合要求。输出符合要求的字符串的数量和每个符合要求的字符串。

举例：假设一开始输入的字符串为A58**52*1,则字符串A58ZS52T1符合要求，而字符串A589992G1不符合要求


title: [NEERC2013] Green Energy

description:
The technological progress in Flatland is impressive. This year, for example, the solar power stations of a new type will be build. In these stations solar panels are mounted not on the ground, but on high towers, along their heights.

There are $n$ towers to be mounted. The towers are already bought. The height of i-th tower is $h_{i}.$ Now engineers want to choose the points where they should be mounted to get the maximal total power.

The landscape of a territory of the power plant is described by a polyline with $m$ vertices. Vertices of the landscape polyline have coordinates $(x_{i}, y_{i}),$ such that $x_{i} < x_{i+1}.$

The sun angle is always $α$ degrees in Flatland. The sun is shining from the top-left to the bottom-right. The power that is produced by a tower depends on the length of its surface illuminated by the sun.

When two towers are mounted close to each other, the shadow of the left tower may fall onto the right tower, so the power, produced by the right tower, decreases. Also, the landscape itself may contain high points that drop shadows on some towers.

![](/upload/images2/ge.png)

Your task is to find the points on the territory of the plant to mount the given towers to maximize the total length of towers surface that is illuminated by the sun.

inputFormat: The first line of the input file contains three integers $n , m$ and $α (1 \le n \le 10^{4}, 2 \le m \le 10^{4}, 1 \le α < 90)$ . The second line contains $n$ integers $h_{i}$ -- the heights of the towers $(1 \le h_{i} \le 10^{3}).$ The following $m$ lines contain pairs $x_{i}, y_{i}$ -- the coordinates of the vertices of the landscape $(|x_{i}| \le 10^{5}, x_{i} < x_{i+1}, |y_{i}| \le 10^{3}).$

outputFormat: On the first line output the maximal possible summary length of towers that can be illuminated by the sun with an absolute precision of at least $10^{-6}.$ On the next $n$ lines output the x-coordinates of the points where the towers should be mounted to achieve this maximum with an absolute precision of at least $10^{-9}.$ Towers should be listed in the same order they are given in the input file.

translation:
## 题目描述 ##
平地上的技术进步令人惊叹。今年正要建造一种新型的太阳能发电站。在这些发电站中，太阳能电池板不是安装在地面上，而是安装在高塔上。

在二为世界中有要安装$i$个高塔。这些塔塔高固定。第$i$座塔的高度是$h_i$。现在，工程师们想要选择安装点，以获得最大的总功率。

电厂区域由有$m$顶点的线连接。这些线的顶点坐标为$(x_i,y_i)$满足$x_i<x_{i+1}$
在平地上，太阳的角度总是$\alpha$度。太阳从左上角照射到右下角。塔产生的功率取决于其表面被太阳照射的面积(其实是长度)。

当安装的两个塔彼此靠近时，左侧塔的阴影可能落在右侧塔上，从而右侧塔产生的功率降低。此外，电厂区域本身可能包含在某些塔楼上投下阴影的高点。

你的任务是在电厂区域内找到安装给定塔架的点，以得到太阳照射下塔架最大总表面积(长度)。

## 输入格式 ##

输入第一行包含三个整数：$n$,$m$,$\alpha$ $(1 \le n \le 10^4,2 \le m \le 10^4,1 \le \alpha <90)$。第二行包含$n$整数$h_i$(塔高）$(1 \le h_i \le 10^3)$。后面的$m$行每行有$x_i$,$y_i$一对数（电厂顶点坐标)$(|x_i|\le 10^5,x_i < x_{i+1},|y_i|\le 10^3)$

## 输出格式 ##

第一行:以至少$10^{-6}$精度输出可被太阳照亮的塔的最大可能汇总面积（长度)。在后n行上，输出此时塔安装点的x坐标，绝对精度至少为$10^{-9}$。塔的输出顺序应与输入顺序相同。

## 说明/提示 ##
时间限制：1h

空间顺序：128PB


title: [NEERC2013] Hack Protection

description:
Pavel is sending to his friend Egor some array of non-negative integers. He wants to be sure, that nobody hacks the array before his friend gets it. To solve this problem Pavel need to compute some kind of a checksum or a digest for his array. Pavel has an innovative mind, so he invents the following algorithm to compute the digest for his array: count the number of subarrays in which the bitwise xor of the numbers in the subarray is equal to the bitwise and of the same numbers.

For example, consider an array of four binary numbers `01`, `10`, `11`, and `11`. The table below to the left lists the results of the bitwise xor of numbers for each subarray of this array, and the table below to the right list the results of the bitwise and of numbers for each subarray of this array. The rows of the table correspond to the starting elements of the subarray from the $1st$ element of the array to the $4th$ one, while columns correspond to the ending elements of the subarray. Matching values are highlighted with gray background.

![](/upload/images2/hp.png)

Your task is to help Pavel compute this kind of a digest of the given array.

inputFormat: The first line contains one integer $n (1 \le n \le 100 000)$ . The second line contains $n$ non-negative integers $a_{i} (0 \le a_{i} \le 2^{31}-1)$ that are written in decimal notation.

outputFormat: On the first line of the output print Pavel's digest of the given array.

translation: 给定一个序列$a_i$，求有多少个区间满足区间内的数的异或和等于与的和的值。


title: [NEERC2013] Interactive Interception

description:
This is an interactive problem.

North Eastern Emergency Rocket Control agency (NEERC) has developed a new radar control system that is designed to better control ballistic rocket interception. To test the new system NEERC agency had developed a mathematical model that is intended to show this system’s abilities.

Let us represent a rocket as a point on a line. Initially the point is at some unknown integer location between $0$ and $p$, inclusive. It has some unknown speed of $q$ which is an integer between $0$ and $v$, inclusive.

Each second the following happens. First, the control system makes a query to the radar of a form “`check L R`” and gets an answer whether the point is currently between $L$ and $R$, inclusive, or not.

After that, the point’s coordinate increases by $q$.

The goal of the radar control system is to learn the exact location of the point at the beginning of some second. When it does learn the point’s location, then instead of making a query to the radar, it gives a command to intercept the point at that location.

You have to implement the control system that locates and intercepts the point while making at most $100$ queries to the radar.

### Interaction protocol
Interaction starts with your program reading two integers — the values of $p$ and $v$ from the standard input($1\leq p\leq 10^5$,$1\leq v\leq 10^5$).

After that your program must print commands to the standard output. Each command must be one of the following two.

- “`check L R`” — make a query to the radar to get an answer whether the point is currently between $L$ and $R$, inclusive, or not. The answer must be read from the standard input and is either “`Yes`” or “`No`”. After that the point’s coordinate is increased by $q$. $L$ and $R$ must be integers.
- “`answer x`” — the exact coordinate $x$ of the point is known, and you order to intercept the point. After printing this command your program must exit.

Your program must write end-of-line sequence and flush the standard output after each command, including the last command “`answer x`” (end-of-line must be written and flushed before exiting).

translation:
**这是一道交互题**。

平面上有一个点，初始位置 $x\in[0,p]$，速度 $q\in[0,v]$，其中 $p,v$ 是给定的。

你可以进行不超过 $100$ 次询问，形如 ``check L R``，满足 $0\le L\le R\le 10^9$，交互库会告诉你是否有 $x\in[L,R]$，每次询问之后，交互库会令 $x\gets x+q$。你需要在某个询问后确定此时的 $x$，并告诉交互库，格式形如 ``answer x``。

$1\le p,v\le 10^5$。

samples:
check 1 3
check 3 5
check 2 4
check 4 5
answer 5

hint: In the given example the point was initially at location $1$ and is moving at a speed $q = 1$.


title: [NEERC2013] Join the Conversation

description:
Abstract Communication Mastership (ACM) is a software company that develops a unique social network called tWinter.

Each tWinter user has a handle that starts with a commercial at $(‘@')$ character. Users of tWinter social network publish short messages to the network.

If a user's message contains another user's handle (preceded by a space or at the beginning of the message, and followed by a space or at the end of the message) then it is called a mention.

A sequence of messages is called a conversation if each message in the sequence (except the first one) contains a mention of the author of the previous message in the sequence.

You are hired to find the longest conversation in the given chronological log of messages.

inputFormat:
The first line of the input file contains an integer $n (1 \le n \le 50 000)$ -- the number of messages in the chronological log.

Each of the next $n$ lines contains a message preceded by its author's handle, a colon $(‘:')$ character, and a space.

Each message is at most $139$ characters long. Each handle is at most $20$ characters long and does not contain colons or spaces.

The input file contains only characters with ASCII codes between $32$ and $126$ , inclusive, and line breaks.

outputFormat:
On the first line of the output file write the length of the longest conversation in the given log. On the second line write $1-based$ indices of the messages in that conversation in ascending order.

If there are multiple longest conversations, write any one of them.

translation:
Abstract Communication Mastership (ACM)是一家软件公司，开发一种名为$“tWinter”$的独特社交网络。

每个$“tWinter”$用户都有一个句柄，句柄由$‘(’$或$‘‘’$或$‘@’$或$‘′’$或 $‘)’$开头。

每个$“tWinter”$社交网络的用户可以向网络发布短消息。

如果用户的消息包含另一个用户的句柄（句柄前面是空格或句柄是消息的开头并且后跟空格或消息末尾），则称为提及。

如果消息序列中的每条消息（第一条消息除外）都提及序列中前一条消息的作者，则该消息序列称为会话。

您需要在给定的消息时间顺序日志中查找最长的对话。

## 输入格式
输入文件共$n+1$行；

第一行包含一个整数$n(1≤n≤50000)$为消息日志中消息个数；

接下来$n$行每行一条消息，前面是其作者的句柄，句柄后是一个冒号，冒号后为消息正文。

每条消息长度最多为$139$个字符。每个手柄长度(不包含冒号或空格)最多为$20$个字符。

输入文件仅包含 ASCII 代码介于32和126（含）之间和换行符。

## 输出格式
输出文件共$2$行；

第一行上，写入给定日志中最长对话的长度；

在第二行写该对话中消息基于1的索引，按升序排列。

## 说明/提示
时间限制：2S；

空间限制：128MB。

samples:
6
@Petr: Leaving for #NEERC tomorrow!
@Roman: This #NEERC is going to be awesome!
@Stone_in_forest: Nothing happened today.
@NEERCNews: @Petr Don't forget an umbrella :)
@Lydia: @NEERCNews cares about @Petr - so cute ^_^
@Lydia: @Lydia @NEERCNews @Petr it won't be raining though!

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


title: [NEERC2013] Kabaleo Lite

description:
Kabaleo Lite is a board game. The board consists of several stacks of conical chips of various colors. Only the color of the top chip of the stack is visible.

Each player has a unique target color and a set of colored chips. The target color is hidden from other players, while the set of chips is visible to them. On his turn, player selects one of his chips and puts it on one of the board stacks, thus recoloring it to the color of the chosen chip.

After the last turn, the number of visible board chips of each color is calculated. The winning color is the color that occurs the maximum times. The player (if any) that has this color as his target color, wins the game. If there is no such player or if there are two or more colors that occur the maximum times, the game ends in a draw.

You are playing your last chip in the Kabaleo Lite game. Other players also have one chip left. You want to determine all possible moves that lead you to winning the game. You do not know the target colors of other players and you cannot predict their moves, so your move must guarantee your victory regardless of moves of your opponents.

inputFormat:
The first line contains four integers $n , p , c$ and $h$ -- the number of stacks on the board $(1 \le n \le 10^{6}),$ the number of players $(1 \le p \le 10^{6}),$ the number of chips' colors $(p \le c \le 10^{6}),$ and your hidden color $(1 \le h \le c)$ .

The second line contains $n$ integers $b_{i}$ -- the color of the visible board chip for each stack on the board $(1 \le b_{i} \le c)$ .

The third line contains $p$ integers $l_{i}$ -- the color of the last chip for each player $(1 \le l_{i} \le c)$ . The players are numbered from one (you) to $n$ in the order of their turns.

outputFormat:
The first line must contain $w$ -- the number of winning moves.

The second line must contain $w$ distinct numbers $m_{i}$ -- the numbers of the stacks on which your chip should be put to win. Stacks are numbered starting from $1$ in the order that their visible colors are given in the input file. You can output their numbers in any order on this line.

Remember, that your move should be winning regardless of the moves of all other players.

translation:
有一种棋盘游戏：棋盘上有 $n$ 个格子，每个格子上可以堆叠若干个有颜色的筹码，只有每个格子中最上方的筹码的颜色是可见的。

参加游戏的每个玩家都有各自不同的一个目标颜色，以及一些彩色筹码。每个人只知道自己的目标颜色，但各自拥有的筹码颜色和数量都是公开的。每个回合中，所有玩家轮流在棋盘上选一个格子放置筹码，同时覆盖下方的筹码。游戏结束后，数出棋盘上可见筹码数最多的颜色，以该颜色为目标颜色的玩家即获胜。若该颜色不是任何玩家的目标颜色，或者棋盘上出现最多的颜色不唯一，则游戏平局。

现在，一局游戏进行到了最后，你和其他所有玩家都只剩最后一个筹码。现在恰好轮到你操作，在不知道其他人的目标颜色的前提下，你想知道你一共有哪些操作可以保证必胜。

### 输入格式

第一行 $4$ 个整数 $n,p,c,h$，分别表示棋盘格数、玩家数、筹码颜色总数和你的目标颜色；

第二行 $n$ 个整数 $b_i$，表示棋盘上现有的筹码颜色，棋盘格编号从 $1$ 开始；

第三行 $p$ 个整数 $l_i$，表示每个玩家的最后一枚筹码的颜色，玩家编号从你开始。

### 输出格式

第一行 $1$ 个整数 $w$，表示你有多少种必胜操作。

第二行 $w$ 个整数 $m_i$，表示你应该把筹码放在哪个格子上。顺序不限。

数据范围见原题。


title: [CERC2013] Rubik's Rectangle

description:
A new puzzle which aims to conquer the game market is a fusion of Rubik's Cube and Fifteen. The board is an $H \times W$ frame with tiles with all numbers from $1$ to $H · W$ printed on them.

![](/upload/images2/rubik1.png)

The only type of move that is allowed is flipping either one of the rows or one of the columns. Flipping reverses the order of the row's (or column's) elements. Below the third row is flipped:

![](/upload/images2/rubik2.png)

You are given a board with tiles numbered in some arbitrary order. Determine a sequence of flips that brings the board to the nicely sorted position, if possible.

![](/upload/images2/rubik3.png)

inputFormat:
The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

The description of each test case starts with an empty line. The next line contains two space-separated integers $W$ and $H (1 \leq W,H \leq 100) -$ the width and height of the puzzle, respectively. Each of the next $H$ lines contains $W$ space-separated integers $-$ the numbers printed on consecutive tiles.

outputFormat:
Print the answers to the test cases in the order in which they appear in the input. Start the output for each test case with the word POSSIBLE or IMPOSSIBLE, depending on whether it is possible to solve the puzzle. If a solution exists, print (in the same line) first the number of moves (possibly $0$) and then their descriptions, each consisting of a single letter $R$ or $C$ specifying whether we are to flip a row or a column, concatenated with the index of the row or column to flip.

Any solution will be accepted as long as it does not use more than $10 · W · H$ moves. Each test case is either solvable within this limit, or not solvable at all.

translation:
有一个 $h\times w$ 的棋盘，每个位置上有一个在 $[1,h\times w]$ 的整数，且没有重复。每次操作可以翻转一行或一列（顺序上翻转）。

每个测试点共有 $T$ 组数据，每组数据都有 $h,w$ ，以及给定的 $h$ 行 $w$ 列的矩阵，要求对于每组数据，输出一行一个操作序列，使得操作后矩阵满足从上到下，从左到右递增。

如果无解，输出 `IMPOSSIBLE`。

如果有解，先输出 `POSSIBLE`，再输出操作序列的长度，然后输出操作序列。如果翻转第 $i$ 行，输出 `Ri`。如果翻转第 $i$ 列，输出 `Ci`，用空格隔开，中间不换行。

本题有 Special Judge, 操作序列长度不能超过 $10hw$。

$h,w \le 100$。

samples:
POSSIBLE 1 R3
POSSIBLE 0
POSSIBLE 3 R3 C3 R2
IMPOSSIBLE

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


title: [CERC2013] What does the fox say?

description: Determined to discover the ancient mystery—the sound that the fox makes—you went into the forest, armed with a very good digital audio recorder. The forest is, however, full of animals’ voices, and on your recording, many different sounds can be heard. But you are well prepared for your task: you know exactly all the sounds which other animals make. Therefore the rest of the recording—all the unidentified noises—must have been made by the fox.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

The first line of each test case contains the recording—words over lower case English alphabet, separated by spaces. Each contains at most 100 letters and there are no more than 100 words. The next few lines are your pre-gathered information about other animals, in the format <animal> goes <sound>. There are no more than 100 animals, their names are not longer than 100 letters each and are actual names of animals in English. There is no fox goes ... among these lines.

The last line of the test case is exactly the question you are supposed to answer: what does the fox say?

outputFormat: For each test case, output one line containing the sounds made by the fox, in the order from the recording. You may assume that the fox was not silent (contrary to popular belief, foxes do not communicate by Morse code).

translation:
### 题目大意

森林里面有很多声响，你想知道有哪些声响是由狐狸发出来的。

已知你搜集到了 $n$ 个声响，并且还知道某些其他动物能够发出的声响，已知如果没有哪一个声响是由其他任何一种动物发出来的话，那这个声响绝对是由狐狸发出来的。现在，给定你这 $n$ 个声响，以及某些其他动物能够发出的声响，请你求出狐狸发出的声响。

### 输入格式
**本题有多组询问。**

第一行包含一个整数 $T$，表示数据的组数。
接下来若干组数据，每组数据由三部分组成：

- 第一行 $n$ 个仅由小写字母组成的字符串，代表搜集到的 $n$ 个声响。
- 接下来有若干行，代表某些其他动物能够发出的声响。格式为 ``<animal> goes <sound>``，其中 `<animal>` 代表动物的名称（仅由一个字符串组成），`<sound>` 代表这个动物发出的声响（仅由一个字符串组成）。保证不会在这些动物中出现狐狸。
- 最后一行，一个确定的字符串 ``what does the fox say?``。

### 输出格式
对于每组数据，输出仅一行，代表狐狸能够发出的声响。

### 数据范围
$n\leqslant 100$。
保证每个字符串的长度不超过 $100$。

Translated by Eason_AC
2020.10.30

samples:
1
toot woof wa ow ow ow pa blub blub pa toot pa blub pa pa ow pow toot
dog goes woof
fish goes blub
elephant goes toot
seal goes ow
what does the fox say?

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

 Central Europe Regional Contest (CERC) 2013


title: [CERC2013] Magical GCD

description:
The Magical GCD of a nonempty sequence of positive integers is defined as the product of its length and the greatest common divisor of all its elements.

Given a sequence $(a_1, \ldots , a_ n)$, find the largest possible Magical GCD of its connected subsequences.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

The description of each test case starts with a line containing a single integer $n$, $1 \leq n \leq 100\, 000$. The next line contains the sequence $a_1, a_2 , \ldots , a _ n$, $1 \leq a_ i \leq 10^{12}$.

outputFormat: For each test case output one line containing a single integer: the largest Magical GCD of a connected subsequence of the input sequence.

translation:
有 $T$ 组询问，每次给出 $n$ 个数 $a_i$。

你需要找到这个数组的一个子序列（要求编号连续），使得该序列中所有数的最大公约数和序列长度的乘积最大，并输出这个最大值。

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

 Central Europe Regional Contest (CERC) 2013


title: [CERC2013] Subway

description:
Johny is going to visit his friend Michelle. His dad allowed him to go there on his own by subway. Johny loves traveling by subway and would gladly use this opportunity to spend half a day underground, but his dad obliged him to make as few line changes as possible. There are a lot of stations in the city, and several subway lines connecting them. All trains are perfectly synchronized $-$ the travel between two consecutive stations on every line takes exactly one minute, and changing lines at any station takes no time at all.

Given the subway map, help Johny to plan his trip so that he can travel for as long as possible, while still following his dad's order.

inputFormat:
First line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

The description of each test case starts with an empty line. The next two lines begin with the strings Stops: and Lines:, and contain the names (separated by a comma and a space) of all subway stops and lines, respectively. A single line for each subway line follows (in no particular order), beginning with route: and listing the names of the stops along this particular line. The final two lines specify the names of the (different) stations nearby Johny's and Michelle's homes.

In each test case, there are at most $300 000$ stations and $100 000$ lines, whose total length does not exceed $1 000 000$ . The names of lines and stations are between $1$ and $50$ characters long and can contain letters, digits, hyphens $(-),$ apostrophes $(‘)$ and `and` signs $(&).$ All lines are bidirectional (although changing the direction of travel counts as a line change) and there are no self-crossings.

outputFormat: Print the answers to the test cases in the order in which they appear in the input. For each test case, print a single line summarizing the optimal route Johny can take (see example output for exact format). You may assume that such a route always exists.

translation:
### 题目描述

$Johny$ 准备去拜访他的朋友 $Michelle$。他的父亲允许他乘地铁独自去那里。$Johny$ 喜欢乘地铁旅行，并很愿意用这次机会在地铁里呆上半天，但是父亲要求他尽量减少换乘次数。这个城市有很多地铁车站，并有几条地铁线路连接它们。所有列车都完全同步——在每条线上的两个连续地铁站点之间地铁行驶的时间恰好需要 $1$ 分钟，而在该城市的任何一个地铁站点上更改线路是不需要花费时间的。

现在 $Johny$ 有了该城市的地铁线路图，请帮助 $Johny$ 计划行程，以便他可以尽可能长时间的在地铁里呆着，同时还要尽量减少换乘次数。

### 输入格式

输入的第 $1$ 行为测试数据 $T$ 的数量。

每组测试数据均用空行分隔。接下来的两行以字符串以 $ Stops: $ 和  $Lines: $ 开头，并分别包含所有地铁站和线路的名称（以逗号和空格分隔）。每条地铁线路中的其中一条线路（不分先后）从 $route: $ 开始，并一一列出了该条线路的站点名称。最后两行给定了 $Johny$ 和 $Michelle$ 的家附近的车站的名称。

在每组测试数据中，最多有 $300000$ 个站点以及 $100000$ 条铁路线路，保证其总长度不超过 $1000000$；铁路线路和地铁站点的名称长度均在 $1$ 至 $50$ 个字符之间，其名称中可以含有字母、数字、连字符 `-`、引号 `'` 和特殊符号 `&`。所有的地铁线路都是双向的（改变行进方向即该条线路被改变），并保证没有自交叉。

### 输出格式

按照在输入中测试数据的顺序来输出每组测试数据的答案。对于每组测试用例，需输出一行来总结 Johny 可以采用的最佳路线（参见样例输出）。假设这样的线路始终存在。

### 输入输出样例

**输入 #1**

```txt
3

Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King'sCross, Arsenal
Johny lives at King'sCross
Michelle lives at GreenPark

Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King'sCross, Arsenal
Johny lives at PiccadillyCircus
Michelle lives at LeicesterSquare

Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King'sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King'sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King'sCross, Arsenal
Johny lives at Victoria
Michelle lives at HydeParkCorner
```

**输出 #1**

```txt
optimal travel from King'sCross to GreenPark: 1 line, 3 minutes
optimal travel from PiccadillyCircus to LeicesterSquare: 1 line, 1 minute
optimal travel from Victoria to HydeParkCorner: 2 lines, 7 minutes
```

### 说明 / 提示

时间限制：$8s$

内存限制：$256\texttt{MB}$

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


title: [CERC2013] Escape

description:
You hit the emperor lich with full force and slay it. There is a stair leading upwards here. You climb upstairs. You drink from the pool. You feel much better. The karmic lizard punches through your armor and hits you. You die...

After an epic fight with the emperor lich, the hero struggles to escape the dungeon consisting of $n$ chambers and $n − 1$ corridors connecting them. He starts in chamber number $1$ and must reach chamber number $t$ , moving only along the corridors. All chambers are reachable from chamber number $1$ . Bruised after the last fight, the hero starts the journey with $0$ hit-points $(HP).$ These points represent his health $-$ if ever they fall below zero, the hero's story ends there as a tragic one.

In some chambers there are monsters $-$ a monster must be fought, and it always manages to take some of the hero's HP. In some other chambers there are magic pools $-$ every pool restores some number of the hit-points. There is no upper limit on the hero's health. Every chamber can be visited multiple times, but the gain or loss of HP happens only once, on the very first visit.

Determine whether the hero can escape the dungeon alive.

inputFormat:
The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

The first line of each test case contains two integers: the number of chambers $n , 2 \le n \le 200 000$ , and the number of the exit chamber $t , 2 \le t \le n$ . The second line contains $n$ space separated integers between $-10^{6}$ and $10^{6} -$ the i-th of them denotes the HP gain in the i-th chamber (negative denotes a monster, positive $-$ a pool, and zero means that the chamber is empty). The first chamber does not contain a monster, but a pool is possible there. The exit chamber may contain a pool or a monster, and the monster will have to be fought before escaping.

The next $n−1$ lines contain the descriptions of corridors. Each one contains a pair of integers $-$ the ends of a corridor.

outputFormat: For each test case print a single line containing the word escaped if escape is possible, or trapped otherwise.

translation:
### 题目背景

在经历和巫妖王史诗级别的战斗后，英雄们想要从地牢中逃走。

### 题目描述

这个地牢是由 $n$ 个房间和 $n-1$ 条走廊连接组成的树状结构，英雄一开始在 $1$ 号房间，而且他只有抵达 $t$ 号房间才能逃离这个地牢。从 $1$ 号房间出发可以抵达任何一个其它的房间，可惜的是，在经历激烈的战斗后，英雄的精力使用完了，所以一开始该英雄的精力为 $0$，并且一旦英雄的精力低于 $0$，那么英雄就会当场逝世，以悲剧结束。在这些房间中，里面暗藏玄机，里面可能有怪兽，也有可能是可以补充精力的魔泉，当然也可能什么也没有，如果是怪兽，那么英雄就必须与它战斗从而消耗一些精力，如果是魔泉，那么英雄可以补充自己的精力。所有的怪兽只会战斗一次，所有的魔泉只能使用一次。（换句话说就是所有的精力的上升或者下降只会发生在第一次访问这个房间的时候）

英雄的精力没有上限，每一个房间都可以反复走多次。

### 输入格式

输入包括多组数据，第一行表示测试的数据的组数 $T$。

每一个测试用例的第 $1$ 行都包括两个整数 $n$ $(2 \le n \le 200000 )$ 和 $t$ $(2 \le t \le n)$，分别表示地牢的房间的数量和英雄必须到达的房间号。第二行是 $n$ 个整数，代表了 $n$ 个房间的情况，其中第 $i$ 个数代表了第 $i$ 个房间情况，所有的数的绝对值都不大于 $10^{6}$。如果该数是负数，表明该房间里面有怪兽，精力会减少，如果是正数，表明房间里面有魔泉，可以补充精力，如果是 $0$，表明房间里面空空如也。注意 $1$ 号房间不会有怪兽，但是有可能会有魔泉，$t$ 号房间可能怪兽或者魔泉，如果是怪兽，那么英雄必须要击败怪兽才能逃离。

在接下来的 $n-1$ 行中，每行两个整数 $a$ 和 $b$ ，表示房间 $a, b$ 之间有一条走廊连接。

### 输出格式

对于每一个测试用例都单行输出：

如果英雄能够逃脱，那么输出 `escaped`，否则输出 `trapped`。


title: [CERC2013] Draughts

description:
Draughts (or checkers) is a game played by two opponents, on opposite sides of a $10 \times 10$ board. The board squares are painted black and white, as on a classic chessboard. One player controls the dark, and the other the light pieces. The pieces can only occupy the black squares. The players make their moves alternately, each moving one of his own pieces.

The most interesting type of move is capturing: if a diagonally adjacent square contains an opponent's piece, it may be captured (and removed from the game) by jumping over it to the unoccupied square immediately beyond it. It is allowed to make several consecutive captures in one move, if they are all made with a single piece. It is also legal to capture by either forward or backward jumps.

![](/upload/images2/dr.png)

The board before and after a single move with two captures.

You are given a draughts position. It is the light player's turn. Compute the maximal possible number of dark pieces he can capture in his next move.

inputFormat:
The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

Each test case starts with an empty line. The following $10$ lines of $10$ characters each describe the board squares. The characters $#$ and . denote empty black and white squares, $W$ denotes a square with a light piece, $B -$ a square with a dark piece.

outputFormat: For each test case print a single line containing the maximal possible number of captures. If there is no legal move (for example, there are no light pieces on the board), simply output $0$ .

translation:
国际跳棋（或称跳棋）是一种由两个对手在 $10 \times 10$ 的棋盘上进行的游戏。棋盘上的方块是黑色或白色的，就像经典的国际象棋棋盘一样。玩家一方控制黑棋，另一方控制白棋。棋子只能占据黑色的格子。棋手们交替走棋，各自移动自己的一个棋子。

最有趣的走法是吃掉：如果一个对角线相邻的格子里有对手的棋子，可以通过跳过它到紧挨着它的未被占领的格子来吃掉（并从游戏中删除被吃掉的这个棋子）。允许在一步棋中用一个棋子连续吃掉几个棋子。通过向前或向后的跳跃来吃子也是合法的。

你会得到一个棋子的位置。现在轮到白方了。计算他在下一步棋中能吃掉的最大可能的黑棋数量。

输入格式

输入的第一行包含测试用例 $T$ 的数量。接下来是测试用例的描述。

每个测试用例以空行开始。接下来的 10 行，每行都有 10 个字符，描述棋盘的方格。字符 # 和 . 表示空的黑色和白色方块，W 表示有浅色棋子的方块，B 表示有深色棋子的方块。

输出格式

对于每个测试案例，输出一行一个整数，代表最多可以吃黑子的个数。如果没有合法的棋步（例如，棋盘上没有白棋），只需输出 0。


title: [CERC2013] History course

description:
You are to give a series of lectures on important historical events, one event per lecture, in some order. Each event lasted for some time interval $[a_i, b_i].$ We say that two events are related if their intervals have a common point. It would be convenient to schedule lectures on related events close to each other. Moreover, lectures on unrelated events should be given in the order in which the events have taken place (if an event A preceded an unrelated event $B$ , then the lecture on A should precede the lecture on $B)$ .

Find the minimum integer $k \ge 0$ and an order of the lectures such that any two related events are scheduled at most $k$ lectures apart from each other (lectures number $i$ and $j$ are considered to be $|i−j|$ lectures apart).

inputFormat:
The first line of input contains the number of test cases $t$ . The descriptions of the test cases follow:

The first line of each test case contains the number $n (1 \le n \le 50000)$ . Each of the next $n$ lines contains two integers $a_i$ and $b_i (-10^9  \le a_i \le b_i \le 10^9) $ - the ends of the i-th interval. The intervals are pairwise different.

outputFormat: Print the answers to the test cases in the order in which they appear in the input. The first line of the answer to each test case should contain the minimum value of $k$ . The next $n$ lines should list the intervals (in the same format as in the input) in an order such that any two related events are scheduled at most $k$ lectures apart. Remember to put any unrelated intervals in the proper order!

translation:
给定 $n$ 个区间，第 $i$ 个区间为 $[a_i,b_i]$。你需要把这些区间按某种顺序排列，使得两个区间如果没有交点，则左端点更小的区间需要排在前面。

设第 $i$ 个区间排在第 $p_i$ 个位置，定义区间 $i$ 与 $j$ 之间的距离为 $|p_i-p_j|$。令 $k$ 为任意两个相交的区间之间的最大距离，你需要最小化 $k$，并输出一组对应的合法顺序。

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times 10^4$，$0\leq|a_i|,|b_i|\leq10^9$。

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

感谢 [hht2006](/user/175829) 提供的 Special Judge。


title: [CERC2013] Chain & Co.

description:
Chain $&$ Co. specializes in producing infinitely strong chains. Because of their high quality products, they are quickly gaining market share. This leads to new challenges, some of which they could have never imagined before. Like, for example, automatic verification of link endurance with a computer program, which you are supposed to write.

The company produces links of equal size. Each link is an infinitely thin square frame in three dimensions (made of four infinitely thin segments).

During tests all links are $axis-aligned^{1}$ and placed so that no two frames touch. To make a proper strength test, two sets of links A and $B$ are forged so that every link of A is inseparable from every link of $B$ (being inseparable means that they cannot be moved apart without breaking one of them).

You stumble upon some links (axis-aligned, pairwise disjoint). Are they in proper testing position? In other words, can they be divided into two non-empty sets A and $B$ with the desired property?

$^{1}Axis-aligned$ means that all segments are parallel to either $X , Y$ , or $Z$ axis.

inputFormat:
The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

The description of each test case starts with an empty line. The next line contains an integer $n , 1 \le n \le 10^{6} -$ the number of links in the chain. Each of the next $n$ lines contains $6$ space separated integers $x_{i}, y_{i}, z_{i}, x_{i}', y_{i}', z_{i}',$ all between $-10^{9}$ and $10^{9} -$ the coordinates of two opposite corners of the i-th link.

outputFormat: For each test case, print a single line containing the word YES if the set is in proper testing position, or NO otherwise.

translation:
给定三维空间中 $n$ 个平行于坐标轴的空心 **正方形**，请判断是否有一种划分方案，使得所有矩形被划分为两个 **非空** 集合 $A,B$，且对于 $\forall i\in A,\forall j\in B$，矩形 $i,j$ 可以扣起来。

这里对“扣起来”的定义是：矩形 $A,B$ 各有一条边穿过另一个矩形，而它的对边则在另一个矩形外。可以尝试想象锁链环环相扣的样子。

不同矩形的边互不相交。多组数据，$n\le 10^6$。

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


title: [CERC2013] Crane

description:
There are $n$ crates waiting to be loaded onto a ship. The crates are numbered $1 , 2 , \cdots , n$ , the numbers determining the order of loading. Unfortunately, someone messed up the transit and the crates are standing in a row in an arbitrary order. As there is only limited space in the dock area, you must sort the crates by swapping some of them.

You are given a crane that works in the following way: you select a connected interval of crates of even length. The crane then exchanges the first half of the interval with the second half. The order inside both halves remains unchanged. Determine the sequence of crane moves that reorders the crates properly.

The crane's software has a bug: the move counter is a $9-based$ (not $10-based,$ as you might think) integer with at most $6$ digits. Therefore, the crane stops working (and has to be serviced) after $9^{6} = 531441$ moves. Your solution must fit within this limit.

inputFormat:
The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

Each test case starts with an integer $n , 1 \le n \le 10 000$ , denoting the number of crates. In the next line a permutation of numbers ${1 , 2 , \cdots $ , n} follows.

outputFormat: For each test case print a single line containing $m -$ the number of swaps $-$ followed by $m$ lines describing the swaps in the order in which they should be performed. A single swap is described by two numbers $-$ the indices of the first and the last element in the interval to be exchanged. Do not follow the crane's strange software design $-$ use standard decimal numeral system.

translation:
有 $n$ 个箱子等着装上船。箱子的编号是 $a_1,a_2,\cdots,a_n$。你的工作是通过若干次交换，将它们从小到大排列。你每次可以选择一个区间，将它的前半部分与后半部分交换，两半内部的顺序保持不变。你最多可以交换 $531441$ 次。

### 输入格式

第一行输入包含数据组数 $T$。

接下来 $2\times T$ 行，表示 $T$ 组数据。每组数据的第一行为 $n\ (1 \leq n \leq 10000)$，表示箱子的数量。第二行为 $n$ 个正整数$a_1,a_2,\cdots,a_n $ ，表示箱子的编号。

### 输出格式

对于每组数据，首先输出一个数 $m$ ，表示交换的次数。 然后输出 $m$ 行，按照顺序描述每一次交换。对于每次交换，输出要交换的区间中第一个元素和最后一个元素的下标。

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