NOIP2016提高組復賽試題Day1Day2

1、第 22 屆全國青少年信息學奧林匹克聯(lián)賽CCF-NOIP-2016提高組（復賽） 第一試競賽時間：2016 年 11 月 19 日 8:30 12:00題目名稱 玩具謎題 天天愛跑步 換教室 題目類型 傳統(tǒng)型 傳統(tǒng)型 傳統(tǒng)型 目錄 toyrunningclassroom可執(zhí)行文件名 toyrunningclassroom輸入文件名 toy.inrunning.inclassroom.in輸出文件名 toy.outrunning.outclassroom.out每個測試點時限 1.0 秒 2.0 秒 1.0 秒 內(nèi)存限制 512 MB512 MB512 MB測試點數(shù)目 202025每個測試點分值

2、 554提交源程序文件名對于 C+語言 toy.cpprunning.cppclassroom.cpp對于 C語言 toy.crunning.cclassroom.c對于 Pascal 語言 toy.pasrunning.pasclassroom.pas編譯選項對于 C+語言 -lm-lm-lm對于 C語言 -lm-lm-lm對于 Pascal 語言 注意事項：1. 文件名（程序名和輸入輸出文件名）必須使用英文小寫。2. 除非特殊說明，結(jié)果比較方式均為忽略行末空格及文末回車的全文比較。3. C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時的返回值必須 是 0。4. 全國統(tǒng)

3、一評測時采用的機器配置為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，內(nèi)存 4G，上述時限以此配置為準。5. 只提供 Linux 格式附加樣例文件。6. 評測在 NOI Linux 下進行。7. 編譯時不打開任何優(yōu)化選項。玩具謎題（toy)【問題描述】小南有一套可愛的玩具小人，它們各有不同的職業(yè)。有一天，這些玩具小人把小南的眼鏡藏了起來。小南發(fā)現(xiàn)玩具小人們圍成了一個圈，它們有的面朝圈內(nèi)，有的面朝圈外。如下圖：這時 singer 告訴小南一個謎題：“眼鏡藏在我左數(shù)第 3 個玩具小人的右數(shù)第 1 個玩具小人的左數(shù)第 2 個玩具小人那里。”小南發(fā)現(xiàn)，這

4、個謎題中玩具小人的朝向非常關(guān)鍵，因為朝內(nèi)和朝外的玩具小人的左右方向是相反的：面朝圈內(nèi)的玩具小人，它的左邊是順時針方向，右邊是逆時針方向；而面向圈外的玩具小人，它的左邊是逆時針方向，右邊是順時針方向。小南一邊艱難地辨認著玩具小人，一邊數(shù)著：“singer 朝內(nèi)，左數(shù)第 3 個是 archer?！癮rcher 朝外，右數(shù)第 1 個是 thinker?！皌hinker 朝外，左數(shù)第 2 個是 writer。“所以眼鏡藏在 writer 這里！”雖然成功找回了眼鏡，但小南并沒有放心。如果下次有更多的玩具小人藏他的眼鏡，或是謎題的長度更長，他可能就無法找到眼鏡了。所以小南希望你寫程序幫他解決類似的謎題。

5、這樣的謎題具體可以描述為：有 n 個玩具小人圍成一圈，己知它們的職業(yè)和朝向?，F(xiàn)在第 1 個玩具小人告訴小南一個包含 m 條指令的謎題，其中第 i 條指令形如“左數(shù)/右數(shù)第 si 個玩具小人”。你需要輸出依次數(shù)完這些指令后，到達的玩具小人的職業(yè)。【輸入格式】從文件 toy.in 中讀入數(shù)據(jù)。輸入的第一行包含兩個正整數(shù) n,m ，表示玩具小人的個數(shù)和指令的條數(shù)。接下來 n 行，每行包含一個整數(shù)和一個字符串，以逆時針為順序給出每個玩具小人的朝向和職業(yè)。其中 0 表示朝向圈內(nèi)， 1 表示朝向圈外。保證不會出現(xiàn)其他的數(shù)。字符串長度不超過 10 且僅由小寫字母構(gòu)成，字符串不為空，并且字符串兩兩不同。整數(shù)和

6、字符串之間用一個空格隔開。接下來 m 行，其中第 i 行包含兩個整數(shù) ai, si ，表示第 i 條指令。若 ai = 0 ，表示向左數(shù) si 個人；若 ai = 1 ，表示向右數(shù) si 個人。保證 ai 不會出現(xiàn)其他的數(shù)， 1 si < n。【輸出格式】輸出到文件 toy.out 中。輸出一個字符串，表示從第一個讀入的小人開始，依次數(shù)完 m條指令后到達的小人的職業(yè)。【樣例 1 輸入】7 30 singer0 reader0 mengbier1 thinker1 archer0 writer1 mogician0 31 10 2【樣例 1 輸出】writer【樣例 1 說明】這組數(shù)據(jù)就是

7、【題目描述】中提到的例子?！緲永?2 輸入】10 101 c0 r0 p1 d1 e1 m1 t1 y1 u0 v1 71 11 40 50 30 11 61 20 80 4【樣例 2 輸出】y【子任務】子任務會給出部分測試數(shù)據(jù)的特點。如果你在解決題目中遇到了困難，可以嘗試只解決一部分測試數(shù)據(jù)。每個測試點的數(shù)據(jù)規(guī)模及特點如下表：測試點 nm全朝內(nèi) 全左數(shù) si = 1職業(yè)長度為 11= 20= 103 2× 3 × 4× 5 × 6× 7 × 8× 9 × 10× 11 × 12× 1

8、3 × 14× 15 × 16× 17= 105= 105 18× 19 × 20× 其中一些簡寫的列意義如下：l 全朝內(nèi)：若為“”， 表示該測試點保證所有的玩具小人都朝向圈內(nèi)；l 全左數(shù)：若為“”，表示該測試點保證所有的指令都向左數(shù)，即對任意的1 i m， ai = 0 ；l si = 1 ：若為“”，表示該測試點保證所有的指令都只數(shù)1個，即對任意的1 i m， si = 1 ；l 職業(yè)長度為1：若為“”，表示該測試點保證所有玩具小人的職業(yè)一定是一個長度為 1 的字符串。天天愛跑步（running)【問題描述】小 C 同學

9、認為跑步非常有趣，于是決定制作一款叫做天天愛跑步的游戲。天 天愛跑步是一個養(yǎng)成類游戲，需要玩家每天按時上線，完成打卡任務。這個游戲的地圖可以看作一棵包含 n 個結(jié)點和 n 1 條邊的樹，每條邊連接兩個結(jié)點，且任意兩個結(jié)點存在一條路徑互相可達。樹上結(jié)點編號為從 1 到 n 的連續(xù)正整數(shù)?，F(xiàn)在有 m 個玩家，第 i 個玩家的起點為 Si ，終點為 Ti 。每天打卡任務開始時，所 有玩家在第 0 秒同時從自己的起點出發(fā)，以每秒跑一條邊的速度，不間斷地沿著 最短 路徑向著自己的終點跑去，跑到終點后該玩家就算完成了打卡任務。（由于地圖是一棵樹，所以每個人的路徑是唯一的）小 C 想知道游戲的活躍度，所以在

10、每個結(jié)點上都放置了一個觀察員。在結(jié)點 j 的 觀 察員會選擇在第 Wj 秒觀察玩家，一個玩家能被這個觀察員觀察到當且僅當該玩家 在第 Wj 秒也正好到達了結(jié)點 j 。小 C 想知道每個觀察員會觀察到多少人？注意：我們認為一個玩家到達自己的終點后該玩家就會結(jié)束游戲，他不能等待一 段時間后再被觀察員觀察到。即對于把結(jié)點 j 作為終點的玩家：若他在第 Wj 秒前到達 終點，則在結(jié)點 j 的觀察員不能觀察到該玩家；若他正好在第 Wj 秒到達終點，則在結(jié) 點 j 的觀察員可以觀察到這個玩家?！据斎敫袷健繌奈募?running.in 中讀入數(shù)據(jù)。第一行有兩個整數(shù) n 和 m 。其中 n 代表樹的結(jié)點數(shù)量，

11、同時也是觀察員的數(shù)量，m 代表玩家的數(shù)量。接下來 n 1 行每行兩個整數(shù) u 和 v ，表示結(jié)點 u 到結(jié)點 v 有一條邊。接下來一行 n 個整數(shù)，其中第 j 個整數(shù)為 Wj ，表示結(jié)點 j 出現(xiàn)觀察員的時間。接下來 m 行，每行兩個整數(shù) Si 和 Ti ，表示一個玩家的起點和終點。對于所有的數(shù)據(jù)，保證 1 Si , Ti n ， 0 Wj n ?！据敵龈袷健枯敵龅轿募?running.out 中。輸出 1 行 n 個整數(shù)，第 j 個整數(shù)表示結(jié)點 j 的觀察員可以觀察到多少人?！緲永?1 輸入】6 32 31 21 44 54 60 2 5 1 2 31 51 32 6【樣例 1 輸出】2 0

12、 0 1 1 1【樣例 1 說明】對于 1 號點， W1 = 0 ，故只有起點為 1 號點的玩家才會被觀察到，所以玩家 1 和玩家 2 被觀察到，共 2 人被觀察到。對于 2 號點，沒有玩家在第 2 秒時在此結(jié)點，共 0 人被觀察到。對于 3 號點，沒有玩家在第 5 秒時在此結(jié)點，共 0 人被觀察到。對于 4 號點，玩家 1 被觀察到，共 1 人被觀察到。對于 5 號點，玩家 1 被觀察到，共 1 人被觀察到。對于 6 號點，玩家 3 被觀察到，共 1 人被觀察到?！緲永?2 輸入】5 31 22 32 41 50 1 0 3 03 11 45 5【樣例 2 輸出】1 2 1 0 1【子任務】

13、每個測試點的數(shù)據(jù)規(guī)模及特點如下表所示。提示：數(shù)據(jù)范圍的個位上的數(shù)字可以幫助判斷是哪一種數(shù)據(jù)類型。測試點編號 nm約定 1= 991= 991所有人的起點等于自己的終點，即 Si = Ti23= 992= 992Wj = 045= 993= 993無 6= 99994= 99994樹退化成一條鏈，其中 1 與 2 有邊，2 與 3 有邊，. . . ，n 1 與 n 有邊 789= 99995= 99995所有的Si = 110111213= 99996= 99996所有的Ti = 114151617= 99997= 99997無 181920= 299998= 299998【提示】如果你的程序

14、需要用到較大的?？臻g（這通常意味著需要較深層數(shù)的遞歸），請務 必仔細閱讀選手目錄下的文檔 running/stack.pdf ，以了解在最終評測時?？臻g的限制 與在當前工作環(huán)境下調(diào)整?？臻g限制的方法。換教室（classroom)【問題描述】對于剛上大學的牛牛來說，他面臨的第一個問題是如何根據(jù)實際情況申請合適的 課程。在可以選擇的課程中，有 2n 節(jié)課程安排在 n 個時間段上。在第 i ( 1 i n )個時間段上，兩節(jié)內(nèi)容相同的課程同時在不同的地點進行，其中，牛牛預先被安排在教室ci上課，而另一節(jié)課程在教室 di 進行。在不提交任何申請的情況下，學生們需要按時間段的順序依次完成所有的 n 節(jié)安

15、排好的課程。如果學生想更換第 i 節(jié)課程的教室，則需要提出申請。若申請通過，學生就可以在第 i 個時間段去教室 di 上課，否則仍然在教室 di 上課。由于更換教 室的需求太多，申請不一定能獲得通過。通過計算，牛牛發(fā)現(xiàn)申請更換第 i 節(jié)課程的教室時，申請被通過的概率是一個己知的實數(shù) ki ，并且對于不同課程的申請，被通過的概率是互相獨立的。學校規(guī)定，所有的申請只能在學期開始前一次性提交，并且每個人只能選擇至多 m 節(jié)課程進行申請。這意味著牛牛必須一次性決定是否申請更換每節(jié)課的教室，而 不能根據(jù)某些課程的申請結(jié)果來決定其他課程是否申請；牛?？梢陨暾堊约鹤钕Ｍ?換教室的 m 門課程，也可以不用完

16、這 m 個申請的機會，甚至可以一門課程都不申請。因為不同的課程可能會被安排在不同的教室進行，所以牛牛需要利用課間時間從 一間教室趕到另一間教室。牛牛所在的大學有 v 個教室，有 e 條道路。每條道路連接兩間教室，并且是可以雙向通行的。由于道路的長度和擁堵程度不同，通過不同的道路耗費的體力可能會有所不同。當?shù)?i （ 1 i n 1 ）節(jié)課結(jié)束后，牛牛就會從這節(jié)課的教室出發(fā)，選擇一條耗費體力最少的路徑前往下一節(jié)課的教室?，F(xiàn)在牛牛想知道，申請哪幾門課程可以使他因在教室間移動耗費的體力值的總和的期望值最小，請你幫他求出這個最小值?，F(xiàn)在牛牛想知道，申請哪幾門課程可以使他因在教室間移動耗費的體力值的總和

17、的期望值最小，請你幫他求出這個最小值。【輸入格式】從文件 classroom.in 中讀入數(shù)據(jù)。第一行四個整數(shù) n, m, v, e 。 n 表示這個學期內(nèi)的時間段的數(shù)量； m 表示牛牛最多 可以申請更換多少節(jié)課程的教室； v 表示牛牛學校里教室的數(shù)量； e 表示牛牛的學校 里道路的數(shù)量。第二行 n 個正整數(shù)，第 i （ 1 i n ）個正整數(shù)表示 ci ，即第 i 個時間段牛牛被安 排上課的教室；保證 1 ci v 。第三行 n 個正整數(shù)，第 i （ 1 i n ）個正整數(shù)表示 di ，即第 i 個時間段另一間上同樣課程的教室；保證 1 di v 。第四行 n 個實數(shù)，第 i （ 1 i n

18、 ）個實數(shù)表示 ki ，即牛牛申請在第 i 個時間段更 換教室獲得通過的概率。保證 0 ki 1 。接下來 e 行，每行三個正整數(shù) aj ， bj ， wj ，表示有一條雙向道路連接教室 aj , bj ，通過這條道路需要耗費的體力值是 wj ；保證 1 aj, bj v ， 1 wj 100 。保證 1 n 2000 ， 0 m 2000 ， 1 v 300 ， 0 e 90000 。保證通過學校里的道路，從任何一間教室出發(fā)，都能到達其他所有的教室。保證 輸入的實數(shù)最多包含 3 位小數(shù)?！据敵龈袷健枯敵龅轿募?classroom.out 中。輸出一行，包含一個實數(shù)，四舍五入精確到小數(shù)點后恰好

19、 2 位，表示答案。你的輸出必須和標準輸出完全一樣才算正確。測試數(shù)據(jù)保證四舍五入后的答案和準確答案的差的絕對值不大于 4×10-3 。（如果你不知道什么是浮點誤差，這段話可以理解為：對于大多數(shù)的算法，你可以正常地使用浮點數(shù)類型而不用對它進行特殊的處理）【樣例 1 輸入】3 2 3 32 1 21 2 10.8 0.2 0.51 2 51 3 32 3 1【樣例 1 輸出】2.80【樣例 1 說明】所有可行的申請方案和期望收益如下表：申請更換教室的時間段申請通過的時間段出現(xiàn)的概率耗費的體力值耗費的體力值的期望無 無 1.088.0110.844.8無 0.28220.206.4無 0.

20、88330.546.0無 0.581、21、20.1644.4810.64420.040無 0.1681、31、30.402.810.4430.14無 0.182、32、30.145.220.1030.44無 0.48【樣例 2】見選手目錄下的 classroom/classroom2.in 與 classroom/classroom2.ans。【提示】1. 道路中可能會有多條雙向道路連接相同的兩間教室。也有可能有道路兩端連接的是同一間教室。2. 請注意區(qū)分 n, m, v, e 的意義， n 不是教室的數(shù)量， m 不是道路的數(shù)量。【子任務】測試點 nmv特殊性質(zhì) 1特殊性質(zhì) 21 1 1 3

21、00× × 2 2 0 203 1 1004 2 3005 3 0 20 6 1 100× 7 2 300× 8 10 0 9 1 20× 10 2 100× 11 10 300 12 20 0 20 × 13 1 100× 14 2 300 15 20× 16 300 0 20× 17 1 10018 2 300 19 300× 20 2000 0 20× 21 122 2 10023 200024 30025特殊性質(zhì) 1：圖上任意兩點 ai ， bi ， ai bi 間，

22、存在一條耗費體力最少的路徑只 包含一條道路。特殊性質(zhì) 2：對于所有的 1 i n ， ki = 1 。第 22 屆全國青少年信息學奧林匹克聯(lián)賽CCF-NOIP-2016提高組（復賽） 第二試競賽時間：2016 年 11 月 20 日 8:30 12:00題目名稱 組合數(shù)問題 蚯蚓 憤怒的小鳥 題目類型 傳統(tǒng)型 傳統(tǒng)型 傳統(tǒng)型 目錄 problemearthwormangrybirds可執(zhí)行文件名 problemearthwormangrybirds輸入文件名 problem.inearthworm.inangrybirds.in輸出文件名 problem.outearthworm.outang

23、rybirds.out每個測試點時限 1.0 秒 1.0 秒 2.0 秒 內(nèi)存限制 512 MB512 MB512 MB測試點數(shù)目 202020每個測試點分值 555提交源程序文件名對于 C+語言 problem.cppearthworm.cppangrybirds.cpp對于 C語言 problem.cearthworm.cangrybirds.c對于 Pascal 語言 problem.pasearthworm.pasangrybirds.pas編譯選項對于 C+語言 -lm-lm-lm對于 C語言 -lm-lm-lm對于 Pascal 語言 注意事項：1. 文件名（程序名和輸入輸出文件名

24、）必須使用英文小寫。2. 除非特殊說明，結(jié)果比較方式均為忽略行末空格及文末回車的全文比較。3. C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時的返回值必須 是 0。4. 全國統(tǒng)一評測時采用的機器配置為：CPU AMD Athlon(tm) II x2 240 processor， 2.8GHz，內(nèi)存 4G，上述時限以此配置為準。5. 只提供 Linux 格式附加樣例文件。6. 評測在 NOI Linux 下進行。7. 編譯時不打開任何優(yōu)化選項。組合數(shù)問題（problem)【問題描述】組合數(shù)表示的是從 n 個物品中選出 m 個物品的方案數(shù)。舉個例子，從(1, 2, 3)三

25、個物品中選擇兩個物品可以有(1, 2),(1, 3),(2, 3)這三種選擇方法。根據(jù)組合數(shù)的定義，我們可以給出計算組合數(shù)的一般公式：其中 n! = 1 × 2 × · · · × n 。小蔥想知道如果給定 n, m 和 k ，對于所有的 0 i n, 0 j min (i, m) 有多少對i(i, j) 滿足是 k 的倍數(shù)?！据斎敫袷健繌奈募?problem.in 中讀入數(shù)據(jù)。第一行有兩個整數(shù) t, k ，其中 t 代表該測試點總共有多少組測試數(shù)據(jù)，k 的意義見【問題描述】。接下來 t 行每行兩個整數(shù) n, m ，其中 n, m 的

26、意義見【問題描述】。【輸出格式】輸出到文件 problem.out 中。t行，每行一個整數(shù)代表所有的 0 i n, 0 j min (i, m) 中有多少對 (i, j) 滿足是 k 的倍數(shù)。【樣例 1 輸入】1 23 3【樣例 1 輸出】1【樣例 1 說明】在所有可能的情況中，只有 = 2 是2 的倍數(shù)。【樣例 2 輸入】2 54 56 7【樣例 2 輸出】07【子任務】測試點 nmkt1 3 3= 2= 12= 3 1043 7 7= 4= 14= 5 1045 10 10= 6= 16= 7 1047 20 100= 8= 18= 9 1049 25 2000= 10= 110= 11

27、10411 60 20= 12= 112= 13 10413 100 25= 14= 114= 15 10415 60= 16= 116= 17 10417 2000 100= 18= 118= 19 10419 2000= 20= 120= 21 104蚯蚓（earthworm)【問題描述】本題中，我們將用符號 LcJ 表示對 c 向下取整，例如： L3.0J = L3.1J = L3.9J = 3。蛐蛐國最近蚯蚓成災了！隔壁跳蚤國的跳蚤也拿蚯蚓們沒辦法，蛐蛐國王只好去請神刀手來幫他們消滅蚯蚓。蛐蛐國里現(xiàn)在共有 n 只蚯蚓（ n 為正整數(shù)）。每只蚯蚓擁有長度，我們設(shè)第 i 只蚯蚓的長度為 a

28、i ( i = 1, 2, . . . , n )，并保證所有的長度都是非負整數(shù)（即：可能存在長度為0的蚯蚓）。每一秒，神刀手會在所有的蚯蚓中，準確地找到最長的那一只（如有多個則任選一個）將其切成兩半。神刀手切開蚯蚓的位置由常數(shù) p （是滿足 0 < p < 1 的有理數(shù)）決定，設(shè)這只蚯蚓長度為 x ，神刀手會將其切成兩只長度分別為 LpxJ 和 x LpxJ 的蚯蚓。特殊地，如果這兩個數(shù)的其中一個等于 0 ，則這個長度為 0 的蚯蚓也會被保留。此 外，除了剛剛產(chǎn)生的兩只新蚯蚓，其余蚯蚓的長度都會增加 q（是一個非負整常數(shù)）。蛐蛐國王知道這樣不是長久之計，因為蚯蚓不僅會越來越多，還

29、會越來越長。蛐 蛐國王決定求助于一位有著洪荒之力的神秘人物，但是救兵還需要 m 秒才能到來.（m 為非負整數(shù)）蛐蛐國王希望知道這 m 秒內(nèi)的戰(zhàn)況。 具體來說，他希望知道：l m 秒內(nèi)，每一秒被切斷的蚯蚓被切斷前的長度（有 m 個數(shù)）；l m 秒后，所有蚯蚓的長度（有 n + m 個數(shù)）。蛐蛐國王當然知道怎么做啦! 但是他想考考你.【輸入格式】從文件 earthworm.in 中讀入數(shù)據(jù)。第一行包含六個整數(shù) n, m, q, u, v, t ，其中： n, m, q 的意義見【問題描述】； u, v, t 均 為正整數(shù)；你需要自己計算 p = u/v （保證 0 < u < v ）；

30、t 是輸出參數(shù)，其含義將會在【輸出格式】中解釋。第二行包含 n 個非負整數(shù)，為 a1, a2, . . . , an ，即初始時 n 只蚯蚓的長度。同一行中相鄰的兩個數(shù)之間，恰好用一個空格隔開。保證 1 n 105 ， 0 m 7 × 106 ， 0 < u < v 109 ， 0 q 200 ， 1 t 71 ，0 ai 108 。【輸出格式】輸出到文件 earthworm.out第一行輸出 個整數(shù)，按時間順序，依次輸出第 t秒，第 2t 秒，第 3t 秒，.被切 斷蚯蚓（在被切斷前）的長度。第二行輸出個整數(shù)，輸出 m 秒后蚯蚓的長度：需要按從大到小的順序，依次輸出排名

31、第 t ，第 2t ，第 3t ，. . . . . . 的長度。同一行中相鄰的兩個數(shù)之間，恰好用一個空格隔開。即使某一行沒有任何數(shù)需要輸出，你也應輸出一個空行。請閱讀樣例來更好地理解這個格式?！緲永?1 輸入】3 7 1 1 3 13 3 2【樣例 1 輸出】3 4 4 4 5 5 66 6 6 5 5 4 4 3 2 2【樣例 1 說明】在神刀手到來前：3 只蚯蚓的長度為 3,3,2。1 秒后：一只長度為 3 的蚯蚓被切成了兩只長度分別為 1 和 2 的蚯蚓，其余蚯蚓的長度增加了 1。最終 4 只蚯蚓的長度分別為(1,2),4,3。括號表示這個位置剛剛有一只蚯蚓被切斷。2 秒后：一只長度為

32、 4 的蚯蚓被切成了 1 和 3。5 只蚯蚓的長度分別為：2,3,(1,3),4。3 秒后：一只長度為 4 的蚯蚓被切斷。6 只蚯蚓的長度分別為：3,4,2,4,(1,3)。4 秒后：一只長度為 4 的蚯蚓被切斷。7 只蚯蚓的長度分別為：4,(1,3),3,5,2,4。5 秒后：一只長度為 5 的蚯蚓被切斷。8 只蚯蚓的長度分別為：5,2,4,4,(1,4),3,5。6 秒后：一只長度為 5 的蚯蚓被切斷。9 只蚯蚓的長度分別為：(1,4),3,5,5,2,5,4,6。7 秒后：一只長度為 6 的蚯蚓被切斷。10 只蚯蚓的長度分別為：2,5,4,6,6,3,6,5,(2,4)。所以，7 秒內(nèi)被

33、切斷的蚯蚓的長度依次為 3,4,4,4,5,5,6。7 秒后，所有蚯蚓長度從大到小排序為 6,6,6,5,5,4,4,3,2,2?！緲永?2 輸入】3 7 1 1 3 23 3 2【樣例 2 輸出】4 4 56 5 4 3 2【樣例 2 說明】這個數(shù)據(jù)中只有 t = 2 與上個數(shù)據(jù)不同。只需在每行都改為每兩個數(shù)輸出一個數(shù)即可。雖然第一行最后有一個 6 沒有被輸出，但是第二行仍然要重新從第二個數(shù)再開始輸出?！緲永?3 輸入】3 7 1 1 3 93 3 2【樣例 3 輸出】2【樣例 3 說明】這個數(shù)據(jù)中只有 t = 9 與上個數(shù)據(jù)不同。注意第一行沒有數(shù)要輸出，但也要輸出一個空行?！咀尤蝿铡縧 測

34、試點 1 3 滿足 m = 0 。l 測試點 4 7 滿足 n, m 1, 000 。l 測試點 8 14 滿足 q = 0 ，其中測試點 8 9 還滿足 m 105 。l 測試點 15 18 滿足 m 3 × 105 。l 測試點 19 20 沒有特殊的約定，參見原始的數(shù)據(jù)范圍。l 測試點 1 12， 15 16 還滿足 v 2 ， 這意味著 u, v 的唯一可能的取值是u = 1, v = 2 ，即 p = 0.5 。這可能會對解決問題有特殊的幫助。每個測試點的詳細數(shù)據(jù)范圍見下表。測試點nmtaivq1= 1= 0= 1 106 2= 02= 1033= 1054= 1= 103

35、5= 1036= 1 2007= 1038= 5 × 104= 5 × 104= 09= 105= 105= 210= 2 × 106= 2111= 2.5 × 106= 2612= 3.5 × 106= 36 10713= 5 × 106= 51 10914= 7 × 106= 71 10815= 5 × 104= 5 × 106= 1 2 20016= 1.5 × 106= 217= 105= 105= 3 10918= 3 × 105= 419= 3.5 × 106=

36、3620= 7 × 106= 71憤怒的小鳥（angrybirds)【問題描述】Kiana 最近沉迷于一款神奇的游戲無法自拔。簡單來說，這款游戲是在一個平面上進行的。有一架彈弓位于 (0, 0) 處，每次 Kiana 可以用它向第一象限發(fā)射一只紅色的小鳥，小鳥們的飛行軌跡均為形如 y = ax2 + bx 的曲線，其中 a, b 是 Kiana 指定的參數(shù)，且必須滿足 a < 0。當小鳥落回地面（即 x 軸）時，它就會瞬間消失。在游戲的某個關(guān)卡里，平面的第一象限中有 n 只綠色的小豬，其中第 i 只小豬所在的坐標為 (xi, yi)。如果某只小鳥的飛行軌跡經(jīng)過了 (xi, yi

37、) ，那么第 i 只小豬就會被消滅掉，同時小鳥將會沿著原先的軌跡繼續(xù)飛行；如果一只小鳥的飛行軌跡沒有經(jīng)過 (xi, yi) ，那么這只小鳥飛行的全過程就不會對第 i 只小豬產(chǎn)生任何影響。例如，若兩只小豬分別位于 (1, 3) 和 (3, 3) ，Kiana 可以選擇發(fā)射一只飛行軌跡為 y =x2 + 4x 的小鳥，這樣兩只小豬就會被這只小鳥一起消滅。而這個游戲的目的，就是通過發(fā)射小鳥消滅所有的小豬。這款神奇游戲的每個關(guān)卡對 Kiana 來說都很難，所以 Kiana 還輸入了一些神秘的指令，使得自己能更輕松地完成這個游戲。這些指令將在【輸入格式】中詳述。假設(shè)這款游戲一共有 T 個關(guān)卡，現(xiàn)在 Kiana 想知道，對于每一個關(guān)卡，至少需要發(fā)射多少只小鳥才能消滅所有的小豬。由于她不會算，