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

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

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

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

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

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

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

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