信息學(xué)-騙分導(dǎo)論

新版騙分導(dǎo)論THENEWGUIDEOFCHEATINGININFORMATICSOLYMPIAD目錄第1章緒論第2章從無解出發(fā)2.1無解情況2.2樣例——白送的分數(shù)第3章“艱苦樸素永不忘”3.1模擬3.2萬能鑰匙——DFS第4章騙分的關(guān)鍵——猜想4.1聽天由命4.2猜測答案4.3尋找規(guī)律4.4小數(shù)據(jù)殺手——打表第5章做貪心的人5.1貪心的算法5.2貪心地得分第6章C++的福利6.1快速排序6.2“如意金箍棒”第7章“寧為玉碎，不為瓦全”第8章實戰(zhàn)演練第9章結(jié)語第1章緒論在Oier中，有一句話廣為流傳：任何蒟蒻必須經(jīng)過大量的刷題練習(xí)才能成為大牛乃至于神牛。這就是著名的lzn定理。然而，我們這些蒟蒻們，沒有經(jīng)過那么多歷練，卻要和大牛們同場競技，我們該怎么以弱勝強呢？答案就是：騙分那么，騙分是什么呢？騙分就是用簡單的程序（比標(biāo)準(zhǔn)算法簡單很多，保證蒟蒻能輕松搞定的程序），盡可能多得騙取分數(shù)。讓我們走進這本《新版騙分導(dǎo)論》，來學(xué)習(xí)騙分的技巧，來挑戰(zhàn)神牛吧！第2章從無解出發(fā)2.1無解情況在很多題目中都有這句話：“若無解，請輸出-1.”看到這句話時，騙分的蒟蒻們就欣喜若狂，因為——數(shù)據(jù)中必定會有無解的情況！那么，只要打出下面這個程序：printf(“-1”);就能得到10分，甚至20分，30分！舉個例子：NOIP2012第4題，文化之旅題目描述Description有一位使者要游歷各國，他每到一個國家，都能學(xué)到一種文化，但他不愿意學(xué)習(xí)任何一種文化超過一次（即如果他學(xué)習(xí)了某種文化，則他就不能到達其他有這種文化的國家）。不同的國家可能有相同的文化。不同文化的國家對其他文化的看法不同，有些文化會排斥外來文化（即如果他學(xué)習(xí)了某種文化，則他不能到達排斥這種文化的其他國家）。現(xiàn)給定各個國家間的地理關(guān)系，各個國家的文化，每種文化對其他文化的看法，以及這位使者游歷的起點和終點（在起點和終點也會學(xué)習(xí)當(dāng)?shù)氐奈幕?，國家間的道路距離，試求從起點到終點最少需走多少路。輸入描述InputDescription第一行為五個整數(shù)N，K，M，S，T，每兩個整數(shù)之間用一個空格隔開，依次代表國家個數(shù)（國家編號為1到N），文化種數(shù)（文化編號為1到K），道路的條數(shù)，以及起點和終點的編號（保證S不等于T）；第二行為N個整數(shù)，每兩個整數(shù)之間用一個空格隔開，其中第i個數(shù)Ci，表示國家i的文化為Ci。接下來的K行，每行K個整數(shù)，每兩個整數(shù)之間用一個空格隔開，記第i行的第j個數(shù)為aij，aij=1表示文化i排斥外來文化j（i等于j時表示排斥相同文化的外來人），aij=0表示不排斥（注意i排斥j并不保證j一定也排斥i）。接下來的M行，每行三個整數(shù)u，v，d，每兩個整數(shù)之間用一個空格隔開，表示國家u與國家v有一條距離為d的可雙向通行的道路（保證u不等于v，兩個國家之間可能有多條道路）。輸出描述OutputDescription輸出只有一行，一個整數(shù)，表示使者從起點國家到達終點國家最少需要走的距離數(shù)（如果無解則輸出-1）。樣例輸入SampleInput輸入樣例1221121201101210輸入樣例2221121201001210樣例輸出SampleOutput輸出樣例1-1輸出樣例210數(shù)據(jù)范圍及提示DataSize&Hint【輸入輸出樣例1說明】由于到國家2必須要經(jīng)過國家1，而國家2的文明卻排斥國家1的文明，所以不可能到達國家2?！据斎胼敵鰳永?說明】路線為1->2?！緮?shù)據(jù)范圍】對于20%的數(shù)據(jù)，有2≤N≤8，K≤5；對于30%的數(shù)據(jù)，有2≤N≤10，K≤5；對于50%的數(shù)據(jù)，有2≤N≤20，K≤8；對于70%的數(shù)據(jù)，有2≤N≤100，K≤10；對于100%的數(shù)據(jù)，有2≤N≤100，1≤K≤100，1≤M≤N2，1≤ki≤K，1≤u,v≤N，1≤d≤1000，S≠T，1≤S,T≤N。這道題看起來很復(fù)雜，但其中有振奮人心的一句話“輸出-1”，我考試時就高興壞了（當(dāng)時我才初一，水平太爛），隨手打了個printf(“-1”);,得10分。2.2樣例——白送的分數(shù)每道題目的后面，都有一組“樣例輸入”和“樣例輸出”。它們的價值極大，不僅能初步幫你檢驗程序的對錯（特別坑的樣例除外），而且，如果你不會做這道題（這種情況蒟蒻們已經(jīng)司空見慣了），你就可以直接輸出樣例！例如美國的USACO，它的題目有一個規(guī)則，就是第一組數(shù)據(jù)必須是樣例。那么，只要你輸出所有的樣例，你就能得到100分（滿分1000）！這是相當(dāng)可觀的分數(shù)了?，F(xiàn)在，你已經(jīng)掌握了最基礎(chǔ)的騙分技巧。只要你會基本的輸入輸出語句，你就能實現(xiàn)這些騙分方法。那么，如果你有一定的基礎(chǔ)，請看下一章——我將教你怎樣用簡單方法騙取部分分數(shù)。第3章“艱苦樸素永不忘”本章的標(biāo)題來源于《學(xué)習(xí)雷鋒好榜樣》的一句歌詞，但我不是想教導(dǎo)你們學(xué)習(xí)雷鋒精神，而是學(xué)習(xí)騙分！看到“樸素”兩個字了嗎？它們代表了一類算法，主要有模擬和DFS。下面我就來介紹它們在騙分中的應(yīng)用。3.1模擬所謂模擬，就是用計算機程序來模擬實際的事件。例如NOIP2012的“尋寶”，就是寫一個程序來模擬小明上藏寶塔的動作。較繁的模擬就不叫騙分了，我這里也不討論這個問題。模擬主要可以應(yīng)用在騙高級數(shù)據(jù)結(jié)構(gòu)題上的分，例如線段樹。下面舉一個例子來說明一下。排隊(USACO2007JanuarySilver)【問題描述】每天，農(nóng)夫約翰的N（1≤N≤50000）頭奶?？偸前赐豁樞蚺藕藐牐幸惶?，約翰決定讓一些牛玩一場飛盤游戲（UltimateFrisbee），他決定在隊列里選擇一群位置連續(xù)的奶牛進行比賽，為了避免比賽結(jié)果過于懸殊，要求挑出的奶牛身高不要相差太大。約翰準(zhǔn)備了Q（1≤Q≤200000）組奶牛選擇，并告訴你所有奶牛的身高Hi（1≤Hi≤106）。他想知道每組里最高的奶牛和最矮的奶牛身高差是多少。注意：在最大的數(shù)據(jù)上，輸入輸出將占據(jù)大部分時間?！据斎搿康谝恍?，兩個用空格隔開的整數(shù)N和Q。第2到第N+1行，每行一個整數(shù)，第i+1行表示第i頭奶牛的身高Hi第N+2到第N+Q+1行，每行兩個用空格隔開的整數(shù)A和B，表示選擇從A到B的所有牛（1≤A≤B≤N）【輸出】共Q行，每行一個整數(shù)，代表每個詢問的答案。輸入樣例輸出樣例63173425154622630對于這個例子，大牛們可以寫個線段樹，而我們蒟蒻，就模擬吧。附模擬程序：for(inti=1;i<=q;i++){scanf(“%d%d”,&a,&b);intmin=INT_MAX,max=INT_MIN;for(inti=a;i<=b;i++){if(h[i]<min)min=h[i];if(h[i]>max)max=h[i];}printf(“%d\n”,max-min);}程序簡潔明了，并且能高效騙分。本程序得50分。3.2萬能鑰匙——DFSDFS是圖論中的重要算法，但我們看來，圖論神馬的都是浮云，關(guān)鍵就是如何騙分。下面引出本書的第2條定理：DFS是萬能的。這對于你的騙分是至關(guān)重要的。比如說，一些動態(tài)規(guī)劃題，可以DFS；數(shù)學(xué)題，可以DFS；剪枝的題，更能DFS。下面以一道省選題為例，解釋一下DFS騙分。例題：NOIP2003，采藥題目描述Description辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應(yīng)該可以讓采到的草藥的總價值最大?！比绻闶浅匠?，你能完成這個任務(wù)嗎？輸入描述InputDescription輸入第一行有兩個整數(shù)T（1<=T<=1000）和M（1<=M<=100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值。輸出描述OutputDescription輸出包括一行，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。樣例輸入SampleInput7037110069112樣例輸出SampleOutput3數(shù)據(jù)范圍及提示DataSize&Hint對于30%的數(shù)據(jù)，M<=10；對于全部的數(shù)據(jù)，M<=100。這題的方法很簡單。我們瞄準(zhǔn)20%的數(shù)據(jù)來做，可以用DFS枚舉方案，然后模擬計算出最優(yōu)解。附一個大致的代碼：voidDFS(intd,intc){if(d==n){if(c>ans)ans=c;return;}DFS(d+1,c+w[i]);DFS(d+1,c);}騙分的關(guān)鍵——猜想4.1聽天由命如果你覺得你的人品很好，可以試試這一招——輸出隨機數(shù)。先看一下代碼：#include<stdlib.h>#include<time.h>//以上兩個頭文件必須加srand(time(NULL));//輸出隨機數(shù)前執(zhí)行此語句printf(“%d”,rand()%X);//輸出一個0~X-1的隨機整數(shù)。這種方法適用于輸出一個整數(shù)（或判斷是否）的題目中，答案的范圍越小越好。讓老天決定你的得分吧。據(jù)說，在NOIP2013中，有人最后一題不會，憤然打了個隨機數(shù)，結(jié)果得了70分啊!!4.2猜測答案有些時候，問題的答案可能很有特點：對于大多數(shù)情況，答案是一樣的。這時，騙分就該出手了。你需要做的，就是發(fā)掘出這個答案，然后直接輸出。有時，你需要運用第3章中學(xué)到的知識，先寫出樸素算法，然后造一些數(shù)據(jù)，可能就會發(fā)現(xiàn)規(guī)律。例如，本班月賽中有一道題：炸毀計劃【問題描述】皇軍侵占了通往招遠的黃金要道。為了保護渤海通道的安全，使得黃金能夠順利地運送到敵后戰(zhàn)略總指揮地延安，從而購買戰(zhàn)需武器，所以我們要通過你的程序確定這條戰(zhàn)略走廊是否安全。已知我們有N座小島，只有使得每一個小島都能與其他任意一個小島聯(lián)通才能保證走廊的安全。每個小島之間只能通過若干雙向聯(lián)通的橋保持聯(lián)系，已知有M座橋(Ai,Bi)表示第i座橋連接了Ai與Bi這兩座城市?，F(xiàn)在，敵人的炸藥只能炸毀其中一座橋，請問在僅僅炸毀這一座橋的情況下，能否保證所有島嶼安全，都能聯(lián)通起來。現(xiàn)在給出Q個詢問Ci，其中Ci表示橋梁編號，橋梁的編號按照輸入順序編號。每個詢問表示在僅僅炸毀第Ci座橋的情況下能否保證所有島嶼安全。如果可以，在輸出文件當(dāng)中，對應(yīng)輸入順序輸出yes，否則輸出no（輸出為半角英文單詞，區(qū)分大小寫，默認為小寫，不含任何小寫符號，每行輸出一個空格，忽略文末空格）?！据斎敫袷健康谝恍腥齻€整數(shù)N，M，Q，分別表示島嶼的個數(shù)，橋梁的個數(shù)和詢問的個數(shù)。第二行到第M+1行每行兩個整數(shù)。第i+1行有兩個整數(shù)AiBi表示這個橋梁的屬性。第M+2行有Q個整數(shù)Ci表示查詢?！据敵龈袷健縌行，表示查詢結(jié)果。【樣例】destroy.indestroy.out211121no【樣例范圍】對于80%的數(shù)據(jù)，N≤100。對于100%的數(shù)據(jù)，N≤1000，N,Q≤M≤2000。你發(fā)現(xiàn)問題了嗎？那么多座橋，炸一座就破壞島嶼的聯(lián)系，可能性微乎其微（除非特別設(shè)計數(shù)據(jù)）。那么，我們的騙分策略就出來了：對于所有詢問，輸出yes.果然，此算法效果不錯，得80分。現(xiàn)在知道猜測答案的厲害了吧？4.3尋找規(guī)律首先聲明：本節(jié)講的規(guī)律不是正當(dāng)?shù)乃惴ㄒ?guī)律，而是數(shù)據(jù)的特點。某些題目會給你很多樣例，你就可以觀察他們的特點了。有時，數(shù)據(jù)中的某一個（或幾個）數(shù)，能通過簡單的關(guān)系直接算出答案。只要你找到了規(guī)律，在很多情況下你都能得到可觀的分數(shù)。這樣的題目大多出現(xiàn)在NOI或更高等級的比賽中，本人蒟蒻一個，就不舉例了。傳說某人去省選時專門琢磨數(shù)據(jù)的規(guī)律，結(jié)果有一題得了30分。4.4小數(shù)據(jù)殺手——打表我認識一個人，他在某老師家上C語言家教，老師每講一題，他都喊一句：“打表行嗎？”他真的是打表的忠實粉絲。表雖然不能亂打，但還是很有用的。先看一個例子：NOIP2003棧題目描述Description棧是計算機中經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，簡單的說，棧就是限制在一端進行插入刪除操作的線性表。棧有兩種最重要的操作，即pop（從棧頂彈出一個元素）和push（將一個元素進棧）。棧的重要性不言自明，任何一門數(shù)據(jù)結(jié)構(gòu)的課程都會介紹棧。寧寧同學(xué)在復(fù)習(xí)棧的基本概念時，想到了一個書上沒有講過的問題，而他自己無法給出答案，所以需要你的幫忙寧寧考慮的是這樣一個問題：一個操作數(shù)序列，從1，2，一直到n（圖示為1到3的情況），棧A的深度大于n?，F(xiàn)在可以進行兩種操作，1.將一個數(shù)，從操作數(shù)序列的頭端移到棧的頭端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的push操作）將一個數(shù)，從棧的頭端移到輸出序列的尾端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的pop操作）使用這兩種操作，由一個操作數(shù)序列就可以得到一系列的輸出序列，下圖所示為由123生成序列231的過程。（原始狀態(tài)如上圖所示）。你的程序?qū)o定的n，計算并輸出由操作數(shù)序列1，2，…，n經(jīng)過操作可能得到的輸出序列的總數(shù)。輸入描述InputDescription輸入文件只含一個整數(shù)n（1≤n≤18）輸出描述OutputDescription輸出文件只有一行，即可能輸出序列的總數(shù)目樣例輸入SampleInput3樣例輸出SampleOutput5這題看似復(fù)雜，但數(shù)據(jù)范圍太小，N<=18。所以，騙分程序就好寫了：inta[18]={1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};scanf(“%d”,&n):printf(“%d”,ans[n-1]);測試結(jié)果不言而喻，AC了。學(xué)完這一章，你已基本掌握了騙分技巧。下面的內(nèi)容涉及一點算法知識，難度有所增加。蒟蒻中的蒟蒻可以止步于此了。第5章做貪心的人5.1貪心的算法給你一堆紙幣，讓你挑一張，相信你一定會挑面值最大的。其實，這就是貪心算法。貪心算法是個復(fù)雜的問題，但你不用管那么多。我們只關(guān)心騙分。給你一個問題，讓你從一些東西中選出一些，你就可以使用貪心的方法，盡量挑好的。舉個例子：這是我們的市隊選拔的一道題。有趣的問題【問題描述】2013年的NOIP結(jié)束后，Smart發(fā)現(xiàn)自己又被題目碾壓了，心里非常地不爽，于是暗下決心瘋狂地刷數(shù)學(xué)題目，做到天昏地暗、廢寢忘食，準(zhǔn)備在今年的中考中大展身手。有一天，他在做題時發(fā)現(xiàn)了一個有趣的問題：給定n個二元組(ai,bi)i)，記函數(shù)：y=100*sigma(ai)/sigma(bi);將函數(shù)y的值四舍五入取整。現(xiàn)將n個二元組去掉其中的k個計算一個新的y值（也四舍五入取整），均能滿足：y<=z，求出最小的z值。Smart想讓你幫他一起找出最小的z值?！据斎敫袷健枯斎氚嘟M測試數(shù)據(jù)。每組測試數(shù)據(jù)第一行兩個整數(shù)：n和k；第二行為n個數(shù)：a1a2……an；第三行為；n個數(shù)：b1b2……bn。輸入數(shù)據(jù)當(dāng)n、k均為0時結(jié)束?！据敵龈袷健繉τ诿拷M測試數(shù)據(jù)輸出一行，即找出的最小的冘值。注意：為避免精度四舍五入出現(xiàn)誤差，測試點保證每個函數(shù)值與最終結(jié)果的差值至少為0.001。【樣例】math.in31501516421279567900math.out83100【數(shù)據(jù)范圍】對于40%的數(shù)據(jù)：n≤20；對于70%的數(shù)據(jù)：n≤1000；對于100%的數(shù)據(jù)：n≤10000，ai,bi都在int范圍內(nèi)。這題讓人望而生畏，但我們有貪心的手段。每個二元組的a值是乘到答案中的，所以a越大越好，那么只要選擇出最小的k個去掉即可。代碼就不寫了，因為這個設(shè)計到下一章的內(nèi)容：排序。此代碼得20分。5.2貪心地得分我們已經(jīng)學(xué)了很多騙分方法，但他們中的大多效率并不高，一般能騙10~20分。這不能滿足我們的貪心。然而，我們可以合成騙分的程序。舉個最簡單的例子，有些含有無解情況的題目，它們同樣有樣例。我們可以寫這個程序if(是樣例)printf(樣例);elseprintf(“-1”);這樣也許能變10分為20分，甚至更多。當(dāng)然，合并騙分方法時要注意，不要重復(fù)騙同一種情況，或漏考慮一些情況。大量能騙分的問題都能用此法，大家可以試試用新方法騙2.1中的例子“文化之旅”。第6章C++的福利（請P黨們跳過本章，這不是你們的福利）在C++中，有一個好東西，名喚STL，被萬千Oier們所崇拜，所喜愛。下面讓我們走進STL。6.1快速排序快速排序是一個經(jīng)典算法，也是C++黨的經(jīng)典福利。他們有這樣的代碼：#include<algorithm>//這是必須的sort(A,A+n);//對一個下標(biāo)從0開始存儲，長度為n的數(shù)組升序排序就這么簡單，完成了P黨一大堆代碼干的事情。6.2“如意金箍棒”C++里有一種東西，叫vector容器。它好比如意金箍棒，可以隨著元素的數(shù)量而改變大小。它其實就是數(shù)組，卻比數(shù)組強得多。下面看看它的幾種操作：vector<int>V;//定義V.push_back(x);//末尾增加一個元素xV.pop_back();//末尾刪除一個元素V.size();//返回容器中的元素個數(shù)它同樣可以使用下標(biāo)訪問。（從0開始）第7章“寧為玉碎，不為瓦全”至此，我已介紹完了我所知的騙分方法。如果上面的方法都不奏效，我也無能為力。但是，我還有最后一招——有句古話說：“寧為玉碎，不為瓦全”。我們蒟蒻也應(yīng)有這樣的精神。騙不到分，就報復(fù)一下，卡評測以泄憤吧！卡評測主要有兩種方法：一是死循環(huán)，故意超時；二是進入終端，卡住編譯器。先介紹下第一種。代碼很簡單，請看：while(1);就是這短短一句話，就能卡住評測機長達10s，20s，甚至更多！對于測試點多、時限長的題目，這是個不錯的方法。第二種方法也很簡單，但危害性較大，建議不要在重要比賽中使用，否則可能讓你追悔莫及。它就是：include<con>（windows系統(tǒng)中使用）或#include</dev/console>（Linux系統(tǒng)中使用）它非常強大，可以卡住評測系統(tǒng)，使其永遠停止不了編譯你的程序。唯一的解除方法是，工作人員強行關(guān)機，重啟，重測。當(dāng)然，我不保證他們不會氣憤地把你的成績變成0分。請慎用此方法。第8章實戰(zhàn)演練下面我們來做一些習(xí)題，練習(xí)騙分技巧。我們來一起分析一下NOIP2013普及組的試題吧。記數(shù)問題（NOIP普及組2013第一題）(count.cpp/c/pas)描述試計算在區(qū)間1到n的所有整數(shù)中,數(shù)字x(0≤x≤9)共出現(xiàn)了多少次?例如,在1到11中,即在1、2、3、4、5、6、7、8、9、10、11中,數(shù)字1出現(xiàn)了4次?！据斎搿枯斎胛募麨閏ount.in。輸入共1行，包含2個整數(shù)n、x，之間用一個空格隔開【輸出】輸出文件名為count.out。輸出共1行，包含一個整數(shù)，表示x出現(xiàn)的次數(shù)。【輸入輸出樣例】count.incount.out1114限制每個測試點1s。【數(shù)據(jù)說明】對于100%的數(shù)據(jù)，1≤n≤1,000,000，0≤x≤9。表達式求值（noip2013普及組第二題）(expr.cpp/c/pas)描述給定一個只包含加法和乘法的算術(shù)表達式,請你編程計算表達式的值?！据斎搿枯斎胛募閑xpr.in。輸入僅有一行，為需要你計算的表達式，表達式中只包含數(shù)字、加法運算符“+”和乘，且沒有括號，所有參與運算的數(shù)字均為0到231-1之間的整數(shù)。輸入數(shù)據(jù)保法運算符“*”證這一行只有0~9、+、*這12種字符?！据敵觥枯敵鑫募麨閑xpr.out。輸出只有一行，包含一個整數(shù)，表示這個表達式的值。注意：當(dāng)答案長度多于4位時，請只輸出最后4位，前導(dǎo)0不輸出?！据斎胼敵鰳永?】expr.inexpr.out1+1*3+48【輸入輸出樣例2】expr.inexpr.out1+1234567890*17891【輸入輸出樣例3】expr.inexpr.out1+1000000003*14【輸入輸出樣例說明】樣例1計算的結(jié)果為8，直接輸出8。樣例2計算的結(jié)果為1234567891，輸出后4位，即7891。樣例3計算的結(jié)果為1000000004，輸出后4位，即4。【數(shù)據(jù)范圍】對于30%的數(shù)據(jù)，0≤表達式中加法運算符和乘法運算符的總數(shù)≤100；對于80%的數(shù)據(jù)，0≤表達式中加法運算符和乘法運算符的總數(shù)≤1000；對于100%的數(shù)據(jù)，0≤表達式中加法運算符和乘法運算符的總數(shù)≤100000。小朋友的數(shù)字（noip2013普及組第三題）(number.cpp/c/pas)描述有n個小朋友排成一列。每個小朋友手上都有一個數(shù)字,這個數(shù)字可正可負。規(guī)定每個小朋友的特征值等于排在他前面(包括他本人)的小朋友中連續(xù)若干個(最少有一個)小朋友手上的數(shù)字之和的最大值。作為這些小朋友的老師,你需要給每個小朋友一個分數(shù),分數(shù)是這樣規(guī)定的:第一個小朋友的分數(shù)是他的特征值,其它小朋友的分數(shù)為排在他前面的所有小朋友中(不包括他本人),小朋友分數(shù)加上其特征值的最大值。請計算所有小朋友分數(shù)的最大值,輸出時保持最大值的符號,將其絕對值對p取模后輸出。格式【輸入】輸入文件為number.in。第一行包含兩個正整數(shù)n、p，之間用一個空格隔開。第二行包含n個數(shù)，每兩個整數(shù)之間用一個空格隔開，表示每個小朋友手上的數(shù)字?！据敵觥枯敵鑫募麨閚umber.out。輸出只有一行，包含一個整數(shù)，表示最大分數(shù)對p取模的結(jié)果。【輸入輸出樣例1】number.innumber.out59972112345【輸入輸出樣例說明】小朋友的特征值分別為1、3、6、10、15，分數(shù)分別為1、2、5、11、21，最大值21對997的模是21?！据斎胼敵鰳永?】第2/4頁number.innumber.out57-1-1-1-1-1-1【輸入輸出樣例說明】小朋友的特征值分別為-1、-1、-1、-1、-1，分數(shù)分別為-1、-2、-2、-2、-2，最大值-1對7的模為-1，輸出-1?！緮?shù)據(jù)范圍】對于