頂級選手wc第31屆全國青少年信

1、第 31 屆青少年信息學(xué)冬令營競賽時間： 2014 年 2 月 13 日8 :00 - 13:00 提交源程序須加后綴編譯開關(guān)對于 C+語言-lm-O2 lmN/A對于 C語言-lm-O2 lmN/A對于 Pascal 語言-O2N/A對于 C+語言space.cppflower.cppN/A對于 C語言space.cflower.cN/A對于 Pascal 語言space.pasflower.pasN/A題目名稱時空穿梭紫荊花之戀非確定機目錄spaceflowernm可執(zhí)行文件名spaceflowerN/A輸入文件名space.inflower.innm1.in nm10.in輸出文件名sp

2、ace.outflower.outnm1.out nm10.out每個測試點時限1 秒12 秒N/A內(nèi)存限制512 MB512 MBN/A測試點數(shù)目102010每個測試點分值10510是否有部分分否否是題目類型傳統(tǒng)型傳統(tǒng)型提交型是否有附加文件否否是第 31 屆青少年信息學(xué)冬令營時空穿梭時空穿梭【問題描述】小 X 駕駛著他的飛船準(zhǔn)備穿梭過一個可以用 個實數(shù)來表示，即 !, !, , ! 。為了穿過這個空間，小 X 需要在這個空間中選取 2 個點作為飛船停留的地方，而這些點需要滿足以下三個條件：1. 每個點的每一維坐標(biāo)均為正整數(shù)，且第 維坐標(biāo)不超過! 。2. 第 + 1 1 1，父節(jié)點的編號至少為

3、1?！据敵龈袷健枯敵鑫募?flower.out 包含n 行，每行輸出 1 個整數(shù)，表示加入第 i 個點之后， 樹上有幾對朋友?！緲永斎搿?50 0 6第 4 頁 共 8 頁第 31 屆青少年信息學(xué)冬令營紫荊花之戀100029524454【樣例輸出】01247【樣例輸入輸出 2】見選手目錄下的 flower/flower.in 與 flower/flower.ans?！緮?shù)據(jù)規(guī)模和約定】對于所有的數(shù)據(jù)，滿足 1 c! 10000, a! 2 10!, r! 10!第 5 頁 共 8 頁測試點編號約定1,2n 1003,4n 10005,6,7,8n 100000 ，節(jié)點 1 最多有兩個子節(jié)點，其

4、它節(jié)點最多有一個子節(jié)點9,10n 100000 ，r! 1011,12n 100000 ，這棵樹是隨機生成的13,14,15n 7000016,17,18,19,20n 100000第 31 屆青少年信息學(xué)冬令營非確定機非確定機【問題描述】“非確定機”是現(xiàn)在假想中的一種計算機，它可以同時運行任意多段指令。這種計算機中一種新的分支指令，執(zhí)行到這條指令時，程序會一分為二，同時分別執(zhí)行這兩個分支。“非確定機”的一個神奇的功能是程序反轉(zhuǎn)。給定一個程序和該程序的輸出， 它可以用相同的時空代價得到一個符合該輸出的輸入。這道題目正是要你反轉(zhuǎn)運行一個程序。在本題中，你有一個已編譯好的，包含一些算法的程序 pr

5、og。它的輸入為一個有向圖和算法編號，輸出為在有向圖上運行算法得到的結(jié)果。同時， 你會得到 10 個由程序 prog 運行得到的輸出文件。你的任務(wù)是對每個輸出文件給出一個可能的輸入文件。為了區(qū)分，在后文中如果沒有特殊說明，我們把給定的程序 prog 的輸出文件稱作“輸入”， 需要提交的程序 prog 的輸入文件稱作“輸出”?！据斎敫袷健吭擃}為提交型試題，所有輸入數(shù)據(jù) nm1.innm10.in 已在試題目錄下。輸入的第一行包含三個正整數(shù), , ，表示圖 的點數(shù)，當(dāng)前使用算法和一個由圖 計算出的評分參數(shù)。接下來有若干行，每行包含若干個整數(shù)，其意義需要你去探究?！据敵龈袷健拷o定的 10 個輸入文件

6、 nm1.innm10.in，你需要分別提交你的輸出文件nm1.outnm10.out。輸出文件的第一行包含 3 個整數(shù), , ，表示有向圖 的點數(shù)，邊數(shù)和當(dāng)前使用的算法。接下來有行，每行包含 3 個整數(shù), , ，表示一條從節(jié)點 連向節(jié)點 ， 權(quán)值為 的有向邊。其中節(jié)點的編號用 1 到 的整數(shù)表示。要求 必須為不超過 20000 的非負(fù)整數(shù)，且不能出現(xiàn)重邊。出現(xiàn)自環(huán)?！境绦虻氖褂谩吭诮K端中先切換到該試題的目錄下cd nm程序 prog 已在試題目錄下，其使用方法是./prog 程序會把作為程序 prog 的輸入，將運行的結(jié)果輸出到標(biāo)第 6 頁 共 8 頁第 31 屆青少年信息學(xué)冬令營非確定機準(zhǔn)

7、輸出。例如./prog nm4.out程序?qū)?nm4.out 作為程序 prog 的輸入。如果你的文件不合法，程序?qū)敵鲥e誤信息?！緲永斎搿?01000010100【樣例輸出】312333120921229【樣例說明】在樣例中，邊的權(quán)值 并可能存在這種情況。影響到運行結(jié)果，在實際的數(shù)據(jù)中也要注意【評分方法】每個測試點單獨評分。如果你的輸出運行后得到的, 與輸入文件一致，得 1 分。如果你的輸出運行后得到的, , 與輸入文件一致，得 2 分。如果你的輸出運行后得到的整數(shù)中，除了以外均與輸入文件一致，得 4 分。在評測時，每個測試點會有一個評分參數(shù)。如果你的輸出運行后得到的整數(shù)中，除了以外均與輸入文件一致，且值與標(biāo)準(zhǔn)文件差值的絕對值不超過， 得 7 分。如果你的輸出運行后得到的整數(shù)和輸入文件全部一致，得 10 分。以上條件如果滿足多個，取最高分。每個測試點的如下第 7 頁 共 8 頁測試點編號測試點編號1068210007203081000第 31 屆青少年信息學(xué)冬令營非確定機【如何測試你的輸出】程序 prog 還有測試的功能，可以根據(jù)你的輸入輸出文件以及 值給出得分或錯誤信息。具體用法為./prog 例如要測試測試點 6，可以使用./prog nm6.ou