NOI2012第一試

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

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

3、準(zhǔn)備使用線性同余法(LinearCongruentialMethod)來生成一個(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ù)的庫函數(shù)使用的也是這種方法。棟棟知道這樣產(chǎn)生的序列具有良好的隨機(jī)性,不過心急的他仍然想盡快知道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ù)?！据敵龈袷健枯敵龅轿募andom.out中，輸出一個(gè)數(shù)，即Xmod。g【樣例輸入】1187153樣例輸出】2樣例說明】k012345146078v的前幾項(xiàng)依次是:因此答案為乳mod=8mod=3。數(shù)據(jù)規(guī)模與約定】測試點(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屆全國青少年信息學(xué)奧林匹克競賽第一試騎行川藏第 頁共7頁第29屆全國青少年信息學(xué)奧林匹克競賽第一試騎行川藏第 頁共7頁騎行川藏【問題描述】蛋蛋非常熱衷于挑戰(zhàn)自我，今年暑假他準(zhǔn)備沿川藏線騎著自行車從成都前往拉薩。川藏線的沿途有著非常美麗的風(fēng)景，但在這一路上也有著很多的艱難險(xiǎn)阻，路況變化多端，而蛋蛋的體力十分有限，因此在每天的騎行前設(shè)定好目的地、同時(shí)合理分配好自己的體力是一件非常重要的事情。由于蛋蛋裝備了一輛非常好的自行車，因此在騎行過程中可以認(rèn)為他僅在克服風(fēng)阻做功（不受自行車本身摩擦力以及自行車

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

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

9、1時(shí)，才能獲得該測試點(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ì)超過10（。1I【提示】必然存在一種最優(yōu)勺體力方案滿足：蛋蛋在每段路上都采用勻速騎行勺方式第29屆全國青少年信息學(xué)奧林匹克競賽第一試魔幻棋盤.第 頁共7頁第29屆全國青少年信息學(xué)奧林匹克競賽第一試騎行川藏第 #頁共7頁魔幻棋盤【題目描述】將要讀二年級(jí)的小Q買了一款新型益智玩具一一魔幻棋盤，它是一個(gè)行妙U的網(wǎng)格棋盤,每

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

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

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