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

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

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

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

4、和別人殺價很有規(guī)律。設(shè)此人第i次報價為Wi元，那么他第i+1次報的價格為WiA或Wi B。到了最后，TENSHI以Z元成交，高高興興的回家去了。任 務(wù) ：求TENSHI把盆竹的價格由W1元殺到Z元的方法總數(shù)。輸入格式：輸入文件第一行有兩個正整數(shù)W1和Z。第二行有兩個正整數(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é)科競賽的失敗以后，得到了一個真理：做一題就要對一題

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

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