全國青少年信息學(xué)(計(jì)算機(jī))奧林匹克分區(qū)聯(lián)賽提高組復(fù)賽模擬試題一

1、全國青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽提高組復(fù)賽模擬試題一（3小時(shí),滿分400分）說明：1.嚴(yán)格按照題目所要求的格式進(jìn)行輸入、輸出，否則嚴(yán)重影響得分。2.題目測試數(shù)據(jù)有嚴(yán)格的時(shí)間限制5s，超時(shí)不得分。3.輸入文件格式不用判錯(cuò);從輸入文件讀入數(shù)據(jù)，輸入文件名在程序中從鍵盤讀入， 計(jì)算結(jié)果輸出到屏幕。4.程序完成后，要按指定的提交文件名編譯成EXE文件，指定的文件名如下：問題A: 天使的起誓（TENSHI NO YUBIKILI）問題描述：TENSHI非常幸運(yùn)的被選為掌管智慧之匙的天使。在正式任職之前，她必須和其他新當(dāng)選的天使一樣，要宣誓。宣誓儀式是每位天使各自表述自己的使命，她們的發(fā)言稿被放

2、在N個(gè)呈圓形排列的寶盒中。這些寶盒按順時(shí)針方向被編上號(hào)碼、N-1、N。一開始天使們站在編號(hào)為N的寶盒旁。她們各自手上都有一個(gè)數(shù)字，代表她們自己的發(fā)言稿所在的盒子是從號(hào)盒子開始按順時(shí)針方向的第幾個(gè)。例如：有個(gè)盒子，那么如果TENSHI手上的數(shù)字為，那么她的發(fā)言稿所在盒子就是第個(gè)?，F(xiàn)在天使們開始按照自己手上的數(shù)字來找發(fā)言稿，先找到的就可以先發(fā)言。TENSHI一下子就找到了，于是她最先上臺(tái)宣誓：“我將帶領(lǐng)大家開啟NOI之門”TENSHI宣誓結(jié)束以后，陸續(xù)有天使上臺(tái)宣誓?？梢杂幸晃惶焓拐伊撕镁枚颊也坏剿陌l(fā)言稿，原來她手上的數(shù)字M非常大，她轉(zhuǎn)了好久都找不到她想找的寶盒。任 務(wù)：請(qǐng)幫助這位天使找到她想找

3、的寶盒的編號(hào)。輸入格式：輸入文件有兩行分別正整數(shù)N和M，其中N、M滿足81000 2 N 10，2 M 10輸出格式：文件只有一行即寶盒的編號(hào)樣例二問題B: 步步高升（Step by Step）問題描述：春節(jié)的時(shí)候TENSHI去逛花市。她來到一個(gè)賣盆竹的攤位，看到一盆叫做“步步高升”的盆竹?！安讲礁呱?，步步高升”學(xué)習(xí)就是要一步一步來，不能急，要打好基礎(chǔ)。在穩(wěn)固的基礎(chǔ)上才談得上步步高升！TENSHI若有所思。她看到這盆東西好意頭，于是想買下。誰知一問價(jià)錢，“不貴不貴，才?！盩ENSHI差點(diǎn)沒昏倒，囊中羞澀嘛。但是TENSHI還是很想買下來，于是她就在一旁觀察。觀察了一段時(shí)間，她發(fā)現(xiàn)這個(gè)賣盆竹的人

4、和別人殺價(jià)很有規(guī)律。設(shè)此人第i次報(bào)價(jià)為Wi元，那么他第i+1次報(bào)的價(jià)格為WiA或Wi B。到了最后，TENSHI以Z元成交，高高興興的回家去了。任 務(wù) ：求TENSHI把盆竹的價(jià)格由W1元?dú)⒌絑元的方法總數(shù)。輸入格式：輸入文件第一行有兩個(gè)正整數(shù)W1和Z。第二行有兩個(gè)正整數(shù)A和B。它們滿足條件：10 W1 106，1 Z 106 ，Z < W12 A 、B 10000，AB輸出格式：將方法總數(shù)輸出，只有一行。注意：結(jié)果不超過MAXLONGINT樣例二問題C: 競賽真理（Truth of Contest）問題描述：TENSHI在經(jīng)歷了無數(shù)次學(xué)科競賽的失敗以后，得到了一個(gè)真理：做一題就要對(duì)一題

5、！但是要完全正確地做對(duì)一題是要花很多時(shí)間（包括調(diào)試時(shí)間），而競賽的時(shí)間有限。所以開始做題之前最好先認(rèn)真審題，估計(jì)一下每一題如果要完全正確地做出來所需要的時(shí)間，然后選擇一些有把握的題目先做。 當(dāng)然，如果做完了預(yù)先選擇的題目之后還有時(shí)間，但是這些時(shí)間又不足以完全解決一道題目，應(yīng)該把其他的題目用貪心之類的算法隨便做做，爭取“騙”一點(diǎn)分?jǐn)?shù)。任 務(wù) ：根據(jù)每一題解題時(shí)間的估計(jì)值，確定一種做題方案（即哪些題目認(rèn)真做，哪些題目“騙”分，哪些不做），使能在限定的時(shí)間內(nèi)獲得最高的得分，輸入格式：輸入文件的第一行有兩個(gè)正整數(shù)N和T，表示題目的總數(shù)以及競賽的時(shí)限（單位秒）。以下的N行，每行個(gè)正整數(shù)W1i 、T1i

6、、W2i 、T2i ，分別表示第i題：完全正確做出來的得分，完全正確做出來所花費(fèi)的時(shí)間（單位 秒），“騙”來的分?jǐn)?shù)，“騙”分所花費(fèi)的時(shí)間（單位秒）。其中，3 N 30，2 T 30000，1 W1i 、W2i 1000，1 T1i 、T2i T。輸出格式：直接把所能得到的最高分值輸出只有一行。樣例一樣例二問題D: 標(biāo)點(diǎn)符號(hào)（Punctuation Mark）問題描述：有一天，TENSHI發(fā)現(xiàn)了一本叫Road to NOI的書。這本書是用英語寫的，奇怪的是這本書完全沒有標(biāo)點(diǎn)符號(hào)，也沒有空格！也就是說這本書整篇都是由一連串字母組成的。TENSHI研究了一會(huì)，發(fā)現(xiàn)了一種斷句的方法：1)單詞是由字母組成的，并且都可以在天使字典（和魔鬼字典相對(duì)的）找到，且這些單詞是不區(qū)分大小寫的（也就是說TenShi和tenshi是一個(gè)單詞）2)每個(gè)單詞的長度不超過。3)句子是由至少三個(gè)單詞組成的，并且這些單詞的字母總數(shù)是這些單詞個(gè)數(shù)的倍數(shù)。例如：iwanttoseeheragain 可以看成是這樣一句話：I want to see her again. 因?yàn)閱卧~數(shù)為，且字母總數(shù)為，是的倍數(shù)。4)句子的第一個(gè)字母不一定要是大寫字母。5)每個(gè)句子的字母總數(shù)不超過。任 務(wù) ：給出一個(gè)字典以及一串字母，請(qǐng)為這串字母劃分句子，使句子總數(shù)最多。輸入格式：輸入文件的第一行為一個(gè)正整數(shù)