網(wǎng)上找的一些試題省選day

2005年安聯(lián)杯安徽省青少年信息學(xué)奧林匹克競賽 一試試題六安，2005.5.21 第PAGE5/4頁2005年安聯(lián)杯安徽省青少年信息學(xué)奧林匹克競賽注意事項(xiàng)務(wù)必看清題目，嚴(yán)格按照所要求的格式輸入、輸出。在調(diào)試程序時(shí)請先使用題目中的示例數(shù)據(jù)，然后再自行設(shè)計(jì)多組測試數(shù)據(jù)進(jìn)行調(diào)試。測試有嚴(yán)格的時(shí)間限制，請盡可能優(yōu)化算法。命名規(guī)則：

(1)每題都規(guī)定了該題的英文名稱。

(2)程序文件和數(shù)據(jù)文件的主文件名都是該題的英文名字。

(3)程序文件擴(kuò)展名采用語言環(huán)境的默認(rèn)擴(kuò)展名。

(4)數(shù)據(jù)文件都是文本文件，輸入和輸出文件的擴(kuò)展名分別是.in和.out。程序應(yīng)從輸入文件讀取數(shù)據(jù)，并嚴(yán)格地按照規(guī)定的輸出格式將結(jié)果輸出到輸出文件中。輸入數(shù)據(jù)文件和輸出數(shù)據(jù)文件都與程序在同一個(gè)目錄中，由于程序所在目錄是不確定的，因此不允許在程序中含有盤符信息和任何形式的路徑信息。選手在競賽結(jié)束時(shí)應(yīng)在軟磁盤上建立以參賽號命名的文件夾，提交所完成各題的源程序文件和編譯所產(chǎn)生的可執(zhí)行文件(即擴(kuò)展名為.exe的文件)到該文件夾中。并在硬盤指定位置留有備份。題目洗牌（SHUFFLE）為了表彰小聯(lián)為Samuel星球的探險(xiǎn)所做出的貢獻(xiàn)，小聯(lián)被邀請參加Samuel星球近距離載人探險(xiǎn)活動。由于Samuel星球相當(dāng)遙遠(yuǎn)，科學(xué)家們要在飛船中度過相當(dāng)長的一段時(shí)間，小聯(lián)提議用撲克牌打發(fā)長途旅行中的無聊時(shí)間。玩了幾局之后，大家覺得單純玩撲克牌對于像他們這樣的高智商人才來說太簡單了。有人提出了撲克牌的一種新的玩法。對于撲克牌的一次洗牌是這樣定義的，將一疊N（N為偶數(shù)）張撲克牌平均分成上下兩疊，取下面一疊的第一張作為新的一疊的第一張，然后取上面一疊的第一張作為新的一疊的第二張，再取下面一疊的第二張作為新的一疊的第三張……如此交替直到所有的牌取完。如果對一疊6張的撲克牌123456，進(jìn)行一次洗牌的過程如下圖所示：

a.初始狀態(tài) b.分成兩疊d.一次洗牌后 c.洗牌從圖中可以看出經(jīng)過一次洗牌，序列123456變?yōu)?15263。當(dāng)然，再對得到的序列進(jìn)行一次洗牌，又會變?yōu)?46135。游戲是這樣的，如果給定長度為N的一疊撲克牌，并且牌面大小從1開始連續(xù)增加到N（不考慮花色），對這樣的一疊撲克牌，進(jìn)行M次洗牌。最先說出經(jīng)過洗牌后的撲克牌序列中第L張撲克牌的牌面大小是多少的科學(xué)家得勝。小聯(lián)想贏取游戲的勝利，你能幫助他嗎？輸入：輸入文件中有三個(gè)用空格間隔的整數(shù)，分別表示N，M，L（其中0＜N≤1010，0≤M≤1010，且N為偶數(shù)）。輸出：單行輸出指定的撲克牌的牌面大小。樣例：輸入：623輸出： 6 病毒檢測（VIRUS）科學(xué)家們在Samuel星球上的探險(xiǎn)仍在繼續(xù)。非常幸運(yùn)的，在Samuel星球的南極附近，探險(xiǎn)機(jī)器人發(fā)現(xiàn)了一個(gè)巨大的冰湖！機(jī)器人在這個(gè)冰湖中搜集到了許多RNA片段運(yùn)回了實(shí)驗(yàn)基地?？茖W(xué)家們經(jīng)過幾個(gè)晝夜的研究，發(fā)現(xiàn)這些RNA片段中有許多是未知的病毒！每個(gè)RNA片段都是由A、C、T、G組成的序列。科學(xué)家們也總結(jié)出了Samuel星球上的“病毒模版片段”。一個(gè)模版片段是由A、C、T、G的序列加上通配符*和?來表示。其中*的意思是可以匹配上0個(gè)或任意多個(gè)字符，而?的意思是匹配上任意一個(gè)字母。如果一個(gè)RNA片段能夠和“病毒模版片段”相匹配，那么這個(gè)RNA片段就是未知的病毒。例如，假設(shè)“病毒模版片段”為A*G?C。RNA片段：AGTC，AGTGTC都是未知的病毒，而RNA片段AGTGC則不是病毒。由于，機(jī)器人搜集的這些RNA片段中除去病毒的其他部分都具有非常高的研究價(jià)值。所以科學(xué)家們希望能夠分辨出其中哪些RNA片段不是病毒，并將不是病毒的RNA片段運(yùn)回宇宙空間站繼續(xù)進(jìn)行研究?？茖W(xué)家將這項(xiàng)任務(wù)交給了小聯(lián)?，F(xiàn)在請你為小聯(lián)編寫程序統(tǒng)計(jì)哪些RNA片段不是病毒。輸入：第一行有一個(gè)字符串，由A、C、T、G、*、?組成。表示“病毒模版片段”?！安《灸０嫫巍钡拈L度不超過1000。第二行有一個(gè)整數(shù)N（0<N<500），表示機(jī)器人搜集到的RNA片段的數(shù)目。隨后的N行，每一行有一個(gè)字符串，由A、C、T、G組成，表示一個(gè)RNA片段。每個(gè)RNA片段的長度不超過500。注意：“病毒模版片段”和RNA片段的長度都至少為1。輸出：只有一行輸出，為整數(shù)M，即不是病毒的RNA片段的數(shù)目。樣例：輸入：A*G?C3AGTCAGTGTCAGTGC輸出：1輸出說明：輸入中的RNA片段AGTGC不是病毒。穿越磁場（CROSS）探險(xiǎn)機(jī)器人在Samuel星球上尋找一塊奇特的礦石，然而此時(shí)它陷入了一片神秘的磁場區(qū)域，動彈不得。探險(xiǎn)空間站立刻掃描了這片區(qū)域，繪制出該區(qū)域的磁場分布平面圖。這片區(qū)域中分布了N個(gè)磁場，每個(gè)磁場呈正方形，且邊與坐標(biāo)軸平行。例如下圖中，存在3個(gè)磁場，白點(diǎn)表示機(jī)器人的位置，黑點(diǎn)表示礦石的位置：XYOXYO例如下面的兩種情形是不會出現(xiàn)的：科學(xué)家們給探險(xiǎn)機(jī)器人啟動了磁力罩，這樣它就可以在磁場中自由穿越了。初始時(shí)，探險(xiǎn)機(jī)器人和所有礦石都不在任何磁場的邊緣。由于技術(shù)限制，在穿越過程中機(jī)器人只能夠水平或垂直移動，且不能夠沿著磁場的邊緣行動。由于磁力罩的能量有限，科學(xué)家們希望探險(xiǎn)機(jī)器人穿越盡量少的磁場邊緣采集到這塊礦石。例如上圖中，探險(xiǎn)機(jī)器人最少需要穿越兩次磁場邊緣?，F(xiàn)在小聯(lián)請你編寫程序，幫助科學(xué)家們設(shè)計(jì)探險(xiǎn)機(jī)器人的路線，統(tǒng)計(jì)探險(xiǎn)機(jī)器人最少需要穿越多少次磁場邊緣。輸入：第一行有一個(gè)整數(shù)N，表示有N個(gè)磁場（1<N<100）。隨后有N行，每行有三個(gè)整數(shù)X、Y、C（0<X,Y,C<10000），表示一個(gè)磁場左下角坐標(biāo)為（X,Y），邊長為C。接下來有一行，共有四個(gè)整數(shù)SX,SY,TX,TY，表示機(jī)器人初始坐