綜合材料tv講義網(wǎng)絡(luò)流練習(xí)2ctsc99

1、1999 IOI選拔賽 第一天 第5頁 共5頁IOI99選拔賽試題（第一天）考試時(shí)間：4小時(shí)試題目錄題號試題名分值Problem A01統(tǒng)計(jì) (Bin)100Problem B補(bǔ)丁vs錯(cuò)誤 (Bugs)100Problem C家園 (Homeland)100注意事項(xiàng)選手必須嚴(yán)格按照題目要求的文件名提交文檔；選手提交的文檔包括：源程序文件；編譯后的可執(zhí)行文件；選手的程序必須嚴(yán)格符合題目要求的輸入輸出方式和格式。 所有題目的輸入文本文件名均為INPUT.TXT 所有題目的輸出文本文件名均為OUTPUT.TXT01統(tǒng)計(jì)(BIN.EXE)近來IOI的專家們在進(jìn)行一項(xiàng)有關(guān)二進(jìn)制數(shù)的研究，研究涉及的一個(gè)統(tǒng)

2、計(jì)問題令他們大傷腦筋。問題是這樣的：對于一個(gè)自然數(shù)n，可以把它轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)，其中：；而且ai=0或1（）,ak=1。如：；。我們統(tǒng)計(jì)一下a0 ak這k+1個(gè)數(shù)中0的個(gè)數(shù)和1的個(gè)數(shù)。如果在這k+1個(gè)數(shù)中，0的個(gè)數(shù)比1的個(gè)數(shù)多，就稱n為A類數(shù)?，F(xiàn)在的任務(wù)是，對于一個(gè)給定的m，求1m中A類數(shù)的個(gè)數(shù)。輸入：輸入文件中只有一個(gè)自然數(shù)m（）。輸出：輸出文件也只有一個(gè)自然數(shù)：1m中A類數(shù)的個(gè)數(shù)。輸入輸出示例： 輸入文件 輸出文件 3 0補(bǔ)丁vs錯(cuò)誤(BUGS.EXE)錯(cuò)誤就是人們所說的Bug。用戶在使用軟件時(shí)總是希望其錯(cuò)誤越少越好，最好是沒有錯(cuò)誤的。但是推出一個(gè)沒有錯(cuò)誤的軟件幾乎不可能，所以很多軟件

3、公司都在瘋狂地發(fā)放補(bǔ)?。ㄓ袝r(shí)這種補(bǔ)丁甚至是收費(fèi)的）。T公司就是其中之一。上個(gè)月，T公司推出了一個(gè)新的字處理軟件，隨后發(fā)放了一批補(bǔ)丁。最近T公司發(fā)現(xiàn)其發(fā)放的補(bǔ)丁有致命的問題，那就是一個(gè)補(bǔ)丁在排除某些錯(cuò)誤的同時(shí)，往往會加入另一些錯(cuò)誤. 此字處理軟件中只可能出現(xiàn)n個(gè)特定的錯(cuò)誤，這n個(gè)錯(cuò)誤是由軟件本身決定的。T公司目前共發(fā)放了m個(gè)補(bǔ)丁，對于每一個(gè)補(bǔ)丁, 都有特定的適用環(huán)境，某個(gè)補(bǔ)丁只有在當(dāng)前軟件中包含某些錯(cuò)誤而同時(shí)又不包含另一些錯(cuò)誤時(shí)才可以使用，如果它被使用，它將修復(fù)某些錯(cuò)誤而同時(shí)加入某些錯(cuò)誤。另外，使用每個(gè)補(bǔ)丁都要耗一定的時(shí)間（即補(bǔ)丁程序的運(yùn)行時(shí)間）。更準(zhǔn)確地說明：設(shè)此字處理軟件中可能出現(xiàn)的n個(gè)錯(cuò)誤

4、為集合B=b1,b2,bn中的元素，T公司目前共發(fā)放了m個(gè)補(bǔ)丁：p1，p2,pm。對于每一個(gè)補(bǔ)丁pi, 都有特定的適用環(huán)境，某個(gè)補(bǔ)丁只有在軟件中包含某些錯(cuò)誤而同時(shí)又不包含另一些錯(cuò)誤時(shí)才可以用，為了說明清楚，設(shè)錯(cuò)誤集合：Bi+、 Bi-， 當(dāng)軟件包含了Bi+中的所有錯(cuò)誤, 而沒有包含Bi-中的任何錯(cuò)誤時(shí)，補(bǔ)丁Pi才可以被使用，否則不能使用，顯然 Bi+、Bi-交集為空。補(bǔ)丁pi將修復(fù)某些錯(cuò)誤而同時(shí)加入某些錯(cuò)誤，設(shè)錯(cuò)誤集合Fi-、Fi+，使用過補(bǔ)丁pi之后，F(xiàn)i-中的任何錯(cuò)誤都不會在軟件中出現(xiàn)，而軟件將包含F(xiàn)i+中的所有錯(cuò)誤， 同樣Fi-、Fi+交集為空。另外，使用每個(gè)補(bǔ)丁都要耗一定的時(shí)間（即補(bǔ)丁

5、程序的運(yùn)行時(shí)間）?，F(xiàn)在T公司的問題很簡單，其字處理軟件的初始版本不幸地包含了集合B中的全部n個(gè)錯(cuò)誤, 有沒有可能通過使用這些補(bǔ)?。ㄈ我忭樞虻厥褂?，一個(gè)補(bǔ)丁可使用多次）， 使此字處理軟件成為一個(gè)沒有錯(cuò)誤的軟件。如果可能，希望找到總耗時(shí)最少的方案。輸入：輸入文件第一行有兩個(gè)正整數(shù)n和m, n表示錯(cuò)誤總數(shù)，m表示補(bǔ)丁總數(shù)，1=n=20, 1=m=100。接下來m行給出了m個(gè)補(bǔ)丁的信息。每行包括一個(gè)正整數(shù)（表示此補(bǔ)丁程序pi的運(yùn)行耗時(shí)）和兩個(gè)長度為n的字符串，中間用一個(gè)空格符隔開。第一個(gè)字符串，如果第k個(gè)字符為+，則表示bk屬于Bi+, 若為-，則表示bk屬于Bi-, 若為0，則bk 既不屬于Bi+也

6、不屬于Bi-，即軟件中是否包含bk不影響補(bǔ)丁pi是否可用。第二個(gè)字符串，如果第k個(gè)字符為+，則表示bk屬于Fi+, 若為-，則表示bk屬于Fi-, 若為0，則bk 既不屬于Fi+也不屬于Fi-，即軟件中是否包含bk不會因使用補(bǔ)丁pi而改變。輸出： 輸出一個(gè)整數(shù)，如果問題有解，輸出總耗時(shí)，否則輸出0。輸入輸出示例:輸入文件3 31 000 00-1 00- 0-+2 0- -+輸出文件8家 園(HOMELAND.EXE)由于人類對自然的瘋狂破壞，人們意識到在大約2300年之后，地球不能再居住了，于是在月球上建立了新的綠地，以便在需要時(shí)移民。令人意想不到的是，2177年冬由于未知的原因，地球環(huán)境發(fā)

7、生了連鎖崩潰，人類必須在最短的時(shí)間內(nèi)遷往月球?，F(xiàn)有n個(gè)太空站處于地球與月球之間（編號1.n），m艘公共交通太空船在其中來回穿梭，每個(gè)太空站Si可容納無限的人，每艘太空船pi只可容納Hpi人。對于每一艘太空船pi，將周期性地?？恳幌盗械奶照荆⊿i1,Si2Sir），如：（1，3，4）表示?？刻照? 3 4 1 3 4 1 3 4 。 任一艘太空船從任一個(gè)太空站駛往另一個(gè)任意的太空站耗時(shí)為1。人只能在太空船?？刻照荆ɑ虻厍?、月球）時(shí)上船或下船。初始時(shí)的人全在地球上，太空船全在初始站（太空船pi處于Si1），目標(biāo)是讓所有的人盡快地全部轉(zhuǎn)移到月球上。輸入：文件第一行為三個(gè)正整數(shù) n（太空站個(gè)數(shù)）、 m（太空船個(gè)數(shù)）、 k（需要運(yùn)送的地球上的人的個(gè)數(shù)），其中 1=m=13, 1=n=20, 1=k=50。接下來的n行給出了太空船的信息，第i+1行說明太空船pi，此行第一個(gè)數(shù)表示pi可容納的人數(shù)Hpi，第二個(gè)數(shù)表示pi停靠一個(gè)周期的太空站個(gè)數(shù)r，1=r=n, 隨后r個(gè)數(shù)便是?？康奶照镜木幪?Si1,Si2,Sir), 地球用0表示，月球用-1表示。0時(shí)刻時(shí)，所有太空船都在初始站，隨后開始運(yùn)行，在時(shí)刻1，2，3等正點(diǎn)時(shí)刻各艘太