試題dayIOI99選拔賽第二天

1、IOI99 選拔賽試題（第二天）時(shí)間：4 小時(shí)試題目錄注意事項(xiàng)選手必須嚴(yán)格按照題目要求的文件名提交文檔；選手提交的文檔包括：1.源程序文件；2.編譯后的可執(zhí)行文件；選手的程序必須嚴(yán)格符合題目要求的輸入輸出方式和格式。所有題目的輸入文本文件名均為 INPUT.TXT所有題目的輸出文本文件名均為 OUTPUT.TXT題號(hào)試題名分值Problem A數(shù)字(Game)100Problem B月亮之眼 (Moon)100Problem C拯救大兵(Rescue)100數(shù)字（GAME.EXE）80 年代全世界流行一種數(shù)字稱為“24 點(diǎn)”。現(xiàn)，把這種在把這個(gè)有趣的推廣一下：您作為者將得到 6 個(gè)不同的自然數(shù)

2、作為操作數(shù)，以及另外一個(gè)自然數(shù)作為理想目標(biāo)數(shù)，而您的任務(wù)是對(duì)這 6 個(gè)操作數(shù)進(jìn)行適當(dāng)?shù)乃阈g(shù)運(yùn)算，要求運(yùn)算結(jié)果小于或等于理想目標(biāo)數(shù)，并且果是最優(yōu)的，即結(jié)果要最接近理想目標(biāo)數(shù)。希望所得結(jié)您可以使用的運(yùn)算只有：+，-，*，/，您還可以使用（）來(lái)改變運(yùn)算順序。注意：所有的中間結(jié)果必須是整數(shù)，所以一些除法運(yùn)算是不允許的（例如，（2*2）/4 是合法的，2*（2/4）是不合法的）下面給出一個(gè)的具體例子：若給出的 6 個(gè)操作數(shù)是：1，2，3，4，7 和 25；理想目標(biāo)數(shù)是 573，則最優(yōu)結(jié)果是 573：（4*25-1）*2）-7）*3。輸入:輸入文件僅一行，包含 7 個(gè)整數(shù)，前 6 個(gè)整數(shù)Mi,1=Mi=1

3、00，表示操作數(shù)，最后一個(gè)整數(shù)T,1=T=1000,表示理想目標(biāo)數(shù)。輸出:輸出文件有兩行，第一行僅一個(gè)整數(shù)，表示您計(jì)算得到的最優(yōu)結(jié)果。第二行是一個(gè)表達(dá)式，即您得到的最優(yōu)結(jié)果的運(yùn)算方案。輸入輸出示例：輸入文件1 2 3 4 7 25 573輸出文件573(4*25-1)*2)-7)*3月亮之眼(MOON.EXE)，由于她經(jīng)營(yíng)有道，小店開得紅紅火火。昨天，是一家古董店的無(wú)意之中得到了散落民間幾百年的珍寶月亮之眼。深知“月亮之眼”價(jià)值連城：它是由許多珍珠相連而成的，工匠們用金線連接珍珠，每根金線連接兩個(gè)珍珠；同時(shí)又對(duì)每根金線染上兩種顏色，一半染成銀白色，一半染成黛黑色。由于自小熟讀古籍，所以還曉得“

4、月亮之眼”的神秘：“月亮之眼”原是一個(gè)古代寺廟的寶物，原本是掛在佛堂的一根頂梁柱上的，整個(gè)寶物垂直懸掛，所有珍珠排成一線，且都鑲嵌在柱子里，而每一根金線又都是繃緊的，并且金線的銀白色一端始終在黛黑色一端的上方；然而，在一個(gè)月圓之夜，“月亮之眼”突然從柱里飛出，掉落下來(lái)，寶物本身完好無(wú)損，只是僧侶們?cè)僖矡o(wú)法以原樣把“月亮之眼”嵌入柱子中了。望著這個(gè)神秘的寶物，回憶著童年讀到的，頓時(shí)萌發(fā)出恢復(fù)“月亮之眼”的沖動(dòng)，但是擺弄了幾天依舊沒有成功?，F(xiàn)在，要麻煩您來(lái)幫助完成這項(xiàng)使命。您要設(shè)計(jì)一個(gè)程序，對(duì)于給定的“月亮之眼”進(jìn)行周密分析，然后給出這串寶物幾百年前嵌在佛堂頂梁柱上的排列模樣。給定的“月亮之眼”有

5、 N 個(gè)珍珠和P 根金線，所有珍珠按一定順序有了一個(gè)序號(hào)：1、2、N。輸入輸入數(shù)據(jù)包含一個(gè)“月亮之眼”的特征描述：文件第一行有兩個(gè)整數(shù)N 和P，其中 N 表示寶物中的珍珠個(gè)數(shù)，P 表示寶物中的金線根數(shù)；以下P 行描述珍珠連接情況：文件第I+1 行有三個(gè)整數(shù)，Ri1,Ri2,Li。其中 Ri1 表示第I 根金線的銀白色一端連接的珍珠序號(hào)；Ri2 表示第 I 根金線的黛黑色一端連接的珍珠序號(hào)；Li表示第I 根金線的長(zhǎng)度。輸出由于珍珠尺寸很小，所以幾個(gè)珍珠可以同時(shí)鑲嵌在一個(gè)位置上。您的輸出數(shù)據(jù)描述的是“月亮之眼”各個(gè)珍珠在頂梁柱上的位置，輸出文件共N 行：第 I 行，一個(gè)整數(shù) S，它表示標(biāo)號(hào)為 I

6、的珍珠在頂梁柱上距離最的距離。注意：若無(wú)解則輸出僅一行，包含一個(gè)整數(shù)“-1”。輸入輸出示例輸入文件9 91 2 32 3 52 7 14 5 45 6 1置珍珠5 9輸出文件510045695參數(shù)限定1=N=255拯救大兵(RESCUE.EXE)1944 年，特種兵麥克接到國(guó)防部令，要求立即趕赴太平洋上的一個(gè)孤被關(guān)押在一個(gè)迷宮里，迷宮地形復(fù)雜，但島，營(yíng)救被敵軍俘虜?shù)拇蟊Ｊ切液名溈说玫搅嗣詫m的地形圖。迷宮的外形是一個(gè)長(zhǎng)方形，其在南北方向被劃分為 N 行，在東西方向被劃分為M 列，于是整個(gè)迷宮被劃分為 N*M 個(gè)單元。用一個(gè)有序數(shù)對(duì)（單元的行號(hào)，單元的列號(hào)）來(lái)表示單元位置。南北或東西方向相鄰的兩

7、個(gè)單元之間可以互通，或者存在一扇鎖著的門，又或者存在一堵不可逾越的墻。迷宮中有一些單元存放著，并且所有的門被分為 P 類，打開同一類的門的同類的門的不同。大兵被關(guān)押在迷宮的東南角，即（N,M）單元里，并已經(jīng)相同，打開不。迷宮只有一個(gè)，在西北角，也就是說，麥克可以直接進(jìn)入(1,1)單元。另外，麥克從一個(gè)單元移動(dòng)到另一個(gè)相鄰單元的時(shí)間為 1，拿取所在單元的開門的時(shí)間忽略不計(jì)。的時(shí)間以及用你的任務(wù)是幫助麥克以最快的方式抵達(dá)所在單元，營(yíng)救大兵。輸入：第一行是三個(gè)整數(shù)，依次表示 N,M,P 的值；第二行是一個(gè)整數(shù)K，表示迷宮中門和墻的總個(gè)數(shù)；第I+2 行（1=I=1 時(shí)，表示(Xi1,Yi1)單元與(Xi2,Yi2)單元之間有一扇第 Gi 類的門，當(dāng) Gi=0 時(shí)，表示(Xi1,Yi1)單元與(Xi2,Yi2)單元之間有一堵不可逾越的墻；（其中，|Xi1-Xi2|+|Yi1-Yi2|=1，0=Gi=P）第 K+3 行是一個(gè)整數(shù)S，表示迷宮中存放的總數(shù)；第 K+3+J 行(1=J=S)，有 3 個(gè)整數(shù)，依次為 Xi1,Yi1,Qi：表示第 J 把存放在(Xi1,Yi1)單元里，并且第 J 把是用來(lái)開啟第 Qi 類門的。（其中 1=Qi=P）注意：輸入數(shù)據(jù)中同一行各相鄰整數(shù)之間用一個(gè)空格分隔。輸