山東信息學(xué)奧賽選拔賽第一試

1、山東省信息學(xué)奧賽選拔賽第一試試題(2005 年 5 月 3 日)1Antiprime 數(shù)（ANT.PAS）如果一個(gè)自然數(shù) n（n=1），滿足所有小于 n 的自然數(shù)（=1）的約數(shù)個(gè)數(shù)都小于 n 的約數(shù)個(gè)數(shù)，則 n 是一個(gè) Antiprime 數(shù)。譬如：1, 2, 4, 6, 12, 24。任務(wù)：編一個(gè)程序：1、 從 ANT.IN 中讀入自然數(shù) n。2、 計(jì)算不大于 n 的最大 Antiprime 數(shù)。3、將結(jié)果輸出到 ANT.OUT 中。輸入( ANT.IN)：輸入文件 ANT.IN 只有一個(gè)整數(shù)，n（1 = n = 2 000 000 000）。輸出(ANT.OUT):輸出文件 ANT.OUT

2、 也只包含一個(gè)整數(shù)，即不大于 n 的最大 Antiprime 數(shù)。樣例輸入( ANT.IN):1000樣例輸出(ANT.OUT)：8402高速公路（Highway.PAS）問題描述:京珠高速公路目前正在建設(shè)當(dāng)中。粵北地區(qū)是世界著名的“丹霞地貌”，京珠在這里必須穿過一大片復(fù)雜的山區(qū)。工程的Bonny 已經(jīng)規(guī)劃好了公路大致的，而工程師們則被派往各個(gè)多山的路段，以設(shè)計(jì)這些路段的具體規(guī)劃?，F(xiàn)在，你因?yàn)樵谛畔W(xué)上取得的出色成就，被 Bonny 派往一個(gè)稱為 DreadfulMess 的最復(fù)雜的路段，并僅僅給了你一張地圖和一些數(shù)據(jù)。坐標(biāo)系描述，其中包括這一地區(qū)的所有山峰的數(shù)據(jù)（俯視圖）及兩個(gè)點(diǎn) A、B。每

3、地圖以的輪廓被假想為四邊形，工程師們把這些四邊形的頂點(diǎn)稱為“測(cè)量點(diǎn)” ，這些四邊形不會(huì)發(fā)生、包含，但有可能有共用的一段邊或頂點(diǎn)。山以外的區(qū)域被認(rèn)為是平地。你的任務(wù)是計(jì)算此路段山區(qū)的總面積，并設(shè)計(jì)一條公路，從 A 點(diǎn)起始，到 B 點(diǎn)終止。設(shè)計(jì)的原則是：公路是一條折線（即轉(zhuǎn)彎點(diǎn)的個(gè)數(shù)是有限的）；公路可以修在平地上、沿山腳或山谷（即兩的結(jié)合部），也可以打隧道；隧道口不能是轉(zhuǎn)彎點(diǎn)，除非它又是測(cè)量點(diǎn)；修建公路的費(fèi)用最小。費(fèi)用的計(jì)算：平地、沿山腳或山谷的修路費(fèi)用為 u0，各修隧道的費(fèi)用為 ui。輸入 (Highway.in)：第一、二行分別為 A、B 點(diǎn)坐標(biāo)，整數(shù)。第三行為 u0，正整數(shù)。第四行為山峰數(shù)

4、n，0=n=50。以下共 n 行，每行首先是一個(gè)正整數(shù) ui，然后是 8 個(gè)整數(shù)，按逆時(shí)針方向給出表示山的四邊形的頂點(diǎn)坐標(biāo)。輸入數(shù)據(jù)保證 A、B 兩點(diǎn)不會(huì)在任何山的數(shù)的絕對(duì)值不會(huì)大于 1000。，四邊形任意 3 個(gè)頂點(diǎn)不在同一直線上，所有的整坐標(biāo)均以整數(shù)對(duì)的形式給出，第一個(gè)數(shù)為橫坐標(biāo)，第二個(gè)為縱坐標(biāo)。同一行內(nèi)若有多個(gè)相鄰整數(shù)，則整數(shù)間以至少一個(gè)空格隔開。輸出 (Highway.out)：第一行為這個(gè)區(qū)域山的總面積。第二行為設(shè)計(jì)公路的總長。第三行為修建所設(shè)計(jì)公路的費(fèi)用。輸出數(shù)據(jù)均保留兩位小數(shù)。輸入輸出樣例Highway.in-10 110 11002110 0 0 -5 5 -10 0 -5 -

5、5300 5 -5 10 0 5 5 0 0Highway.out 100.0021.932252.153.(VIR.PAS)_問題描述：二進(jìn)制碼中不存在任何一段最近發(fā)現(xiàn)了如下的規(guī)律：某些確定的二進(jìn)制串是的代碼。如果某段代代碼，那么就稱這段代碼是安全的?，F(xiàn)在已經(jīng)找出了所有的代碼段，試問，是否存在一個(gè)無限長的安全的二進(jìn)制代碼。示例：例如如果011, 11, 00000為代碼段，那么一個(gè)可能的無限長安全代碼就是 010101。如果01,11, 000000為代碼段，那么就不存在一個(gè)無限長的安全代碼。任務(wù)：請(qǐng)寫一個(gè)程序：在文本文件 WIR.IN 中讀入代碼；判斷是否存在一個(gè)無限長的安全代碼；將結(jié)果輸

6、出到文件 WIR.OUT 中。輸入格式（WIR.IN）：在文本文件 WIR.IN 的第一行包括一個(gè)整數(shù) n，表示代碼段的數(shù)目。以下的 n 行每一行都包代碼段的總長度不超過 30000。括一個(gè)非空的 01 字符串就是一個(gè)輸出格式（WIR.OUT）：代碼段。所有在文本文件 WIR.OUT 的第一行輸出一個(gè)單詞：TAK假如存在這樣的代碼；NIE如果不存在。樣例:輸入（WIR.IN）：3011100000輸出（WIR.OUT）：NIE4.動(dòng)物園(Sle.pas)問題描述（背景）：位于郊區(qū)的動(dòng)物園很早就采用了當(dāng)時(shí)先進(jìn)的自動(dòng)化管理設(shè)施對(duì)動(dòng)物進(jìn)行管理。但是由于當(dāng)時(shí)的系統(tǒng)沒有考慮 2000 年問題，使得管理十

7、分擔(dān)心。雖然采取了很多防范措施，系統(tǒng)還是在世紀(jì)之交出現(xiàn)了一些 BUG，部分動(dòng)物的籠子門自動(dòng)打開了，關(guān)在里面的動(dòng)物都跑出來了。幸好動(dòng)物園已經(jīng)關(guān)閉，動(dòng)物不會(huì)跑出動(dòng)物園。警長 Still 接到后率領(lǐng)一支干警奔赴現(xiàn)場(chǎng)。這時(shí)動(dòng)物已經(jīng)跑出了籠子，所以干警們花了很多時(shí)間才控制住了，所有的動(dòng)物都己經(jīng)送到動(dòng)物園的廣場(chǎng)。但是此時(shí)有一個(gè)棘手，由于系統(tǒng)完全，無法得知?jiǎng)游锸菑哪膫€(gè)籠子里面跑出來的。此時(shí)，干警們記得動(dòng)物的一些行動(dòng)，都是如下的形式：第 t 分鐘看到某某動(dòng)物在某個(gè)位置Still 希望通過這些零碎的信息得到動(dòng)物是從哪個(gè)籠子跑出來的。任務(wù)：根據(jù)給出的信息，編程求出每個(gè)動(dòng)物的籠子的位置。動(dòng)物園的地形描述為一個(gè) n

8、* n 的網(wǎng)格，一個(gè)格子可以是建筑物或者平地?；\子的位置只可能在平地，動(dòng)物也只在平地運(yùn)動(dòng)。每種動(dòng)物的奔跑速度不一樣，例如一分鐘可以跑 5 個(gè)格子，貓一分鐘只可以跑 2 個(gè)格子等等。以下是一個(gè)例子（其中陰影部分是建筑物）：每個(gè)籠子只關(guān)一只動(dòng)物，不同的籠子關(guān)不同的動(dòng)物。不同的籠子可能在同一個(gè)格子里。輸入格式(Sle.In)：第一行為自然數(shù) n，表示網(wǎng)格的邊長(n = 100)籠子籠子以下 n 行為一個(gè) n*n 的字符串矩陣，表示動(dòng)物園的地形。其中.表示空地，*表示建筑物。接著一行是自然數(shù) p，表示籠子的數(shù)目（同時(shí)也是動(dòng)物的數(shù)目）。P = 100以下 p 行，每行兩個(gè)自然數(shù) Row, Col，表示一個(gè)籠子處于網(wǎng)格的第 Row 行，第 Col 列。Row = nCol = n以下 p 行，每行一個(gè)整數(shù) Vi，依次表示號(hào)表示。為 i 的動(dòng)物的速度（格子/分鐘），每個(gè)動(dòng)物用它的編接著一行是自然數(shù) r，表示干警們提供的信息數(shù)目。以下 r 行，每行 4 個(gè)自然數(shù)，t, Row, Col, j，表示第t 分鐘在網(wǎng)格的(Row, Col)位置看到動(dòng)物 j .具體格式參照樣例。輸出格式