頂級(jí)選手wc第31屆全國(guó)青少年信

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

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

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

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

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

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

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