NIOP2005復(fù)賽試題.pdf

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