提高组
（请选手务必仔细阅读本页内容）
一．题目概况
| 中文题目名称 | 修补管道 | 跳跃 | 叠箱子 | 神奇的项链 | Ships |
| 英文题目与子目录名 | pipe | jump | box | fett | ships |
| 可执行文件名 | pipe | jump | box | fett | ships |
| 输入文件名 | pipe.in | jump.in | box.in | fett.in | ships.in |
| 输出文件名 | pipe.out | jump.out | box.out | fett.out | ships.out |
| 每个测试点时限 | 1 秒 | 1 秒 | 1 秒 | 1 秒 | 1 秒 |
| 测试点数目 | 10 | 10 | 10 | 10 | 10 |
| 每个测试点分值 | 10 | 10 | 10 | 10 | 10 |
| 附加样例文件 | 有 | 有 | 有 | 有 | 有 |
| 结果比较方式 | 全文比较（过滤行末空格及文末回车） | ||||
| 题目类型 | 传统 | 传统 | 传统 | 传统 | 传统 |
| 对于pascal 语言 | pipe.pas | jump.pas | box.pas | fett.pas | ships.pas |
| 对于c 语言 | pipe.c | jump.c | box.c | fett.c | ships.c |
| 对于c++ 语言 | pipe.cpp | jump.cpp | box.cpp | fett.cpp | ships.cpp |
| 对于pascal 语言 | fpc pipe.pas | fpc jump.pas | fpc box.pas | fpc fett.pas | fpc ships.pas |
| 对于c 语言 | gcc -o pipe pipe.c -lm | gcc -o jump jump.c -lm | gcc -o box box.c -lm | gcc -o fett fett.c -lm | gcc -o ships ships.c -lm |
| 对于c++ 语言 | g++ -o pipe pipe.cpp -lm | g++ -o jump jump.cpp -lm | g++ -o box box.cpp -lm | g++ -o fett fett.cpp -lm | g++ -o ships ships.cpp -lm |
| 内存上限 | 128M | 128M | 128M | 128M | 128M |
1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3、统一评测时采用的机器配置为：CPU P4 3.0GHz，内存 2G，上述时限以此配置为准。
4、特别提醒：评测在Windows下进行，评测软件为cena8.0。
修补管道
(pipe.pas/c/cpp)
【题目描述】
被分成n*m的格子，两个城市M和Z之间的天然气通过管道相连，管道有以下几种形态：
天然气从城市M运送到城市Z，管道是双向的，且对于Block +,天然气必须在两个方向都有流动。如图：
现在有一个格子的管道消失了，你的任务就是找到这个格子以及管道的类型。
【输入格式】
第一行两个数n,m，中间用一个空格隔开；以下 n行，每行m个字符。
'.'表示空格，'|'，'-'，'+'，'1'，'2'，'3'，'4'表示管道的类型。
M、Z表示起点和终点。
数据保证只有一个管道口和M、Z相邻，这个管道设计中没有废弃管道（也就是说所有管道都必须使用),数据保证答案存在且唯一。
【输出格式】
一行，前两个数表示管道位置，后一个字符表示管道类型。
即（行，列，管道类型），中间用一个空格隔开。
【样例输入1】
3 7
.......
.M-.-Z.
.......
【样例输出1】
2 4 -
【样例输入2】
3 5
..1-M
1-+..
Z.23.
【样例输出2】
2 4 4
【数据规模】
对于100%的数据：1≤n,m≤25；
跳跃
(jump.pas/c/cpp)
【题目描述】
跳跃是笨笨的天性,当然跳需要消耗能量，每跳1米就会消耗1点能量，如果笨笨有很多能量就能跳很高。
笨笨为了收集能量，来到百亩森林的一个神秘地方。在这里，笨笨的正上方每100米处就有一个能量球（也就是这些能量球位于海拔100，200，300……米处），每个能量球所能提供的能量是不同的，一共有N个能量球（也就是最后一个能量球在N×100米处）。笨笨为了想收集能量，想跳着吃完所有的能量球。笨笨可以自由控制他每次跳的高度，接着他跳起把这个高度以下的能量球都吃了，他便能获得能量球内的能量，接着吃到的能量球消失。当然笨笨的跳跃技能还不够高，还不会二级跳，所以不能因新吃到的能量而变化此次跳跃的高度，并且每次跳完都会掉下来，回到地面。
问笨笨若要吃完所有的能量球，最多还能保留多少能量。
【输入格式】
输入文件第1行包含两个正整数N，M，表示了能量球的个数和笨笨的初始能量。
第2行包含N个非负整数，从左到右第I个数字依次从下向上描述了位于I×100米位置能量球包含的能量，每2个整数之间用1个空格隔开。
【输出格式】
输出文件仅包括一个非负整数，为笨笨吃完所有能量球后最多保留的能量。
【样例输入】
3 200
200 200 200
【样例输出】
400
【样例说明】
第1次跳100米，得到200能量，消耗100能量，所以落地后拥有300能量。
第2次跳300米，吃到剩下的第2棵能量球，消耗拥有的300能量，得到400能量。
若第1次跳200米，第2次跳300米，最后剩余300能量。
【数据规模】
对于10%的数据：有N≤10；
对于20%的数据：有N≤100；
对于40%的数据：有N≤1,000；
对于70%的数据：有N≤100,000；
对于100%的数据：有N≤2,000,000；
保证对于所有数据，笨笨都能吃到所有的能量球，并且能量球包含的能量之和不超过231-1。
叠箱子
(box.pas/c/cpp)
【题目描述】
笨笨有N个重量为1的无盖空箱子，每个箱子有长和宽，那么长宽小的箱子就可以放进长宽大的箱子里。现在笨笨要通过把箱子放进其他箱子中来制造一个最重的箱子，请你告诉笨笨一个箱子最多能有多少重。
假设箱子i的长为Ai，宽为Bi。那么箱子i能放进箱子j的条件就是Ai 第一行1个整数N，表示箱子个数。 之后N行，每行2个整数Ai、Bi，表示箱子的长宽。 【输出格式】 一个整数，表示最重的箱子的重量。 【样例输入1】 4 9 10 10 9 1 8 0 0 【样例输出1】 3 【样例输入2】 7 1 2 2 4 2 5 3 3 4 5 5 4 6 5 【样例输出2】 4 【数据规模】 对于10%的数据: 1≤N≤10； 对于40%的数据: 1≤N≤1,000； 对于100%的数据: 1≤N≤500,000； 0≤Ai,Bi≤1,000,000； 神奇的项链 (fett.pas/c/cpp) 【题目描述】 笨笨有一条神奇的项链，为什么说它神奇呢？因为它有两个性质： 1. 神奇的项链可以拉成一条线，线上依次是N个珠子，每个珠子有一个能量值Ei； 2. 除了第一个和最后一个珠子，其他珠子都满足Ei=(Ei-1+Ei+1)/2+Di。 由于这条项链很长，我们只能知道其两端珠子的能量值。并且我们知道每个珠子的Di是多少。请聪明的你求出这N个珠子的能量值分别是多少。 【输入格式】 第一行三个整数N、E1、EN，表示珠子个数N，第一个珠子和第N个珠子的能量值。 第二行N-2个整数，表示第2个珠子到第N-1个珠子的Di。 【输出格式】 输出仅一行，N个整数，表示1到N个这N个珠子各自的能量值Ei。每2个整数之间用1个空格隔开；请放心，数据保证对于任意珠子满足(Ei-1+Ei+1)Mod 2=0； 【样例输入1】 4 1 4 0 0 【样例输出1】 1 2 3 4 【样例输入2】 10 1 29 0 2 -3 5 1 4 2 -1 【样例输出2】 1 13 25 33 47 51 53 47 37 29 【数据规模】 对于40%的数据: 1 (ships.pas/c/cpp) 【题目描述】 告诉你一个n*n的正方形。正方形里只有0和1。问你由1组成的不同大小的极大4连通块（有公共边）分别有多少。 【输入格式】 第一行一个整数n表示正方形的大小（左上角为(1,1))。 接下来n行，每行有一些用','分隔的区间，表示在该行上哪些区间值为1。以';'结束。对于每个区间的描述，如果区间的大小为1，那么仅用一个数字表示。如果区间大小大于1，那么用"st-en"描述。st为区间开始的列号。en为区间结束的列号。-为分隔符。 【输出格式】 输出含有若干行。你应该按照连通块的大小降序输出。对于每一行，你需要输出两个整数a，b，分别表示连通块的大小和这种大小的连通块的个数，a,b之间用1个空格隔开。 【样例输入】 12 2-4,7,9; 1,4,11-12; 1,4,10,12; 1,4-8,10-12; 1,8; 1,3-6,8,10-12; 1,3,5-6,8,11; 1,8,10-12; 1-8; ; 2; 2-4,7-10,12; 【样例输出】 29 1 7 3 4 2 1 3 【数据规模】 保证只有不超过1,000个连通块。保证每个连通块大小不超过1,000； 对于30%的数据：1≤n≤2,000； 对于100%的数据：1≤n≤30,000；下载本文
