信息學(xué)集訓(xùn)隊(duì)作業(yè)stoneage.beta

1、石器時(shí)代 (交互式)(stoneage)【背景描述】借助月光寶盒，HURRICANE 小組的成員們來(lái)到了石器時(shí)代。在熱鬧的廣場(chǎng)上，不同部落的原始人來(lái)來(lái)往往進(jìn)進(jìn)出出。但是，石器時(shí)代是非常容易爆發(fā)的。爆發(fā)時(shí)，處于絕對(duì)優(yōu)勢(shì)地位的部落總是能夠獲勝。某一時(shí)刻一個(gè)部落在廣場(chǎng)上有“絕對(duì)優(yōu)勢(shì)”，指的是該時(shí)刻在廣場(chǎng)上此部落的人數(shù)比其他部落的人數(shù)之和還要多。出于安全考慮，HURRICANE 小組的成員都非常迫切的希望知道目前在廣場(chǎng)上哪個(gè)部落有絕對(duì)優(yōu)勢(shì)。但不幸的是，HURRICANE 小組成員們只能判斷兩個(gè)原始人是不是屬于一個(gè)部落。你的任務(wù)就是協(xié)助 HURRICANE 小組！【任務(wù)描述】這是一道交互式的題目，你的程

2、序需要和交互庫(kù)交互并按照約定完成所有庫(kù)函數(shù)的調(diào)用：你需要在執(zhí)行任何其他的操作之前初始化交互庫(kù)；然后通過(guò)調(diào)用庫(kù)函數(shù)來(lái)完成你對(duì)數(shù)據(jù)的輸入及處理，其中包括：獲得原始人進(jìn)入廣場(chǎng)的信息；獲得原始人離開(kāi)廣場(chǎng)的信息；獲得 HURRICANE 小組對(duì)于占“絕對(duì)優(yōu)勢(shì)”的部落的查詢(xún)，并在此之后返回該信息給交互庫(kù)。在接到程序結(jié)束的任務(wù)后，你需要正常的退出程序?！窘换シ绞健浚◣?kù)函數(shù)）提供的交互庫(kù)中包括了如下的函數(shù)，現(xiàn)將它們的功能說(shuō)明如下：init：初始化函數(shù)。你需要在你程序的一開(kāi)始調(diào)用它，且僅能調(diào)用一次。調(diào)用后交互庫(kù)會(huì)完成相應(yīng)的初始化工作，此時(shí)，廣場(chǎng)上沒(méi)有原始人（即廣場(chǎng)是空的）。getjob：你應(yīng)當(dāng)調(diào)用該函數(shù)來(lái)獲取你

3、的程序下一步要做的工作。本函數(shù)返回值作如下約定：對(duì)0：表示有一個(gè)原始人進(jìn)入了廣場(chǎng)約定第 i 個(gè)進(jìn)入廣場(chǎng)的原始人為 i；一個(gè)正整數(shù) i：表示為 i 的原始人離開(kāi)了廣場(chǎng)；-1：表示 HURRICANE 小組希望知道當(dāng)前廣場(chǎng)上哪個(gè)部落有絕對(duì)優(yōu)勢(shì)。在下一次調(diào)用本函數(shù)前你必須調(diào)用且僅調(diào)用一次 answer 函數(shù)作為回答；-2：表示任務(wù)完成。在此后不應(yīng)該有任何其他庫(kù)函數(shù)調(diào)用。你的程序應(yīng)該馬上退出。注意：約定進(jìn)入廣場(chǎng)的原始人總數(shù)不超過(guò) 1,000,000；query(i, j)：調(diào)用 init 以后，你隨時(shí)都可以調(diào)用本函數(shù)。它的作用是測(cè)試為 i 的和為 j 的原始人是不是屬于同一個(gè)部落，返回 1 表示屬于同

4、一部落，否則返回 0。注意：你必須保證為 i 和 j 的原始人都進(jìn)入過(guò)廣場(chǎng)，否則視為對(duì)庫(kù)函數(shù)的調(diào)用。answer(i)：i 是你的回答。如果目前有部落處于絕對(duì)優(yōu)勢(shì)地位，則第 i個(gè)入場(chǎng)的原始人應(yīng)該屬于該部落并且仍然在場(chǎng)上（i 可以是他們中任何一個(gè)的入場(chǎng)序號(hào)）；如果目前沒(méi)有部落處于絕對(duì)優(yōu)勢(shì)，i 應(yīng)該為 0?！窘换永俊緶y(cè)試說(shuō)明】你應(yīng)該寫(xiě)一個(gè)輸入文件stoneage.in 來(lái)測(cè)試你的程序，文件格式說(shuō)明如下：第一行為一個(gè)正整數(shù) N，表示廣場(chǎng)上總共將進(jìn)入的原始人的數(shù)目；調(diào)用返回解釋initN/A程序初始化，石器時(shí)代廣場(chǎng)上一個(gè)人也沒(méi)有。getjob0原始人A 第一個(gè)進(jìn)入廣場(chǎng)（1）。getjob0原始人B

5、 第二個(gè)進(jìn)入廣場(chǎng)（2）。query(1,2)0查詢(xún)?cè)既薃 和B，發(fā)現(xiàn)他們不屬于同一個(gè)部落。getjob-1詢(xún)問(wèn)：當(dāng)前存在占絕對(duì)優(yōu)勢(shì)的部落嗎？answer(0)N/A顯然不存在。以 0 作為回答。getjob0原始人C 第三個(gè)進(jìn)入廣場(chǎng)（3）。getjob-1再次詢(xún)問(wèn)是否存在占絕對(duì)優(yōu)勢(shì)的部落。query(3,2)1查詢(xún)C 和B，發(fā)現(xiàn)他們屬于同一個(gè)部落。answer(3)N/AC 和 B 都是占絕對(duì)優(yōu)勢(shì)的部落的成員，回答其中任何一個(gè)即可。getjob2原始人B 離開(kāi)了廣場(chǎng)。getjob-1再次詢(xún)問(wèn)。answer(0)N/A當(dāng)前不存在占絕對(duì)優(yōu)勢(shì)的部落。getjob1原始人A 離開(kāi)了廣場(chǎng)。getjob

6、-2得到可以退出的標(biāo)志，任務(wù)完成，程序退出。第 2 行到第 N+1 行，每一行有一個(gè)正整數(shù)，第 i+1 行的數(shù)Ji 表示第i（1 Ji 1,000,000）；個(gè)進(jìn)入廣場(chǎng)的原始人所屬部落的從第 N+2 行起，每一行含有一個(gè)整數(shù)，依次為每次調(diào)用 getjob 的返回值；你需要保證輸入文件的最后一行是一個(gè)整數(shù)-2，表示最后一次調(diào)用 getjob 的返回值是-2，同時(shí)輸入結(jié)束。運(yùn)行程序時(shí)測(cè)試庫(kù)會(huì)生成stoneage.log你的程序的每一次對(duì)庫(kù)函數(shù)的調(diào)用。stoneage.log 會(huì)忠實(shí)你的程序的調(diào)用，即使它們是的。你可以根據(jù)stoneage.log 來(lái)判斷你的程序的正確性。【語(yǔ)言相關(guān)的說(shuō)明】對(duì)于使用

7、PASCAL 的選手來(lái)說(shuō)，數(shù)定義：提供的stonelib.ppu 單元包括如下的函procedure init;function getjob:long;function query(i,j:longprocedure answer(ans:long):);eger;你可以通過(guò)uses stonelib;語(yǔ)句來(lái)使用這個(gè)單元并調(diào)用其中的函數(shù)。對(duì)于使用 C/C+的選手來(lái)說(shuō)，提供的 stonelib.h/.o 庫(kù)包括如下的函數(shù)定義：void init(); long getjob();query(long i,long j);void answer(long ans);你需要建立一個(gè)工程，然后將 stonelib.o 及你的源程序加入到該工程中。然后就可以通過(guò)#include “stonelib.h”預(yù)編譯指令來(lái)包含這個(gè)頭文件并使用并調(diào)用其中的函數(shù)?！具\(yùn)行限制】【評(píng)分方法】本題目一共有十個(gè)測(cè)試點(diǎn)，每個(gè)測(cè)試點(diǎn)的分?jǐn)?shù)為總分?jǐn)?shù)的 10%。在測(cè)試過(guò)程中，