“一家人杯”模拟赛 比赛环境适应赛 题目

大幕徐徐拉开……
为使参赛者熟悉本次NOIP提高组模拟赛的比赛环境，特举办比赛环境适应赛，给大家体验比赛平台的机会。比赛共有三题。由于本次比赛不是正式比赛，题量和难度和正式赛并不相同，时间也很宽松。
比赛时间：2010年5月31日，19:00:00 - 22:00:00。

单击此处提交你的程序。

特别说明：
一、文件名（程序名和输入输出文件名）必须使用小写。
二、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
三、统一评测时采用的机器参考配置为：CPU AMD 2.7GHz 双核，内存 2 GB，使用虚拟机环境测试。
四、关于使用Pascal语言与编译结果的说明
1．对于Pascal语言的程序，当使用IDE和fpc编译结果不一致时，以fpc的编译结果为准。
2．允许使用数学库(uses math子句)，以及ansistring。但不允许使用编译开关（最后测试时pascal的范围检查开关默认关闭：{$R-,Q-,S-}），也不支持与优化相关的选项。
五．关于C++语言中模板使用的限制说明
不作限制

题目一、神牛果 (时限:1 sec | 内存: 128 MB | 分值: 100 分)

【题目描述】
在某次膜拜大会上，一些神牛被要求集体膜拜。这些神牛被奖励每人吃一些神牛果。但是，每个神牛的肚量不一样。为了不显得某些人吃得太多，决定两人一组，使得吃得最多的那组吃得尽量少。（神牛数为偶数）
【输入格式】
第一行一个整数 n。(n<=10000)
第二行有 n 个正整数，为给定的一列数字，表示每个神牛能吃多少神牛果。(数字均小于 1000000000)
文件名为“1.in”。
【输出格式】
一个正整数，吃的最多的一组神牛吃的个数的最小值。
文件名为“1.out”。
【输入样例】

4
1 5 2 8
【输出样例】
9
单击此处提交你的程序。

题目二、四面楚歌 (时限:1 sec | 内存: 128 MB | 分值: 100 分)

【题目描述】
公元2008年10月31日星期五，笃志者所在的整个机房由于猖獗的病毒一片恐慌。经查证，病毒是由A1机器散播开来的。。这要追溯到29日，笃志者由于病毒被迫从A1机器撤离。
一想到病毒是从自己的机器传开的，笃志者就心神不宁。他决定搞清楚病毒是怎么散播开来的。事实上，机房内的机器并不是全部都能够互相感染的。笃志者（ceeji）好不容易经过测试得到了机房中各机器间是否连通的图表，就在他马上就要得出结果的时候，大脑突然乱了！问题的严重性在于：如果他不在1s内搞清楚这个问题，机房就会整体瘫痪。现在笃志者求助于你，他需要知道病毒从未感染机房开始，最少入侵几台机器之后，机房就会整体感染。
【输入格式】
文件的第一行为一个整数n，第二行至第n+1行为n*n的矩阵（若第i行第j列为1，则机器i能对机器j进行ARP攻击（即感染机器j），若第i行第j列为0，则机器i不能感染机器j）。
文件名为“2.in”。
【输出格式】
输出文件只有一行，为笃志者想知道的最少感染机器数。
文件名为“2.out”。
【输入样例】
8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0
【输出样例】
2
【数据范围】
对于 100% 的数据，n<=1000。
单击此处提交你的程序。

题目三、监考老师 (时限:1 sec | 内存: 128 MB | 分值: 100 分)

【题目描述】

上周四监考老师在你的帮助下一次性抓住了好多作弊的同学，Black对你相当不满，这次轮到你帮助Black和他的同学们作弊了……
而监考老师没有了你的帮助，决定这次的考试座位线形排列。但因为教室地方不够大，考场移到了地面凹凸不平的操场上。

Black和他的同学们坐成一竖列，毫无疑问每个人只能向前看，且只能看比自己位置低的人的卷子。Black昨天晚上花了整晚测量每个人座位所在的高度，现在需要休息。他想知道自己能看到的（只能向前看）最近的同学座位所在的高度，但是睡着前他忘了告诉你他的位置了！没办法，你必须计算出所有位置的结果。

【输入格式】

数据的第一行是一个正整数n，表示一共有多少个座位。
第二行有n个用空格隔开的正整数，它们从前至后给出了n个座位的高度。这些数保证小于2^31。

文件名为“3.in”。
【输出格式】

输出一行用空格隔开的n个数，这些数对应输入数据中的座位的结果。如果输入中某个座位无法作弊（即它前边的座位都不比它低），请输出0。

文件名为“3.out”。
【输入样例】
7
3 1 2 7 6 7 4

【输出样例】
0 0 1 2 2 6 2
【数据范围】
对于100%的数据，n<=1000 000。

单击此处提交你的程序。