宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 1 页 共 7 页
宁波市第25届中小学生计算机程序设计竞赛
复赛试题（初中组）
比赛时间：2010年4月18日上午9:00—12:00
题目一览
试题名称 英文代号 程序名 输入文件名 输出文件名 内存限制 时限 折纸 folding folding.in folding.out 128 MB 1秒 幻灯片 slide slide.in slide.out 128 MB 1秒 插入排序 insert insert.pas/c/cpp insert.in insert.out 128 MB 1秒 军训整队 lineup lineup.pas/c/cpp lineup.in lineup.out 128 MB 1秒 folding.pas/c/cpp slide.pas/c/cpp 关于竞赛中不同语言使用限制的说明
一．关于使用Pascal语言与编译结果的说明
1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。 2．允许使用数学库(uses math子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。
3．本次比赛允许使用64位整数类型：int64或qword。
二．关于C++语言中模板使用的限制说明
1．允许使用的部分：
标准容器中的布尔集合，迭代器，串，流。
相关的头文件：
序列适配器：stack, queue, priority_queue 关联容器：map, multimap, set, multiset 拟容器：valarray
散列容器：hash_map, hash_set, hash_multimap, hash_multiset 所有的标准库算法
相关头文件：
? 宁波市计算机学会，2010
宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 2 页 共 7 页
1. 折纸 (folding)
【题目描述】
小猪上幼儿园的时候，报名参加了折纸兴趣小组。他表现出了极大的热情，折出了n件折纸作品。他的作品只有3种，分别是长方形、正方形和直角三角形。
小猪很想知道他的n件折纸的周长之和、面积之和。
a
b a b
a a a
a
b c a
相邻边长度分别为a和b的长方形,周长为2a+2b，面积为a*b
边长为a的正方形,周长为4a，面积为a*a
直角边长度分别为a,b，斜边长度为c的直角三角形,周长为a+b+c，面积为ab/2
【输入】
输入文件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
? 宁波市计算机学会，2010
宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 3 页 共 7 页
【样例输出】
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 【输出】 输出文件slide.out中仅有一行，该行只有一个整数，表示抽出某张幻灯片后剩余幻灯片公共面积的最大值。 0 1 2 3 4 5 1 2 3 4 5 x 【样例输入】 3 0 0 4 3 1 1 3 4 2 2 5 5 【样例输出】 4 y ? 宁波市计算机学会，2010 宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 4 页 共 7 页 【数据规模】 20%的数据，2≤n≤10; 80%的数据，2≤n≤100，所有幻灯片左上角、右下角的坐标的绝对值不超过10000; 100%的数据，2≤n≤100000，所有幻灯片左上角、右下角的坐标的绝对值不超过100000000。数据保证本题输出结果不会超过2000000000。 3. 插入排序 (insert) 【题目描述】 有依次排列的一列数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。小猪希望花费最少的代价来把这个数列排成不降序列。所谓不降序列，是指对于数列中任意两个数，排在前面的数小于等于排在后面的数。 【输入】 输入文件insert.in的第一行只有一个整数n，表示共有n个整数。 第2行有n个整数（互相之间以一个空格分隔），表示待排序的n个数。 【输出】 输出文件insert.out中只有一行，该行只有一个整数，表示花费的最小代价。 【样例输入】 4 ? 宁波市计算机学会，2010 宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 5 页 共 7 页 7 1 2 3 【样例输出】 6 【样例说明】 很显然移动7是不划算的。一种移动方法是： 初始情况：7 1 2 3 => (把3移到最前面得) 3 7 1 2 => (把1移到最前面得) 1 3 7 2 => (把2移到1与3之间得) 1 2 3 7 最终整个序列成为升序。 消耗的代价是3 + 1 + 2 = 6。 【数据规模】 30%的数据初始数列是1至n的一个排列，即1至n都在初始数列出现且仅出现一次； 20%的数据，1≤n≤10； 90%的数据，1≤n≤1000； 100%的数据,1≤n≤100000,初始数列的每个数在1和20000之间(包括1和20000)。 【提示】 不需要移动的数之间符合什么规律呢？ 4. 军训整队 (lineup) 【题目描述】 小猪军训的时候，同学们需要排成一个n * m的方阵。 每个同学都可以用(x,y)表示他应该排的位置，比如(2,3)的同学被安排在第2行第3列。A教官要求同学们最后排成的形状应该如下表所示： (1,1) (2,1) (3,1) …… (n,1) (1,2) (2,2) (3,2) …… (n,2) (1,3) (2,3) (3,3) …… (n,3) …… …… …… …… …… (1,m) (2,m) (3,m) …… (n,m) 上级领导要检查A教官的编队能力，于是就发了个大招把A教官的方阵给打乱了（将n行 ? 宁波市计算机学会，2010