「一家人杯」模擬賽 比賽環境適應賽 題目

大幕徐徐拉開……
為使參賽者熟悉本次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。

單擊此處提交你的程序。