1、模擬法,在自然界和日常生活中，許多現(xiàn)象具有不確定的性質(zhì)，有些問(wèn)題甚至很難建立數(shù)學(xué)模型，或者很難用計(jì)算機(jī)建立遞推、遞歸、枚舉、回溯法等算法。在這種情況下，一般采用模擬策略。所謂模擬策略就是模擬某個(gè)過(guò)程，通過(guò)改變數(shù)學(xué)模型的各種參數(shù)，進(jìn)而觀察變更這些參數(shù)所引起過(guò)程狀態(tài)的變化，由此展開算法設(shè)計(jì)。,模擬形式,隨機(jī)模擬 題目給定或者隱含某一概率。設(shè)計(jì)者利用隨機(jī)函數(shù)和取整函數(shù)設(shè)定某一范圍的隨機(jī)值，將符合概率的隨機(jī)值作為參數(shù)。然后根據(jù)這一模擬的數(shù)學(xué)模型展開算法設(shè)計(jì)。由于解題過(guò)程借助了計(jì)算機(jī)的偽隨機(jī)數(shù)發(fā)生數(shù)，其隨機(jī)的意義要比實(shí)際問(wèn)題中真實(shí)的隨機(jī)變量稍差一些，因此模擬效果有不確定的因素； 過(guò)程模擬 題目不給出概率

2、，要求編程者按照題意設(shè)計(jì)數(shù)學(xué)模型的各種參數(shù)，觀察變更這些參數(shù)所引起過(guò)程狀態(tài)的變化，由此展開算法設(shè)計(jì)。模擬效果完全取決于過(guò)程模擬的真實(shí)性和算法的正確性，不含任何不確定因素。由于過(guò)程模擬的結(jié)果無(wú)二義性，因此競(jìng)賽大都采用過(guò)程模擬。,模擬法的類型,直敘式模擬,篩選法模擬,構(gòu)造法模擬,直敘式模擬,直敘式模擬即按照試題要求展開模擬過(guò)程。編程者要忠實(shí)于原題，認(rèn)真審題，千萬(wàn)不要疏漏任何條件，精心設(shè)計(jì)方便模擬的數(shù)據(jù)結(jié)構(gòu)。“直敘式模擬”的難度取決于模擬對(duì)象所包含的動(dòng)態(tài)變化的屬性有多少，動(dòng)態(tài)屬性愈多，則難度愈大。,花生采摘,魯賓遜先生有一只寵物猴，名叫多多。這天，他們兩個(gè)正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼

3、著一張小小的紙條：“歡迎免費(fèi)品嘗我種的花生！熊字”。 魯賓遜先生和多多都很開心，因?yàn)榛ㄉ撬麄兊淖類?ài)。在告示牌背后，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)格（如圖1）。有經(jīng)驗(yàn)的多多一眼就能看出，每棵花生植株下的花生有多少。為了訓(xùn)練多多的算術(shù)，魯賓遜先生說(shuō)：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過(guò)你一定要在我限定的時(shí)間內(nèi)回到路邊?！?我們假定多多在每個(gè)單位時(shí)間內(nèi)，可以做下列四件事情中的一件： 1)從路邊跳到最靠近路邊（即第一行）的某棵花生植株； 2)從一棵植株跳到前后左右與之相鄰的另一棵植株； 3)采摘一棵植株下的花生

4、； 4)從最靠近路邊（即第一行）的某棵花生植株跳回路邊。 現(xiàn)在給定一塊花生田的大小和花生的分布，請(qǐng)問(wèn)在限定時(shí)間內(nèi)，多多最多可以采到多少個(gè)花生？注意可能只有部分植株下面長(zhǎng)有花生，假設(shè)這些植株下的花生個(gè)數(shù)各不相同。 例如在圖2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下長(zhǎng)有花生，個(gè)數(shù)分別為13, 7, 15, 9。沿著圖示的路線，多多在21個(gè)單位時(shí)間內(nèi)，最多可以采到37個(gè)花生。 【輸入文件】輸入文件peanuts.in的第一行包括三個(gè)整數(shù)，M, N和K，用空格隔開；表示花生田的大小為M * N（1M, N20），多多采花生的限定時(shí)間為K（0K1000

5、）個(gè)單位時(shí)間。接下來(lái)的M行，每行包括N個(gè)非負(fù)整數(shù)，也用空格隔開；第i + 1行的第j個(gè)整數(shù)Pij（0Pij 500）表示花生田里植株(i, j)下花生的數(shù)目，0表示該植株下沒(méi)有花生。 【輸出文件】輸出文件peanuts.out包括一行，這一行只包含一個(gè)整數(shù)，即在限定時(shí)間內(nèi)，多多最多可以采到花生的個(gè)數(shù)。,解法1:直譯模擬,每次在二維數(shù)組中找到當(dāng)前最大值的位置 若最大值為零，則由當(dāng)前位置直接返回路邊；否則判斷走至最大值位置后再返回路邊的時(shí)間是否來(lái)得及： 如果來(lái)得及，則移動(dòng)到最大值位置，把該位置的花生數(shù)置為零，累加已用時(shí)間； 如果來(lái)不及，就由當(dāng)前位置直接返回路邊。,設(shè) var t,m,n,k,max

6、,i,j,max1i,max1j,maxi,maxj,total:integer; 多多目前的行程為t；花生田的規(guī)模為m*n；多多采花生的限定時(shí)間為k ；最近采集花生的位置為（max1i,max1j），準(zhǔn)備采集花生的位置為（maxi，maxj），顯然兩個(gè)采集點(diǎn)的距離為 ；多多在限定時(shí)間內(nèi)可采集到的最多花生數(shù)為total p:array1.20,1.20of integer; 花生田。其中pi，j為花生田里植株(i, j)下花生的數(shù)目 由于多多在相鄰元素間移動(dòng)一步的時(shí)間為一個(gè)單位，因此除去多多從路邊往返數(shù)組第一行的2個(gè)單位時(shí)間，則多多在數(shù)組內(nèi)采集花生的時(shí)間不允許超過(guò)k-2（k=k-2）個(gè)時(shí)間單位

7、。 我們首先計(jì)算花生數(shù)最多的位置（max1i，max1j）和該位置的花生數(shù)max，將多多的行程t初始化為max1i。顯然，如果花生田里有花生(max0)且采集了花生最多的植株后可返回路邊（t+max1i-1k），則采集（max1i，max1j）位置的花生（pmax1i,max1j0；totaltotal+max）。然后計(jì)算下一個(gè)花生數(shù)最多的位置（maxi，maxj），將兩個(gè)采集點(diǎn)的距離計(jì)入t(tt+ )，并將（maxi，maxj）設(shè)為下一個(gè)采集目標(biāo)（max1imaxi;max1jmaxj）。 重復(fù)上述計(jì)算過(guò)程，直至花生田里無(wú)花生(max=0)或者采集（max1i，max1j）位置的花生后無(wú)法返

8、回路邊（t+max1i-1k）為止。由此得出算法：,readln(m,n,k);讀花生田的規(guī)模和多多采花生的限定時(shí)間 k:=k-2; 計(jì)算多多在數(shù)組內(nèi)采集花生的最多時(shí)間 max:=0;讀花生田的信息。計(jì)算花生數(shù)最多的位置（max1i，max1j）和該位置的花生數(shù)max for i:=1 to m do for j:=1 to n do begin read(pi,j); if pi,jmax then begin max:=pi,j;max1i:=i;max1j:=j；end;then end;for t:=max1i;total:=0; 多多的行程和采集的花生數(shù)初始化 while (t+ma

9、x1i-10) do若在限定時(shí)間內(nèi)回到路邊且找到花生最多的植株，則采摘它的花生，并累計(jì)采摘的花生總數(shù) begin pmax1i,max1j:=0;total:=total+max; max:=0;計(jì)算當(dāng)前花生數(shù)最多的位置（maxi，maxj）和該位置的花生數(shù)max for i:=1 to m do for j:=1 to n do if pi,jmax then begin max:=pi,j;maxi:=i;maxj:=j；end;then t:=t+1+abs(max1i-maxi)+abs(max1j-maxj);累計(jì)行程 max1i:=maxi;max1j:=maxj；從該位置出發(fā)，繼

10、續(xù)采摘花生 end;while writeln(total);輸出限定時(shí)間內(nèi)多多采到花生數(shù)的最大值 時(shí)間復(fù)雜度為O (k*n2),解法2:貪心算法,先將花生植株按花生數(shù)遞減的順序排列成一維數(shù)組，數(shù)組元素記錄下植株的花生數(shù)和位置。按照數(shù)組順序，找出距離之和不超過(guò)k-2、且最接近k-2的前若干個(gè)元素，將這些元素記錄的花生數(shù)累加起來(lái)，便構(gòu)成了問(wèn)題的解。算法的時(shí)間復(fù)雜度為O (n*log n +k)。,字符串的展開,【問(wèn)題描述】在初賽普及組的“閱讀程序?qū)懡Y(jié)果”的問(wèn)題中，我們?cè)o出一個(gè)字符串展開的例了：如果在輸入的字符串中，含有類似于“d-h”或“4-8”的子串，我們就把它當(dāng)作一種簡(jiǎn)寫，輸出時(shí)，用連續(xù)遞

11、增的字母或數(shù)字串替代其中的減號(hào)，即，將上面兩個(gè)子串分別輸出為“dcfgh”和“45678”。在本題中，我們通過(guò)增加些參數(shù)的設(shè)置，使字符串的展開更為靈活。具體約定如下： （1)遇到下面的情況需要做字符串的展開：在輸入的字符串中，出現(xiàn)了減號(hào)“”，減號(hào)兩側(cè)同為小寫字母或同為數(shù)字，且按照AScII碼的順序，減號(hào)右邊的字符嚴(yán)格大于左邊的字符。 (2)參數(shù)p1:展開方式。p1=1時(shí)，對(duì)于字母予串，填充小寫字母： p1=2時(shí)，對(duì)于字母子串，填充大寫字母。這兩種情況下數(shù)字子串的填充方式相同。pl=3時(shí)，不論是字母r串還足數(shù)字子串，都用與要填充的字母?jìng)€(gè)數(shù)相同的星號(hào)*來(lái)填充。 (3)參數(shù)p2：填充字符的重復(fù)個(gè)數(shù)。

12、p2=k表示同一個(gè)字符要連續(xù)填充k個(gè)。例如，當(dāng)p2=3時(shí)，子串“d-h”應(yīng) 展 為“deeefffgggh”。減號(hào)兩側(cè)的字符小變。,(4)參數(shù)p3：是否改為逆序：p3=l表示維持原有順序，p3=2表示采用逆序輸出，注意這時(shí)仍然不包括減號(hào)兩端的字符。例如當(dāng)p1=1、p2=2、p3=2時(shí)，子串“d-h”應(yīng)擴(kuò)展為“dggffeeh”。 (5)如果減號(hào)右邊的子符恰好是左邊字符的后繼只刪除中間的減號(hào)，例如：“de”應(yīng)輸出為“de”，“3-4”應(yīng)輸出為“34”。如果減號(hào)右邊的字符按照ASCLL碼的順序小于或等于左邊字符，輸出時(shí)，要保留中間的減號(hào)，例如：“d-d”應(yīng)輸出為“d-d”，“3-l”應(yīng)輸出為“3-

13、l”。 【輸入】輸入文件expandin包括兩行：第l行為用空格隔開的3個(gè)正整數(shù)，依次表示參數(shù)p1，p2，p3;第2行為一行字符串，僅由數(shù)字、小寫字母和減號(hào)“-”組成。行首和行末均無(wú)空格。 【輸出】輸出文件expandout只有一行，為展開后的字符串。 【限制】 40的數(shù)據(jù)滿足：寧符串長(zhǎng)度小超過(guò)5;100%的數(shù)據(jù)滿足：lp13，lp28，lp32。字符串長(zhǎng)度不超過(guò)100,試題簡(jiǎn)述,題目大意：給出一個(gè)字符串（串長(zhǎng)100），對(duì)于串中出現(xiàn)-符號(hào)，且-左右兩邊均為小寫字母或數(shù)字，且左邊的比右邊的小，則需要按要求將它展開。 其中有三個(gè)展開參數(shù)，p1，p2，p3。 p1：展開方式。p1=1時(shí)，對(duì)于字母子串

14、填充小寫字母；p1=2時(shí)，對(duì)于字母子串填寫大寫字母；p1=3時(shí)，無(wú)論是字符串還是數(shù)字串都填寫*。 p2：填充字符的重復(fù)個(gè)數(shù)。 p3：是否為逆序。,算法,直接模擬。對(duì)于每一個(gè)-，判斷是否需要展開即可。算法復(fù)雜度O(L)（L為答案字符串長(zhǎng)度）。設(shè) 展開后的目標(biāo)串為ans，長(zhǎng)度為tot； 初始串st，string類型;,判別是否需要展開,設(shè)-左右的字符分別為ch1和ch2。若ch1和ch2同為數(shù)碼或同為字母且遞增，則需要展開；否則不需要展開。這一判別過(guò)程由布爾函數(shù)check(ch1,ch2)描述： function check(ch1,ch2:char):boolean;若字符ch1和ch2同數(shù)碼或

15、同字母且遞增，則返回true；否則返回false begin check:=false; if(ch1 in 0.9)and(ch2 in 0.9) or(ch1 in a.z)and(ch2 in a.z) then if ch1ch2 then check:=true end;,展開規(guī)則,若相鄰的兩個(gè)同類型且遞增的字符ch1和ch2，則需要被展開的中間字符按照序數(shù)計(jì)算為ord(ch1)+1ord(ch2)-1，其中每個(gè)字符被展開p2次，展開的內(nèi)容由p1決定，順序由p3決定： ， 其中當(dāng)展開字母（p1=1,2） 時(shí)，p3=,procedure add(ch1,ch2:char);輸入相鄰的兩

16、個(gè)同類型且遞增的字符，按要求展開 var i,j,s,e:longint; begin s:=ord(ch1);e:=ord(ch2);計(jì)算兩個(gè)字符的asll碼 if p1=3若填寫 then begin for i:=s+1 to e-1 do按照字典序，ch1與ch2間的每個(gè)中間字符用p2個(gè)取代 for j:=1 to p2 do begininc(tot);anstot:=*end; exit end; if p1=2若填充大寫字母，則首尾字符取大寫字母的asll碼 then begin if ch1 in a.z then begin s:=s-32;e:=e-32 end end;

17、if p3=1若正序，則按照字典順序，ch1至ch2間的每個(gè)中間字符重復(fù)p2次 then for i:=s+1 to e-1 do for j:=1 to p2 do begin inc(tot);anstot:=chr(i)end else for i:=e-1 downto s+1 do若逆序，則按照字典逆序，ch2至ch1的每個(gè)中間字符重復(fù)p2次 for j:=1 to p2 do begin inc(tot); anstot:=chr(i) end end;,主程序,readln(p1,p2,p3);讀展開方式 readln(st);讀初始串 l:=length(st);計(jì)算初始串的長(zhǎng)

18、度 tot:=1;ans1:=st1;第個(gè)字符進(jìn)入目標(biāo)串 for i:=2 to l-1 do逐個(gè)字符展開 if sti=- then begin if check(sti-1,sti+1)若相鄰的兩個(gè)字符同類型且遞增，則按照要求展開；否則第i個(gè)字符進(jìn)入目標(biāo)串 then add(sti-1,sti+1) else begin inc(tot);anstot:=sti end end else begin inc(tot);anstot:=sti end; 否則第i個(gè)字符進(jìn)入目標(biāo)串 inc(tot); anstot:=stl最后一個(gè)字符進(jìn)入目標(biāo)串 for i:=1 to tot do write

19、(ansi);輸出展開后的目標(biāo)串 writeln;,昂貴的聘禮,年輕的探險(xiǎn)家來(lái)到了一個(gè)印第安部落里。在那里他和酋長(zhǎng)的女兒相愛(ài)了，于是便向酋長(zhǎng)去求親。酋長(zhǎng)要他用10000個(gè)金幣作為聘禮才答應(yīng)把女兒嫁給他。探險(xiǎn)家拿不出這么多金幣，便請(qǐng)求酋長(zhǎng)降低要求。酋長(zhǎng)說(shuō)：“嗯，如果你能夠替我弄到大祭司的皮襖，我可以只要8000金幣。如果你能夠弄來(lái)他的水晶球，那么只要5000金幣就行了?！碧诫U(xiǎn)家就跑到大祭司那里，向他要求皮襖或水晶球，大祭司要他用金幣來(lái)?yè)Q，或者替他弄來(lái)其他的東西，他可以降低價(jià)格。探險(xiǎn)家于是又跑到其他地方，其他人也提出了類似的要求，或者直接用金幣換，或者找到其他東西就可以降低價(jià)格。不過(guò)探險(xiǎn)家沒(méi)必要用

20、多樣?xùn)|西去換一樣?xùn)|西，因?yàn)椴粫?huì)得到更低的價(jià)格。探險(xiǎn)家現(xiàn)在很需要你的幫忙，讓他用最少的金幣娶到自己的心上人。另外他要告訴你的是，在這個(gè)部落里，等級(jí)觀念十分森嚴(yán)。地位差距超過(guò)一定限制的兩個(gè)人之間不會(huì)進(jìn)行任何形式的直接接觸，包括交易。他是一個(gè)外來(lái)人，所以可以不受這些限制。但是如果他和某個(gè)地位較低的人進(jìn)行了交易，地位較高的的人不會(huì)再和他交易，他們認(rèn)為這樣等于是間接接觸，反過(guò)來(lái)也一樣。因此你需要在考慮所有的情況以后給他提供一個(gè)最好的方案。,為了方便起見(jiàn)，我們把所有的物品從1開始進(jìn)行編號(hào)，酋長(zhǎng)的允諾也看作一個(gè)物品，并且編號(hào)總是1。每個(gè)物品都有對(duì)應(yīng)的價(jià)格P，主人的地位等級(jí)L，以及一系列的替代品Ti和該替代品

21、所對(duì)應(yīng)的“優(yōu)惠”Vi。如果兩人地位等級(jí)差距超過(guò)了M，就不能“間接交易”。你必須根據(jù)這些數(shù)據(jù)來(lái)計(jì)算出探險(xiǎn)家最少需要多少金幣才能娶到酋長(zhǎng)的女兒。 輸入文件:M，N（1=N=100），依次表示地位等級(jí)差距限制和物品的總數(shù)。 按照編號(hào)從小到大依次給出了N個(gè)物品的描述。每個(gè)物品的描述開頭是三個(gè)非負(fù)整數(shù)P、L、X（XN），依次表示該物品的價(jià)格、主人的地位等級(jí)和替代品總數(shù)。接下來(lái)X行每行包括兩個(gè)整數(shù)T和V，分別表示替代品的編號(hào)和“優(yōu)惠價(jià)格”。 輸出文件:最少需要的金幣數(shù)。,數(shù)據(jù)結(jié)構(gòu),const maxn=100;物品數(shù)上限 type ny=nz;物品的指針變量 nz=array1.maxn,1.2 of l

22、ongint;替代品序列，包括每一個(gè)替代品的編號(hào)和“優(yōu)惠價(jià)格” nx=record p,x,l:longint; 物品的價(jià)格、替代品總數(shù)和主人的地位等級(jí) list:ny; 替代品序列 end; var map:array1.maxn of nx;物品序列 can:array1.maxn of boolean;記錄與當(dāng)前客戶的等級(jí)差距在限制范圍內(nèi)的客戶 p,l,x,i,j,m,n，l1:longint;,輸入信息,readln(m,n);輸入地位等級(jí)差距限制和物品總數(shù) readln(map1.p,map1.l,map1.x);讀入物品1的價(jià)格、主人的地位等級(jí)和替代品總數(shù) new(map1.lis

23、t);讀入物品1的每個(gè)替代品的編號(hào)和“優(yōu)惠價(jià)格” for i:=1 to map1.x do readln(map1.listi,1,map1.listi,2); for i:=2 to n do讀入物品2物品n的信息 with mapi do begin readln(p,l,x);new(list); for j:=1 to x do readln(listj,1,listj,2); end;,計(jì)算最少需要的金幣數(shù),遞推每一個(gè)客戶h(1hn) 11尋找每一個(gè)與客戶h的等級(jí)差距在限制范圍內(nèi)的客戶i 搜索客戶i的每一個(gè)可與客戶h交易的替代品j,若替代后花錢更少，則記下 pricei=minpr

24、icej+物品j的優(yōu)惠價(jià)，物品i的單價(jià) 12若當(dāng)前方案最佳（price1min），則調(diào)整min 最后輸出min,procedure solve; var i,j,now,more:longint; price:array1.maxnof longint; pricei為客戶i的最少花銷 ok:boolean;不存在更便宜的方案標(biāo)志 min,h:longint; 最少需要的金幣數(shù)和當(dāng)前客戶 begin min:=maxlongint;最少需要的金幣數(shù)初始化 for h:=1 to n do begin枚舉每一個(gè)客戶 fillchar(can,sizeof(can),false); for i:=

25、1 to n do標(biāo)記每一個(gè)與客戶h的等級(jí)差距在限制范圍內(nèi)的客戶 if (mapi.l-maph.l=0) and (mapi.l-maph.l=m) then cani:=true; for i:=1 to n do pricei:=mapi.p;初始時(shí)直接購(gòu)買,repeat ok:=true; for i:=1 to n do枚舉每一個(gè)與客戶h的等級(jí)差距在限制范圍內(nèi)的客戶 if cani then for j:=1 to mapi.x do begin枚舉物品i的每一個(gè)替代品，記下其編號(hào)和“優(yōu)惠價(jià)格” now:=mapi.listj,1; more:=mapi.listj,2; if （c

26、annow）and(pricenow+morepricei) 若第j個(gè)替代品可與客戶h交易且間接交易后花錢更少，則采取該交易方案 then begin ok:=false;pricei:=pricenow+more;end; end;for until ok; if price1min then min:=price1;若目前方案的花錢最少，則記下 end;for writeln(min);輸出最少需要的金幣數(shù) end;,DAM語(yǔ)言,有個(gè)機(jī)器執(zhí)行一種DASM語(yǔ)言。該機(jī)器有一個(gè)棧，初始時(shí)棧里只有一個(gè)元素x，隨著DAM語(yǔ)言程序的執(zhí)行，棧里的元素會(huì)發(fā)生變化。DAM語(yǔ)言有四種指令： D指令：把棧頂元素

27、復(fù)制一次加到棧頂 A指令：把棧頂元素取出，加到新的棧頂元素中。 M指令：把棧頂元素取出，乘到新的棧頂元素中。 如果執(zhí)行A或M指令的時(shí)候棧內(nèi)只有一個(gè)元素，則機(jī)器會(huì)發(fā)出錯(cuò)誤信息。如果程序無(wú)誤，那么執(zhí)行完畢以后，棧頂元素應(yīng)該是x的多項(xiàng)式，例如，程序DADDMA的執(zhí)行情況為（棧內(nèi)元素按照從底到頂?shù)捻樞驈淖笾劣遗帕校枚禾?hào)隔開）： x x， x 2x 2x， 2x 2x， 2x， 2x 2x， 4x2 4x2+2x 給出一段DAM程序，求出執(zhí)行完畢后棧頂元素。 輸入:輸入僅一行，包含一個(gè)不空的字符串s，長(zhǎng)度不超過(guò)12，代表一段DAM程序。輸入程序保證合法且不會(huì)導(dǎo)致錯(cuò)誤。 輸出:僅輸出一行，即棧頂多項(xiàng)式。

28、須按照習(xí)慣寫法降冪輸出，即：等于1的系數(shù)不要打印，系數(shù)為0的項(xiàng)不打印，第一項(xiàng)不打印正號(hào)。一次方不打印1。,模擬需要注意的問(wèn)題,用數(shù)組來(lái)表示多項(xiàng)式(由于指令不超過(guò)12條，而D指令和A，M指令總數(shù)應(yīng)該相等，因此最多有6條M指令(DMDMDMDMDMDM)，因此次數(shù)上限為26=64),避免鏈表。 系數(shù)采用extended類型(指令形式為DAMDMDMDMDM)系數(shù)最大可能為232),避免高精度。,$n+ var degree ： array1 . 20 of integer； 存儲(chǔ)系數(shù)個(gè)數(shù)的棧 co ： array1 . 20， 0 . 64 of extended；存儲(chǔ)多項(xiàng)式的棧 tmp ： ar

29、ray0 . 64 of extended；系數(shù)序列 I， j， d， a， b， top ： integer； 棧頂指針為top s ： string； Dam程序 first ： boolean； begin top 1； 棧頂指針初始化 fillchar(co， sizeof(co)， 0)； 存儲(chǔ)多項(xiàng)式的棧清零 degree1 1；初始時(shí)棧里只有一個(gè)元素x co1， 1 1； read(s)；輸入Dam程序 for I 1 to length(s) do依次執(zhí)行Dam程序中的每一條命令 case sI of D： begin 把棧頂元素復(fù)制一次加到棧頂 inc(top)；degreet

30、op degreetop 1； for j 0 to degreetop do cotop， j cotop 1， j； end； D ,A： begin 把棧頂元素取出，加到新的棧頂元素中 dec(top)； if degreetop 0 then begin if first then first false else write(+)； if abs(cotop， I 1.0) 1e-6 then write(cotop， I ： 0 ： 0)； write(x)； if I 1 then write(， I)； end；then writeln； end.main,跳遠(yuǎn),在水平面上整齊

31、的放著n個(gè)正三角形，相鄰兩個(gè)三角形的底邊之間無(wú)空隙， 如左圖所示。一個(gè)小孩子想站在某個(gè)三角形i的頂端，跳到三角形j的頂端上(ij)。他總是朝著斜向45度的方向起跳，且初始水平速度v不超過(guò)一個(gè)給定值v0。在跳躍過(guò)程中，由于受到重力作用（忽略空氣阻力），小孩子將沿著拋物線行進(jìn)，水平運(yùn)動(dòng)方程為x = x0 + vt，豎直運(yùn)動(dòng)方程為y = y0 + vt 0.5gt2，運(yùn)動(dòng)軌跡是一條上凸的拋物線。取g=10.0，(x0， y0)是起跳點(diǎn)坐標(biāo)。 請(qǐng)編程求出他從每個(gè)位置起跳能到達(dá)的最遠(yuǎn)三角形的編號(hào)。注意：跳躍過(guò)程中不許碰到非起點(diǎn)和終點(diǎn)的其他三角形。 輸入:第一行為兩個(gè)正整數(shù)n，v0(3n10， 1v010

32、0)，表示三角形的個(gè)數(shù)和最大水平初速度。第二行有n個(gè)正整數(shù)li(1li20)，表示從左到右各個(gè)三角形的邊長(zhǎng)。 輸出:輸出僅一行，包括n-1個(gè)數(shù)，表示從三角形1，2，3n-1的頂點(diǎn)出發(fā)能到達(dá)的最右的三角形編號(hào)。如果從某三角形出發(fā)無(wú)法達(dá)到任何三角形，相應(yīng)的數(shù)為0。,狀態(tài)：起跳點(diǎn)i和i點(diǎn)后的點(diǎn)j。每個(gè)狀態(tài)元素的取值范圍：1in-1，i+1jn 約束條件的分析：判斷小孩能否從i點(diǎn)跳到j(luò)點(diǎn)的方法如下： 設(shè)起點(diǎn)和終點(diǎn)間的水平距離為l、垂直距離為h。則由物理知識(shí)（已在題目中給出）有：t = l / v;h = vt 5t2 = l 5*(l/v)2 。 因此，v = sqrt(5*l*l/ (l-h)。當(dāng)然

33、，這個(gè)v不一定符合要求，它需要滿足兩個(gè)條件: 它不能大于極限速度v0，即必須有v v0 跳躍過(guò)程中不得碰到其他三角形。 如何判斷頂點(diǎn)k是否在拋物線下呢？我們可以算出到達(dá)時(shí)間t0 = dx / v（其中dx為起點(diǎn)到頂點(diǎn)k的水平坐標(biāo)增量），然后算出該時(shí)刻的豎直坐標(biāo)增量vt0 0.5t02。如果此增量大于起點(diǎn)到頂點(diǎn)k的豎直坐標(biāo)增量，則拋物線在上方。只有起點(diǎn)和終點(diǎn)之間任何一個(gè)三角形的頂點(diǎn)不在拋物線下方，則跳遠(yuǎn)不能完成。 我們?cè)诿杜e過(guò)程中不斷將小孩所能跳到的點(diǎn)j調(diào)整為best。 枚舉結(jié)束后，best即為試題要求的最遠(yuǎn)點(diǎn)。,var len ： array1 . 20 of longint； x， y ：

34、array1 . 20 of double；三角形頂端頂點(diǎn)的坐標(biāo)序列 l， h， t， v， v0 ： double； ok ： boolean；跳躍成功標(biāo)志 i， j， k， n， best ： integer； begin read(n， v0)；輸入三角形的個(gè)數(shù)和最大水平初速度 for i1 to n do read(leni)；入從左到右各個(gè)三角形的邊長(zhǎng) x1len1 / 2；計(jì)算每一個(gè)三角形頂端頂點(diǎn)的坐標(biāo) y1len1 * sqrt(3) / 2； for i2 to n do begin xixi - 1+leni - 1/2+leni/2； yileni*sqrt(3)/2； e

35、nd；for,for i 1 to n - 1 do依次計(jì)算每一個(gè)三角形所能到達(dá)的最遠(yuǎn)點(diǎn) begin best 0；從三角形i出發(fā)能到達(dá)的最右的三角形編號(hào)初始化 for j i + 1 to n do依次枚舉右方的每一個(gè)三角形 begin l xj - xi；計(jì)算三角形i與三角形j的兩個(gè)頂端頂點(diǎn)的水平距離和垂直距離 h yj - yi； if l v0 then break；若大于極限速度v0，則無(wú)法從三角形i起跳 oktrue； for ki+1 to j-1 do判斷跳躍過(guò)程中是否碰到其他三角形 begin t(xk - xi)/v；計(jì)算到達(dá)三角形k的時(shí)間,if (v * t - 5 *

36、t * t) - (yk - yi) 1e-6 then begin如果該時(shí)刻的豎直坐標(biāo)增量大于起點(diǎn)到頂點(diǎn)k的豎直坐標(biāo)增量，則拋物線在上方 ok false； break； end；then end；for if ok then best j 若跳遠(yuǎn)成功，則三角形j為目前三角形i所能到達(dá)的最遠(yuǎn)點(diǎn)，否則跳遠(yuǎn)不能完成 else break； end；for write(best， )；輸出從三角形i的頂點(diǎn)出發(fā)所能到達(dá)的最右的三角形編號(hào)） end；for writeln； end.main,作業(yè)調(diào)度方案,我們現(xiàn)在要利用m臺(tái)機(jī)器加工n個(gè)工件，每個(gè)工件都有m道工序，每道工序都在不同的指定的機(jī)器上完成。每

37、個(gè)工件的每道工序都有指定的加工時(shí)間。每個(gè)工件的每個(gè)工序稱為一個(gè)操作，我們用記號(hào)j-k表示一個(gè)操作，其中j為1到n中的某個(gè)數(shù)字，為工件號(hào)；k為1到m中的某個(gè)數(shù)字，為工序號(hào)，例如2-4表示第2個(gè)工件第4道工序的這個(gè)操作。在本題中，我們還給定對(duì)于各操作的一個(gè)安排順序。例如，當(dāng)n=3，m=2時(shí)，“1-1，1-2，2-1，3-1，3-2，2-2”就是一個(gè)給定的安排順序，即先安排第1個(gè)工件的第1個(gè)工序，再安排第1個(gè)工件的第2個(gè)工序，然后再安排第2個(gè)工件的第1個(gè)工序，等等。一方面，每個(gè)操作的安排都要滿足以下的兩個(gè)約束條件。 (1) 對(duì)同一個(gè)工件，每道工序必須在它前面的工序完成后才能開始； (2) 同一時(shí)刻每

38、一臺(tái)機(jī)器至多只能加工一個(gè)工件。,則對(duì)于安排順序“1 1 2 3 3 2”，下圖中的兩個(gè)實(shí)施方案都是正確的。但所需要的總時(shí)間分別是10與12。,另一方面，在安排后面的操作時(shí)，不能改動(dòng)前面已安排的操作的工作狀態(tài)。由于同一工件都是按工序的順序安排的，因此，只按原順序給出工件號(hào)，仍可得到同樣的安排順序，于是，在輸入數(shù)據(jù)中，我們將這個(gè)安排順序簡(jiǎn)寫為“1 1 2 3 3 2”。還要注意，“安排順序”只要求按照給定的順序安排每個(gè)操作。不一定是各機(jī)器上的實(shí)際操作順序。在具體實(shí)施時(shí)，有可能排在后面的某個(gè)操作比前面的某個(gè)操作先完成。例如，取n=3,m=2，已知數(shù)據(jù)如下：,當(dāng)一個(gè)操作插入到某臺(tái)機(jī)器的某個(gè)空檔時(shí)（機(jī)器

39、上最后的尚未安排操作的部分也可以看作一個(gè)空檔），可以靠前插入，也可以靠后或居中插入。為了使問(wèn)題簡(jiǎn)單一些，我們約定：在保證約束條件（1）（2）的條件下，盡量靠前插入。并且，我們還約定，如果有多個(gè)空檔可以插入，就在保證約束條件（1）（2）的條件下，插入到最前面的一個(gè)空檔。于是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。 顯然，在這些約定下，對(duì)于給定的安排順序，符合該安排順序的實(shí)施方案是唯一的，請(qǐng)你計(jì)算出該方案完成全部任務(wù)所需的總時(shí)間。 【輸入文件】輸入文件jsp.in 的第1行為兩個(gè)正整數(shù)，用一個(gè)空格隔開： m n（其中m（20）表示機(jī)器數(shù)，n（20）表示工件數(shù)） 第2行：個(gè)用空格

40、隔開的數(shù)，為給定的安排順序。 接下來(lái)的2n行，每行都是用空格隔開的m個(gè)正整數(shù)，每個(gè)數(shù)不超過(guò)20。其中前n行依次表示每個(gè)工件的每個(gè)工序所使用的機(jī)器號(hào)，第1個(gè)數(shù)為第1個(gè)工序的機(jī)器號(hào)，第2個(gè)數(shù)為第2個(gè)工序機(jī)器號(hào)，等等。后n行依次表示每個(gè)工件的每個(gè)工序的加工時(shí)間。可以保證，以上各數(shù)據(jù)都是正確的，不必檢驗(yàn)。 【輸出文件】輸出文件jsp.out只有一個(gè)正整數(shù)，為最少的加工時(shí)間。,題目大意,有N個(gè)工件和M臺(tái)機(jī)器，每個(gè)工件都必須要經(jīng)過(guò)這M道工序。每個(gè)工件對(duì)不同機(jī)器需要不同時(shí)間處理。每個(gè)工件有一個(gè)工序的操作先后順序，下一個(gè)工序必須再前面的工序都完成后才能開始。每臺(tái)機(jī)器同一時(shí)間只能對(duì)一個(gè)工件進(jìn)行一道工序。給出一個(gè)

41、安排順序，對(duì)于當(dāng)前給出的工件，將它插入到工作方案中適合的位置（需要滿足該工件對(duì)工序的操作順序，以及機(jī)器的使用規(guī)定）。求出將所有工件加工完所需要的最短時(shí)間。,直譯模擬,由于每個(gè)工件的每個(gè)工序使用的機(jī)器號(hào)和加工時(shí)間給定，因此安排順序給出后，所用時(shí)間也就唯一確定，所以直接模擬即可得到答案。 難點(diǎn)：找出當(dāng)前機(jī)器i開始加工的時(shí)間 方法：用所有時(shí)間的部分和進(jìn)行優(yōu)化。,計(jì)算每臺(tái)機(jī)器加工時(shí)間的情況,設(shè)tti,j=1，表明機(jī)器i在時(shí)刻j被使用;tti,j=0，表明機(jī)器i在時(shí)刻j未使用; sumi,j機(jī)器i在j時(shí)間前使用的時(shí)間和，即sumi,j= ； 顯然，機(jī)器i開始加工的時(shí)間j為加工前后使用的時(shí)間和為0的位置，

42、即當(dāng) sumi,j+加工當(dāng)前工件工序的時(shí)間=sumi,j 時(shí)，表明機(jī)器i可以從j時(shí)刻開始加工當(dāng)前工件，因?yàn)樵撈陂g沒(méi)有其它工件使用該機(jī)器。這樣順序查找一遍所有時(shí)間點(diǎn)，即可找出機(jī)器i開始加工的時(shí)間。,遞推安排順序i,1、第i個(gè)順序加工的工件pp已知；如果能夠知道工件pp的工序，則使用的機(jī)器號(hào)已知。因此需要計(jì)算每個(gè)工件的當(dāng)前工序 2、從工件pp的上一個(gè)工序的結(jié)束時(shí)間開始，計(jì)算加工pp工件當(dāng)前工序的開始時(shí)間，因此需要計(jì)算每個(gè)工件當(dāng)前工序的結(jié)束時(shí)間； 3、加工期間，該機(jī)器標(biāo)志被使用，因此需要計(jì)算tt； 4、從加工開始至末尾時(shí)間，調(diào)整使用的時(shí)間和，因此需要計(jì)算sum； 5、最少加工時(shí)間是所有安排順序的結(jié)束

43、時(shí)間的最大值。,按照安排順序遞推完成所有工件加工的最短時(shí)間,1、初始時(shí)，假設(shè)每一個(gè)工件從工序1開始加工； for i:=1 to m*n do遞推安排順序 begin 2、取出第i個(gè)順序加工的工件pp、pp工件當(dāng)前工序ss、使用的機(jī)器號(hào)aa、上一個(gè)工序的結(jié)束時(shí)間edpp； 3、從edpp時(shí)刻開始，計(jì)算機(jī)器aa開始進(jìn)工pp工件當(dāng)前工序的時(shí) 間j； 4、設(shè)置加工期間機(jī)器aa被使用，累計(jì)機(jī)器aa使用的時(shí)間和； 5、設(shè)置工件pp完成本工序的結(jié)束時(shí)間edpp，調(diào)整最少加工時(shí)間； 6、枚舉機(jī)器aa完成工件pp的當(dāng)前工序后的每一個(gè)可能時(shí)間jj，計(jì)算使用的時(shí)間和； 7、pp工件進(jìn)入下一個(gè)工序； end; in

44、c(ans),數(shù)據(jù)結(jié)構(gòu),const maxt=8000;時(shí)間數(shù)的上限 maxn=20;工件和工序數(shù)的上限 inf=jsp.in;outf=jsp.out; var a,t:array1.maxn,1.maxnof longint; 工件i的j工序所使用的機(jī)器號(hào)為ai,j，加工時(shí)間為ti,j p:array1.maxn*maxnof longint;在安排順序i中加工的工件號(hào)為pi st,ed:array1.maxnof longint; 工件i的當(dāng)前工序?yàn)閟ti；上一個(gè)工序的結(jié)束時(shí)間為edi sum,tt:array1.maxn,-1.maxtof longint; sumI,j機(jī)器i在j時(shí)間

45、前使用的時(shí)間和；tti,j=1，表明機(jī)器i在時(shí)刻j被使用， tti,j=0，表明機(jī)器i在時(shí)刻j未使用 n,m,ans:longint; 工件數(shù)為n，機(jī)器數(shù)為m，最少加工時(shí)間為ans,輸入信息,procedure init; var i,j:longint; begin assign(input,inf);reset(input);文件讀準(zhǔn)備 readln(m,n);輸入機(jī)器數(shù)和工件數(shù) for i:=1 to m*n do read(pi);輸入每個(gè)安排順序中被加工的工件號(hào) for i:=1 to n do輸入每個(gè)工件的每個(gè)工序所使用的機(jī)器號(hào) for j:=1 to m do read(ai,j

46、); for i:=1 to n do輸入每個(gè)工件的每個(gè)工序的加工時(shí)間 for j:=1 to m do read(ti,j); close(input) end;,計(jì)算最少加工時(shí)間ans,procedure main; var i,pp,aa,ss,j,jj:longint; Begin 1、初始時(shí)假設(shè)每一個(gè)工件從工序1開始加工 for i:=1 to n do sti:=1； for i:=1 to m*n do遞推安排順序 begin 2、取出第i個(gè)順序加工的工件pp、pp工件當(dāng)前工序所使用的機(jī)器號(hào)aa、pp工件的當(dāng)前工序ss和上一個(gè)工序的結(jié)束時(shí)間 pp:=pi;aa:=app,stpp

47、;ss:=stpp;j:=edpp； 3、計(jì)算機(jī)器aa開始進(jìn)行工件pp當(dāng)前工序的時(shí)間j while(sumaaj+tpp,ss-1-sumaaj-10)do inc(j);,4、設(shè)置加工期間機(jī)器aa被使用，累計(jì)機(jī)器aa使用的時(shí)間和 for jj:=j to j+tpp,ss-1 do begin ttaajj:=1;sumaajj:=sumaajj-1+1；end； 5、計(jì)算工件pp完成本工序的結(jié)束時(shí)間，調(diào)整最少加工時(shí)間 edpp:=j+tpp,ss;ans:=max(ans,j+tpp,ss-1); 6、枚舉機(jī)器aa完成工件pp的ss工序后的每一個(gè)可能時(shí)間jj，計(jì)算使用的時(shí)間和 for jj

48、:=j+tpp,ss to maxt do sumaajj:=sumaajj-1+ttaajj； inc(stpp);7、計(jì)算pp工件的下一個(gè)工序 end; inc(ans) end;,篩選法模擬,模擬過(guò)程中可能產(chǎn)生的所有解組成一個(gè)篩。篩選法模擬即先從題意中找出約束條件，然后將篩中的每一個(gè)可能解放到約束條件的過(guò)濾器上，一次一次地將不符合條件的解過(guò)濾掉，最后沉淀在篩中的即為問(wèn)題的解?！昂Y選法模擬”的結(jié)構(gòu)和思路簡(jiǎn)明、清晰，但帶有盲目性，因此時(shí)間效率并不一定令人滿意?！昂Y選法模擬”的關(guān)鍵是找準(zhǔn)約束條件，任何錯(cuò)誤和疏漏都會(huì)導(dǎo)致模擬失敗。,蒙特卡洛法,計(jì)算定積分 其中ab，0f(x)d， 輸入： a b

49、 d a0a1ak(表示f(x)=ak*xk+a1*x+a0),產(chǎn)生n(足夠大)個(gè)均勻分布在長(zhǎng)方形a b c d上的隨機(jī)數(shù)點(diǎn)(xi，yi)。其中 xi均勻分布在區(qū)間a，b上的隨機(jī)數(shù)，即xi=a+(b-a)*random(1)； yi均勻分布在區(qū)間0，d上的隨機(jī)數(shù)，即yi=d*random(1)； n個(gè)隨機(jī)數(shù)點(diǎn)組成一個(gè)篩。約束條件的過(guò)濾器是某點(diǎn)(xi，yi)是否落在曲邊梯形a e f b外。如果是（yif(xi)），則該點(diǎn)從篩中過(guò)濾掉。 最后有m個(gè)隨機(jī)數(shù)點(diǎn)留在篩中（這些隨機(jī)數(shù)點(diǎn)落在曲邊梯形a e f b內(nèi)）。曲邊梯形a e f b的面積應(yīng)該為m和n的比值乘以長(zhǎng)方形a b c d的面積,funct

50、ion f(x)：real；計(jì)算f(x) begin f(x)akxk+ak-1kk-1+a1x+a0； end；f function amoncar (a， b， d， n)：real；計(jì)算 begin randomize； m0； for i1 to n do begin xa+(b-a)*random(1)；產(chǎn)生ki yd*random(1)；產(chǎn)生yi if yf(x) then mm+1；若(xi，yI)落入曲邊梯形內(nèi)，則累計(jì)其點(diǎn)數(shù) end；for amoncarm/n*(b-a)*d；返回曲邊梯形面積 end；amoncar 在主程序中，輸入隨機(jī)點(diǎn)的個(gè)數(shù)n和a，b，d，然后通過(guò)調(diào)用函

51、數(shù)amoncar (a，b，d，n)計(jì)算和輸出定積分的值。注意，n愈大，定積分的值愈精確，但速度愈慢。,self-number,對(duì)任意一個(gè)正整數(shù)n，定義d(n)為n加上其每一位上的數(shù)字，比如d(75) = 75 + 7 + 5 = 87。并且稱n是d(n)的一個(gè)generator。一個(gè)正整數(shù)，如果沒(méi)有任何generator，就說(shuō)這個(gè)數(shù)是一個(gè)self-number。給出一列數(shù)s1，s2，sK，問(wèn)范圍1, N內(nèi)第s1，s2，sK大的self-number分別是什么。 輸入： n k(1 N 107,1 K 5000) s1，s2，sK 輸出：范圍1, N內(nèi)第s1，s2，sK大的self-numbe

52、r,如果一個(gè)數(shù)x不能通過(guò)d(n)方式算得出，那么稱之為Self-number。如1、3、5、7、9都是Self-number。,用篩數(shù)方法產(chǎn)生1, N中的所有self-number,在一張一維的布爾表中，從小到大將每個(gè)數(shù)n的d(n)都標(biāo)記為不可能是self-number，那么未被標(biāo)記的一定就是self-number了。 布爾表的容量：因?yàn)閐(n) n（各位數(shù)的和）并不會(huì)很大：最大也不過(guò)9*lgn=81。,計(jì)算d(n)的時(shí)間復(fù)雜度,原時(shí)間復(fù)雜度為O(NlgN)：因?yàn)槊看斡?jì)算d(n)時(shí)侯分離其每一位的時(shí)間復(fù)雜度是O(lgN)。本題中N高達(dá)107，因此這個(gè)O(lgN)的因子不可以忽略。 優(yōu)化 首先預(yù)

53、處理，開一個(gè)subi數(shù)組，記錄i的每一位之和，但是這里i的范圍不用太大，只要在O(sqrt(n)=104就可以了。這樣計(jì)算d(n)的時(shí)侯，就可以將n的各位和分成低4位和高3位來(lái)計(jì)算，而每次計(jì)算不過(guò)是調(diào)用subi，這樣計(jì)算d(n)的時(shí)間復(fù)雜度就降到了O(1)。 綜上，本題的時(shí)間復(fù)雜度就是O(sqrt(n)lgN + N + Mlog2M)，其中Mlog2M是在輸出的時(shí)侯需要對(duì)si進(jìn)行排序。,設(shè)篩data，其中datai 將數(shù)i的d(i)標(biāo)記為不可能是self-number。篩長(zhǎng)為1000。 data篩的指針為now ； self-number序列為request，其中request i. req

54、uest 為si，request i. number為si的輸入順序，request i. answer為順序?yàn)閟i的self-number數(shù)。self-number序列的指針為p； self-number的個(gè)數(shù)為total。,初始化,read(N , K); for i := 1 to K do輸入s1，s2，sK ，記下輸入順序 begin read(requesti.request);讀si requesti.number := i;記下si的輸入順序 end; qk_sort(1 , K)；按照s1，s2，sK 遞增順序排列request 計(jì)算sub0sub10000，其中subi為整

55、數(shù)i的各位數(shù)的和；,fillchar(data , sizeof(data) , 0);初始時(shí)篩滿，即所有數(shù)可能是self-number數(shù) now := 1; total := 0; p := 1; data篩的指針、 self-number的個(gè)數(shù)、 self-number序列的指針初始化 for i := 1 to N do順序搜索1, N內(nèi)第s1，s2，sK大的self-number begin if not datanow then若now在篩中 begin inc(total);累計(jì)self-number的個(gè)數(shù) while (p Limit do dec(tmp , Limit);將d

56、i限制在1000范圍內(nèi) datatmp := true; datanow := false; 在data篩中保留第now個(gè)元素，去掉第di個(gè)元素 if now = Limit循環(huán)右移data篩的指針now then now := 1 else inc(now); end;,輸出self-number,for i := 1 to K do按照輸入要求記下各個(gè)self-number數(shù) outarrrequesti.number := requesti.answer; 輸出1.n中self-number的個(gè)數(shù) total; 輸出outarr1 outarrk；,構(gòu)造法模擬,構(gòu)造法模擬需要完整精確地構(gòu)

57、造出反映問(wèn)題本質(zhì)的數(shù)學(xué)模型，根據(jù)該模型設(shè)計(jì)狀態(tài)變化的參數(shù)，計(jì)算模擬結(jié)果。由于數(shù)學(xué)模型建立了客觀事物間準(zhǔn)確的運(yùn)算關(guān)系，因此其效率一般比較高?！皹?gòu)造法模擬”的關(guān)鍵是找到數(shù)學(xué)模型。問(wèn)題是，能產(chǎn)生正確結(jié)果的數(shù)學(xué)模型并不是唯一的，從不同的思維角度看問(wèn)題，可以得出不同的數(shù)學(xué)模型，而模擬效率和編程復(fù)雜度往往因數(shù)學(xué)模型而異。即便有數(shù)學(xué)模型，但解該模型的準(zhǔn)確方法是否有現(xiàn)成算法、編程復(fù)雜度如何，這些都是我們要考慮的問(wèn)題。,守望者的逃離,【問(wèn)題描述】惡魔獵手尤迫安野心勃勃.他背叛了暗夜精靈，率深藏在海底的那加企圖叛變：守望者在與尤迪安的交鋒中遭遇了圍殺.被困在一個(gè)荒蕪的大島上。為了殺死守望者，尤迪安開始對(duì)這個(gè)荒島施

58、咒，這座島很快就會(huì)沉下去，到那時(shí)，刀上的所有人都會(huì)遇難：守望者的跑步速度，為17m/s， 以這樣的速度是無(wú)法逃離荒島的。慶幸的是守望者擁有閃爍法術(shù)，可在1s內(nèi)移動(dòng)60m，不過(guò)每次使用閃爍法術(shù)都會(huì)消耗魔法值10點(diǎn)。守望者的魔法值恢復(fù)的速度為4點(diǎn)/s，只有處在原地休息狀態(tài)時(shí)才能恢復(fù)。 現(xiàn)在已知守望者的魔法初值M，他所在的初始位置與島的出口之間的距離S，島沉沒(méi)的時(shí)間T。你的任務(wù)是寫一個(gè)程序幫助守望者計(jì)算如何在最短的時(shí)間內(nèi)逃離荒島，若不能逃出，則輸出守望者在剩下的時(shí)間內(nèi)能走的最遠(yuǎn)距離。注意:守望者跑步、閃爍或休息活動(dòng)均以秒(s)為單位。且每次活動(dòng)的持續(xù)時(shí)間為整數(shù)秒。距離的單位為米(m)。 【輸入】輸入文件escape.in僅一行，包括空格隔開的三個(gè)非負(fù)整數(shù)M，S，T。 【輸出】 輸出文件escape.out包含兩行: 第1行為字符串Yes或No (區(qū)分大小寫)，即守望者是否能逃離荒島。 第2行包含一個(gè)整數(shù)，第一行為Yes (區(qū)分大小寫）時(shí)表示守望著逃離荒島的最短時(shí)間 第一行為No (區(qū)分大小寫) 時(shí)表示守望者能走的最遠(yuǎn)距離。,如果守望者尚未逃出荒島且荒島未沉沒(méi)（(nows)and(tT）)，則應(yīng)采用盡可能使用魔法的貪心策略,守望者的魔法值足以施展閃爍法術(shù)（p10），則使用1秒閃爍法術(shù)：p=p-10;now=now+60;t=t