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

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

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

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

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

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

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

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