公告公告 NOIP2005NOIP2005NOIP2005NOIP2005 復賽提高組試題復賽提高組試題 第十一屆全國青少年奧林匹克信息學聯賽復賽提高組試題 提高組 三小時完成 誰拿了最多獎學金 scholar pas c cpp 問題描述 某校的慣例是在每學期的期末考試之后發放獎學金 發放的獎學金共有五種 獲取的條件各自不 同 1 院士獎學金 每人 8000 元 期末平均成績高于 80 分 80 并且在本學期內發表 1 篇或 1 篇以上論文的學生均可獲得 2 五四獎學金 每人 4000 元 期末平均成績高于 85 分 85 并且班級評議成績高于 80 分 80 的學生均可獲得 3 成績優秀獎 每人 2000 元 期末平均成績高于 90 分 90 的學生均可獲得 4 西部獎學金 每人 1000 元 期末平均成績高于 85 分 85 的西部省份學生均可獲 得 5 班級貢獻獎 每人 850 元 班級評議成績高于 80 分 80 的學生干部均可獲得 只要符合條件就可以得獎 每項獎學金的獲獎人數沒有限制 每名學生也可以同時獲得多項獎學 金 例如姚林的期末平均成績是 87 分 班級評議成績 82 分 同時他還是一位學生干部 那么 他可以同時獲得五四獎學金和班級貢獻獎 獎金總數是 4850 元 現在給出若干學生的相關數據 請計算哪些同學獲得的獎金總數最高 假設總有同學能滿足獲得 獎學金的條件 輸入文件 輸入文件 scholar in 的第一行是一個整數N 1 N 100 表示學生的總數 接下來的 N 行每行是一位學生的數據 從左向右依次是姓名 期末平均成績 班級評議成績 是否是學生 干部 是否是西部省份學生 以及發表的論文數 姓名是由大小寫英文字母組成的長度不超過 20 的字符串 不含空格 期末平均成績和班級評議成績都是 0 到 100 之間的整數 包括 0 和 100 是否是學生干部和是否是西部省份學生分別用一個字符表示 Y 表示是 N 表示不是 發表的論文數是 0 到 10 的整數 包括 0 和 10 每兩個相鄰數據項之間用一個空格分隔 輸出文件 輸出文件 scholar out 包括三行 第一行是獲得最多獎金的學生的姓名 第二行是這名學生獲得 的獎金總數 如果有兩位或兩位以上的學生獲得的獎金最多 輸出他們之中在輸入文件中出現最 早的學生的姓名 第三行是這 N 個學生獲得的獎學金的總數 樣例輸入 4 YaoLin 87 82 YN0 ChenRuiyi 88 78NY 1 LiXin 92 88N N0 ZhangQin 83 87 YN1 樣例輸出 ChenRuiyi 9000 28700 過河 river pas c cpp 問題描述 在河上有一座獨木橋 一只青蛙想沿著獨木橋從河的一側跳到另一側 在橋上有一些石子 青蛙 很討厭踩在這些石子上 由于橋的長度和青蛙一次跳過的距離都是正整數 我們可以把獨木橋上 青蛙可能到達的點看成數軸上的一串整點 0 1 L 其中 L 是橋的長度 坐標為 0 的 點表示橋的起點 坐標為 L 的點表示橋的終點 青蛙從橋的起點開始 不停的向終點方向跳躍 一次跳躍的距離是 S 到 T 之間的任意正整數 包括 S T 當青蛙跳到或跳過坐標為 L 的點時 就算青蛙已經跳出了獨木橋 題目給出獨木橋的長度 L 青蛙跳躍的距離范圍 S T 橋上石子的位置 你的任務是確定青蛙要 想過河 最少需要踩到的石子數 輸入文件 輸入文件 river in 的第一行有一個正整數 L 1 L 109 表示獨木橋的長度 第二行有 三個正整數 S T M 分別表示青蛙一次跳躍的最小距離 最大距離 及橋上石子的個數 其 中 1 S T 10 1 M 100 第三行有 M 個不同的正整數分別表示這 M 個 石子在數軸上的位置 數據保證橋的起點和終點處沒有石子 所有相鄰的整數之間用一個空格 隔開 輸出文件 輸出文件 river out 只包括一個整數 表示青蛙過河最少需要踩到的石子數 樣例輸入 10 2 3 5 2 3 5 6 7 樣例輸出 2 數據規模 對于 30 的數據 L 10000 對于全部的數據 L 109 篝火晚會 fire pas c cpp 問題描述 佳佳剛進高中 在軍訓的時候 由于佳佳吃苦耐勞 很快得到了教官的賞識 成為了 小教官 在軍訓結束的那天晚上 佳佳被命令組織同學們進行篝火晚會 一共有 n 個同學 編號從 1 到 n 一開始 同學們按照 1 2 n 的順序坐成一圈 而實際上每個人都有兩個最希望相鄰的 同學 如何下命令調整同學的次序 形成新的一個圈 使之符合同學們的意愿 成為擺在佳佳面 前的一大難題 佳佳可向同學們下達命令 每一個命令的形式如下 b1 b2 bm 1 bm 這里 m 的值是由佳佳決定的 每次命令 m 的值都可以不同 這個命令的作用是移動編號是 b1 b2 bm 1 bm 的這 m 個同學的位置 要求 b1 換到 b2 的位置上 b2 換到 b3 的位置 上 要求 bm 換到 b1 的位置上 執行每個命令都需要一些代價 我們假定如果一個命令要移動 m 個人的位置 那么這個命令的 代價就是m 我們需要佳佳用最少的總代價實現同學們的意愿 你能幫助佳佳嗎 輸入文件 輸入文件 fire in 的第一行是一個整數 n 3 n 50000 表示一共有 n 個同學 其后 n 行每行包括兩個不同的正整數 以一個空格隔開 分別表示編號是 1 的同學最希望相鄰的兩個 同學的編號 編號是 2 的同學最希望相鄰的兩個同學的編號 編號是 n 的同學最希望相鄰 的兩個同學的編號 輸出文件 輸出文件 fire out 包括一行 這一行只包含一個整數 為最小的總代價 如果無論怎么調整都 不能符合每個同學的愿望 則輸出 1 樣例輸入 4 3 4 4 3 1 2 1 2 樣例輸出 2 數據規模 對于 30 的數據 n 1000 對于全部的數據 n 50000 等價表達式 equal pas c cpp 問題描述 明明進了中學之后 學到了代數表達式 有一天 他碰到一個很麻煩的選擇題 這個題目的題干 中首先給出了一個代數表達式 然后列出了若干選項 每個選項也是一個代數表達式 題目的要 求是判斷選項中哪些代數表達式是和題干中的表達式等價的 這個題目手算很麻煩 因為明明對計算機編程很感興趣 所以他想是不是可以用計算機來解決這 個問題 假設你是明明 能完成這個任務嗎 這個選擇題中的每個表達式都滿足下面的性質 1 表達式只可能包含一個變量 a 2 表達式中出現的數都是正整數 而且都小于 10000 3 表達式中可以包括四種運算 加 減 乘 乘冪 以及小括號 小括號的優先級最高 其次是 然后是 最后是 和 和 的優先級是相同的 相 同優先級的運算從左到右進行 注意 運算符 以及小括號 都是英文字 符 4 冪指數只可能是 1 到 10 之間的正整數 包括 1 和 10 5 表達式內部 頭部或者尾部都可能有一些多余的空格 下面是一些合理的表達式的例子 a 1 2 3 a a a a a a 9999 a a a 1 a 1 3 1 10 9 輸入文件 輸入文件 equal in 的第一行給出的是題干中的表達式 第二行是一個整數 n 2 n 26 表示選項的個數 后面 n 行 每行包括一個選項中的表達式 這 n 個選項的標號分別是 A B C D 輸入中的表達式的長度都不超過 50 個字符 而且保證選項中總有表達式和題干中的表達式是等 價的 輸出文件 輸出文件 equal out 包括一行 這一行包括一系列選項的標號 表示哪些選項是和題干中的表 達式等