宁波市第25届中小学生计算机程序设计竞赛
复赛试题（初中组）
比赛时间：2010年4月18日上午9:00—12:00
题目一览
试题名称 | 折纸 | 幻灯片 | 插入排序 | 军训整队 |
英文代号 | folding | slide | inrt | lineup |
程序名 | folding.pas/c/cpp | slide.pas/c/cpp | inrt.pas/c/cpp | lineup.pas/c/cpp |
输入文件名 | folding.in | slide.in | inrt.in | lineup.in |
输出文件名 | folding.out | slide.out | inrt.out | lineup.out |
内存限制 | 128 MB | 128 MB | 128 MB | 128 MB |
时限 | 1秒 | 1秒 | 1秒 | 1秒 |
| | | | |
关于竞赛中不同语言使用限制的说明
一．关于使用Pascal语言与编译结果的说明
1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。
2．允许使用数学库(us math子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。
3．本次比赛允许使用64位整数类型：int64或qword。
二．关于C++语言中模板使用的限制说明
1．允许使用的部分：
标准容器中的布尔集合，迭代器，串，流。
相关的头文件：<bitt> <iterator> <string> <iostream>
2．禁止使用的部分：
序列：vector，list，deque
序列适配器：stack, queue, priority_queue
关联容器：map, multimap, t, multit
拟容器：valarray
散列容器：hash_map, hash_t, hash_multimap, hash_multit
所有的标准库算法
相关头文件：<vector> <list> <deque> <stack> <map> <t> <algorithm>
3．本次比赛允许使用64位整数：long long或unsigned long long。
1. 折纸 (folding)
【题目描述】
小猪上幼儿园的时候，报名参加了折纸兴趣小组。他表现出了极大的热情，折出了n件折纸作品。他的作品只有3种，分别是长方形、正方形和直角三角形。
小猪很想知道他的n件折纸的周长之和、面积之和。
【输入】
输入文件folding.in的第一行只有一个整数n，表示共有n件作品。
接下来n行，每行有若干个以空格分隔的整数，表示一件作品的情况。其中第一个整数k（k=1或2或3），表示小猪制造的这件作品的类型，1表示长方形，2表示正方形，3表示直角三角形。
如果k为1，后面会跟二个正整数，表示长方形的二条相邻边的长度；
如果k为2，后面会跟一个正整数，表示正方形的边长。
如果k为3，后面会跟三个正整数，表示直角三角形三条边的长度（输入数据保证三条边能构成直角三角形）。
【输出】
输出文件folding.out中仅有一行，该行有二个整数（互相之间以一个空格分隔），表示所有作品的周长之和以及面积之和。
【样例输入】
3
1 2 3
2 4
3 4 3 5
【样例输出】
38 28
【数据规模】
50%的数据，1≤n≤10，所有边长为不超过50的正整数。
80%的数据，1≤n≤11000，所有边长为不超过200的正整数。
100%的数据，1≤n≤100000，所有边长为不超过10000的正整数。
2. 幻灯片 (slide)
【题目描述】
小猪桌上有n张透明的矩形幻灯片。幻灯片的四条边都平行于坐标轴，但是幻灯片的大小不一定相同。现在定义n张幻灯片的公共面积是被这n张幻灯片都覆盖住的面积，也就是在这个公共部分里，每一个点都在所有幻灯片的内部或边上。
小猪想要抽出某张幻灯片，使得剩下的(n - 1)张幻灯片的公共面积最大。请帮他计算出抽出某张幻灯片后剩余幻灯片公共面积的最大值。
【输入】
输入文件slide.in的第一行只有一个整数n，表示共有n张幻灯片。
接下来n行，每行有四个整数x1、y1、x2、y2（互相之间以一个空格分隔），表示一张幻灯片矩形的左上角坐标是(x1,y1)，右下角坐标是(x2, y2)。保证x1<x2，y1<y2。
【输出】
输出文件slide.out中仅有一行，该行只有一个整数，表示抽出某张幻灯片后剩余幻灯片公共面积的最大值。
【样例输入】
3
0 0 4 3
1 1 3 4
2 2 5 5
【样例输出】
4
【数据规模】
20%的数据，2≤n≤10;
80%的数据，2≤n≤100，所有幻灯片左上角、右下角的坐标的绝对值不超过10000;
100%的数据，2≤n≤100000，所有幻灯片左上角、右下角的坐标的绝对值不超过100000000。数据保证本题输出结果不会超过2000000000。
3. 插入排序 (inrt)
【题目描述】
有依次排列的一列数a1,a2,a3,…,an-1,an。你可以随便把一个数拿出，插到最前面(当前第1个数a1前)、最后面(当前最后一个数an后面)、或者剩余数列中任意的相邻两个数之间。
比如起始数依次为4 5 6 7 8 9。如果把第4个数a4=7拿出，然后任意放回，可能有
7 4 5 6 8 9
4 7 5 6 8 9
4 5 7 6 8 9
4 5 6 7 8 9
4 5 6 8 7 9
4 5 6 8 9 7
这6种排列。
已知把第i个数ai拿出后插回去花费的代价为该数的值ai。小猪希望花费最少的代价来把这个数列排成不降序列。所谓不降序列，是指对于数列中任意两个数，排在前面的数小于等于排在后面的数。
【输入】
输入文件inrt.in的第一行只有一个整数n，表示共有n个整数。
