NIOP2005復(fù)賽試題.pdf

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