NOI2012第一試

1、第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽CCFNOI2012第一試競(jìng)賽時(shí)間：2012年7月30日8:00-13:00題目名稱(chēng)隨機(jī)數(shù)生成器騎行川藏魔幻棋盤(pán)目錄randombicyclingchess可執(zhí)行文件名randombicyclingchess輸入文件名random.inbicycling.inchess.in輸出文件名random.outbicycling.outchess.out每個(gè)測(cè)試點(diǎn)時(shí)限1秒1秒5秒內(nèi)存限制512MB512MB512MB測(cè)試點(diǎn)數(shù)目202010每個(gè)測(cè)試點(diǎn)分值5510是否有部分分否否否題目類(lèi)型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型是否有附加文件無(wú)無(wú)無(wú)提交源程序須加后綴對(duì)于C+語(yǔ)言random

2、.cppbicycling.cppchess.cpp對(duì)于C語(yǔ)言random.cbicycling.cchess.c對(duì)于Pascal語(yǔ)言random.pasbicycling.paschess.pas注意：最終測(cè)試時(shí)，所有編譯命令均不打開(kāi)任何優(yōu)化開(kāi)關(guān)。第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第一試隨機(jī)數(shù)生成器第 #頁(yè)共7頁(yè)第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第一試隨機(jī)數(shù)生成器第 頁(yè)共7頁(yè)第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第一試隨機(jī)數(shù)生成器第 頁(yè)共7頁(yè)第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第一試隨機(jī)數(shù)生成器第 #頁(yè)共7頁(yè)隨機(jī)數(shù)生成器【問(wèn)題描述】棟棟最近迷上了隨機(jī)算法，而隨機(jī)數(shù)生成是隨機(jī)算法的基礎(chǔ)。棟棟

3、準(zhǔn)備使用線性同余法(LinearCongruentialMethod)來(lái)生成一個(gè)隨機(jī)數(shù)列，這種方法需要設(shè)置四個(gè)非負(fù)整數(shù)參數(shù)皿,c,X,按照下面的公式生成出一系列隨機(jī)數(shù):X=(aXc)modm其中mod表示前面的數(shù)除以啲余數(shù)。從這個(gè)式子可以看出，這個(gè)序列的下一個(gè)數(shù)總是由上一個(gè)數(shù)生成的。用這種方法生成的序列具有隨機(jī)序列的性質(zhì),因此這種方法被廣泛地使用,包括常用的C+和Pascal的產(chǎn)生隨機(jī)數(shù)的庫(kù)函數(shù)使用的也是這種方法。棟棟知道這樣產(chǎn)生的序列具有良好的隨機(jī)性,不過(guò)心急的他仍然想盡快知道X是多少。由于棟棟需要的隨機(jī)數(shù)是0,1，,Q-1之間的，他需要將X除以gnn取余得到他想要的數(shù)，即Xmod，你只需要

4、告訴棟棟他想要的數(shù)暫mod是多少就可以了?！据斎敫袷健枯斎胛募andom.in中包含6個(gè)用空格分割的整數(shù)九和矽其中a,X0是非負(fù)整數(shù)，m,n,g是正整數(shù)。【輸出格式】輸出到文件random.out中，輸出一個(gè)數(shù)，即Xmod。g【樣例輸入】1187153樣例輸出】2樣例說(shuō)明】k012345146078v的前幾項(xiàng)依次是:因此答案為乳mod=8mod=3。數(shù)據(jù)規(guī)模與約定】測(cè)試點(diǎn)編號(hào)nm,a,c,X0m,a性質(zhì)g1n100m,a,c,X0100m為質(zhì)數(shù)2n1000m,a,c,X01000m為質(zhì)數(shù)3n104m,a,c,X0104m為質(zhì)數(shù)4n104m,a,c,X0104m為質(zhì)數(shù)5n105m,a,c,X0

5、104m與a-1互質(zhì)6n105m,a,c,X0104m與a-1互質(zhì)7n105m,a,c,X0104m與a-1互質(zhì)8n106m,a,c,X0104/9n106m,a,c,X0109m為質(zhì)數(shù)10n106m,a,c,X0109/a10811n1012m,a,c,X0109m為質(zhì)數(shù)12n1012m,a,c,X0109m為質(zhì)數(shù)13n1016m,a,c,X0109m與a-1互質(zhì)14n1016m,a,c,X0109m與a-1互質(zhì)15n1016m,a,c,X0109/16n1018m,a,c,X0109/17n1018m,a,c,X0109/18n1018m,a,c,X01018m為質(zhì)數(shù)19n1018m,a,

6、c,X01018m與a-1互質(zhì)20n1018m,a,c,X01,m1,a0，c0，X00，g1。第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第一試騎行川藏第 頁(yè)共7頁(yè)第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第一試騎行川藏第 頁(yè)共7頁(yè)騎行川藏【問(wèn)題描述】蛋蛋非常熱衷于挑戰(zhàn)自我，今年暑假他準(zhǔn)備沿川藏線騎著自行車(chē)從成都前往拉薩。川藏線的沿途有著非常美麗的風(fēng)景，但在這一路上也有著很多的艱難險(xiǎn)阻，路況變化多端，而蛋蛋的體力十分有限，因此在每天的騎行前設(shè)定好目的地、同時(shí)合理分配好自己的體力是一件非常重要的事情。由于蛋蛋裝備了一輛非常好的自行車(chē)，因此在騎行過(guò)程中可以認(rèn)為他僅在克服風(fēng)阻做功（不受自行車(chē)本身摩擦力以及自行車(chē)

7、與地面的摩擦力影響）。某一天他打算騎殿路，每一段內(nèi)的路況可視為相同：對(duì)于第段路，我們給出有關(guān)這段路況的3個(gè)參數(shù).sk.M，其中表示這段路的長(zhǎng)度，7表示這段路的風(fēng)阻系數(shù)，M表示這段路上的風(fēng)速（q0表示在這段路上他遇到了順風(fēng)，反之則意1I味著他將受逆風(fēng)影響）。若某一時(shí)刻在這段路上騎車(chē)速度為，則他受到的風(fēng)阻大小為=kj（u-叩2（這樣若在長(zhǎng)度為的路程內(nèi)保持騎行速度不變，則他消耗能量（做功）E=kj（u一冬）2S）。設(shè)蛋蛋在這天開(kāi)始時(shí)的體能值是請(qǐng)幫助他設(shè)計(jì)一種行車(chē)方案，使他在有限的體力內(nèi)用最短的時(shí)間到達(dá)目的地。請(qǐng)告訴他最短的時(shí)間是多少?！据斎敫袷健枯斎胛募icycling.in中的第一行包含一個(gè)正整

8、數(shù)惰口一個(gè)實(shí)數(shù)滬分別表示路段的數(shù)量以及蛋蛋的體能值。接下來(lái)布分別描述階路段，每行有3個(gè)實(shí)數(shù)/嚴(yán);，分別表示第段路的長(zhǎng)度，風(fēng)阻系數(shù)以及風(fēng)速。【輸出格式】輸出到文件bicycling.out中，輸出一個(gè)實(shí)數(shù)T表示蛋蛋到達(dá)目的地消耗的最短時(shí)間，要求至少保留到小數(shù)點(diǎn)后6位?！緲永斎搿?1000010000105200001585000056【樣例輸出】12531.34496464【樣例說(shuō)明】一種可能的方案是：蛋蛋在三段路上都采用勻速騎行的方式，其速度依次為5.12939919,8.03515481,6.17837967。【評(píng)分方法】本題沒(méi)有部分分，你程序的輸出只有和標(biāo)準(zhǔn)答案的差距不超過(guò)0.00000

9、1時(shí)，才能獲得該測(cè)試點(diǎn)的滿分，否則不得分。【數(shù)據(jù)規(guī)模與約定】對(duì)于10%勺數(shù)據(jù)，N=1；對(duì)于40%勺數(shù)據(jù)，N2；對(duì)于60%勺數(shù)據(jù)，N100；對(duì)于80%勺數(shù)據(jù)，N1000；對(duì)于所有數(shù)據(jù)，N10000，EU108，0st100000,0k.15，-100v：100。數(shù)據(jù)保證最終的答案不會(huì)超過(guò)10（。1I【提示】必然存在一種最優(yōu)勺體力方案滿足：蛋蛋在每段路上都采用勻速騎行勺方式第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第一試魔幻棋盤(pán).第 頁(yè)共7頁(yè)第29屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第一試騎行川藏第 #頁(yè)共7頁(yè)魔幻棋盤(pán)【題目描述】將要讀二年級(jí)的小Q買(mǎi)了一款新型益智玩具一一魔幻棋盤(pán)，它是一個(gè)行妙U的網(wǎng)格棋盤(pán),每

10、個(gè)格子中均有一個(gè)正整數(shù)。棋盤(pán)守護(hù)者在棋盤(pán)的第行第Y列（行與列均從開(kāi)始編號(hào)）并且始終不會(huì)移動(dòng)。棋盤(pán)守護(hù)者會(huì)進(jìn)行兩種操作：（a）詢(xún)問(wèn)：他會(huì)以自己所在位置為基礎(chǔ)，向四周隨機(jī)擴(kuò)展出一塊大小不定的矩形區(qū)域，向你詢(xún)問(wèn)這一區(qū)域內(nèi)所有數(shù)的最大公約數(shù)是多少。（b）修改：他會(huì)隨意挑選棋盤(pán)上的一塊矩形區(qū)域，將這一區(qū)域內(nèi)的所有數(shù)同時(shí)加上一個(gè)給定的整數(shù)。游戲說(shuō)明書(shū)上附有這樣一句話“聰明的小朋友，當(dāng)你連續(xù)答對(duì)1993032次4詢(xún)問(wèn)后會(huì)得到一個(gè)驚喜噢！”。小Q十分想得到這個(gè)驚喜，于是每天都在玩這個(gè)玩具。但由于他粗心大意，經(jīng)常算錯(cuò)數(shù)，難以達(dá)到這個(gè)目標(biāo)。于是他來(lái)向你尋求幫助，希望你幫他寫(xiě)一個(gè)程序來(lái)回答棋盤(pán)守護(hù)者的詢(xún)問(wèn)，并保證1

11、00%的正確率。為了簡(jiǎn)化問(wèn)題，你的程序只需要完成棋盤(pán)守護(hù)者的次操作，并且問(wèn)題保證任何時(shí)刻棋盤(pán)上的數(shù)字均為不超過(guò)62-1的正整數(shù)?！据斎敫袷健枯斎胛募hess.in中的第一行為兩個(gè)正整數(shù)N,M,表示棋盤(pán)的大小。第二行為兩個(gè)正整數(shù)境，表示棋盤(pán)守護(hù)者的位置。第三行僅有一個(gè)正整數(shù)T表示棋盤(pán)守護(hù)者將進(jìn)行次操作。接下來(lái)T行，每行有Mb正整數(shù)，用來(lái)描述初始時(shí)棋盤(pán)上每個(gè)位置的數(shù)。接下來(lái)行,按操作的時(shí)間順序給出次操作。每行描述一次操作，以一個(gè)數(shù)字0或1開(kāi)頭：若以數(shù)字0開(kāi)頭，表示此操作為詢(xún)問(wèn)，隨后會(huì)有四個(gè)非負(fù)整數(shù)1xy1,%2,y2，表示詢(xún)問(wèn)的區(qū)域是以棋盤(pán)守護(hù)者的位置為基礎(chǔ)向上擴(kuò)展尤行，向下擴(kuò)展2行,向左擴(kuò)展，

12、向右擴(kuò)展2列得到的矩形區(qū)域（詳見(jiàn)樣例）。若以數(shù)字1開(kāi)頭，表示此操作為修改，隨后會(huì)有四個(gè)正整數(shù)1xy1,%2,y2和一個(gè)整數(shù)c表示修改區(qū)域的上、下邊界分別為第樣勺行，左、右邊界分別為第1yy2列（詳見(jiàn)樣例），在此矩形區(qū)域內(nèi)的所有數(shù)統(tǒng)一加上c（注意可能為負(fù)數(shù)）?！据敵龈袷健枯敵龅轿募hess.out中。對(duì)于每次詢(xún)問(wèn)操作，每行輸出一個(gè)數(shù)，表示該區(qū)域內(nèi)所有數(shù)的最大公約數(shù)。【輸入樣例】221146121824TOC o 1-5 h z0001011112612122600011【輸出樣例】66樣例說(shuō)明】初始狀態(tài)第一次操作后第二次操作后第三次操作后第四次操作后61261212181218121818241824182424302430對(duì)于第一、第四次操作（查詢(xún)操作）后，加粗部分表示查詢(xún)區(qū)域。