試題一：殺螞蟻

程序名： antbuster.pas/c/cpp

可執(zhí)行文件名： antbuster.exe

輸入文件名： antbuster.in

輸出文件名： antbuster.out

時(shí)間限制： 3s

最近，佳佳迷上了一款好玩的小游戲： antbuster 。

游戲規(guī)則非常簡(jiǎn)單：在一張地圖上，左上角是螞蟻窩，右下角是蛋糕，螞蟻會(huì)源源不斷地從窩里爬出來(lái)，試圖把蛋糕搬回螞蟻窩。而你的任務(wù)，就是用原始資金以及殺螞蟻獲得的獎(jiǎng)金造防御塔，殺掉這些試圖跟你搶蛋糕的螞蟻 ~

下附一張游戲截圖：

為了拿到盡可能高的分?jǐn)?shù)，佳佳設(shè)計(jì)了很多種造塔的方案，但在嘗試了其中的一小部分后，佳佳發(fā)現(xiàn)，這個(gè)游戲?qū)嵲谑翘M(fèi)時(shí)間了。為了節(jié)省時(shí)間，佳佳決定寫(xiě)個(gè)程序，對(duì)于每一種方案，模擬游戲進(jìn)程，根據(jù)效果來(lái)判斷方案的優(yōu)劣。

根據(jù)自己在游戲中積累的一些經(jīng)驗(yàn)，以及上網(wǎng)搜到的一些參數(shù)，佳佳猜了螞蟻爬行的算法，并且假設(shè)游戲中的螞蟻也是按這個(gè)規(guī)則選擇路線(xiàn)：

1 、每一秒鐘開(kāi)始的時(shí)候，螞蟻都在平面中的某個(gè)整點(diǎn)上。如果螞蟻沒(méi)有扛著蛋糕，它會(huì)在該點(diǎn)留下 2 單位的信息素，否則它會(huì)留下 5 單位的信息素。然后螞蟻會(huì)在正北、正南、正東、正西四個(gè)方向中選擇一個(gè)爬過(guò)去。

2 、選擇方向的規(guī)則是：首先，爬完一個(gè)單位長(zhǎng)度后到達(dá)的那個(gè)點(diǎn)上，不能有其他螞蟻或是防御塔，并且那個(gè)點(diǎn)不能是螞蟻上一秒所在的點(diǎn)（除非上一個(gè)時(shí)刻螞蟻就被卡住，且這個(gè)時(shí)刻它仍無(wú)法動(dòng)），當(dāng)然，螞蟻也不會(huì)爬出地圖的邊界（我們定義這些點(diǎn)為不可達(dá)點(diǎn)）。如果此時(shí)有多個(gè)選擇，螞蟻會(huì)選擇信息素最多的那個(gè)點(diǎn)爬過(guò)去。

3 、如果此時(shí)仍有多種選擇，螞蟻先面向正東，如果正東不是可選擇的某個(gè)方向，它會(huì)順時(shí)針轉(zhuǎn) 90 °，再次判斷，如果還不是，再轉(zhuǎn) 90 ° ... 直到找到可以去的方向。

4 、如果將每只螞蟻在洞口出現(xiàn)的時(shí)間作為它的活動(dòng)時(shí)間的第 1 秒，那么每當(dāng)這只螞蟻的活動(dòng)時(shí)間秒數(shù)為 5 的倍數(shù)的時(shí)候，它先按規(guī)則 1~3 確定一個(gè)方向，面對(duì)該方向后逆時(shí)針轉(zhuǎn) 90 °，若它沿當(dāng)前方向會(huì)走到一個(gè)不可達(dá)點(diǎn)，它會(huì)不停地每次逆時(shí)針轉(zhuǎn) 90 °，直到它面對(duì)著一個(gè)可達(dá)的點(diǎn)，這樣定下的方向才是螞蟻?zhàn)罱K要爬去的方向。

5 、如果螞蟻的四周都是不可達(dá)點(diǎn)，那么螞蟻在這一秒內(nèi)會(huì)選擇停留在當(dāng)前點(diǎn)。下一秒判斷移動(dòng)方向時(shí)，它上一秒所在點(diǎn)為其當(dāng)前停留的點(diǎn)。

6 、你可以認(rèn)為螞蟻在選定方向后，瞬間移動(dòng)到它的目標(biāo)點(diǎn)，這一秒鐘剩下的時(shí)間里，它就停留在目標(biāo)點(diǎn)。

7 、螞蟻按出生的順序移動(dòng)，出生得比較早的螞蟻先移動(dòng)。

?

然后，是一些有關(guān)地圖的信息：

1、? 每一秒，地圖所有點(diǎn)上的信息素會(huì)損失 1 單位，如果那個(gè)點(diǎn)上有信息素的話(huà)。

2、? 地圖上某些地方是炮臺(tái)。炮臺(tái)的坐標(biāo)在輸入中給出。

3、? 地圖的長(zhǎng)、寬在輸入中給出，對(duì)于 n * m 的地圖，它的左上角坐標(biāo)為（ 0 ， 0 ），右下角坐標(biāo)為（ n ， m ）。螞蟻洞的位置為（ 0 ， 0 ），蛋糕的位置為（ n ， m ）。

4、? 你可以把螞蟻看做一個(gè)直徑為 1 單位的圓，圓心位于螞蟻所在的整點(diǎn)。

5、? 游戲開(kāi)始時(shí)，地圖上沒(méi)有螞蟻，每個(gè)點(diǎn)上的信息素含量均為 0 。

?

一些有關(guān)炮塔的信息：

1、? 炮塔被放置在地圖上的整點(diǎn)處。

2、? 為了簡(jiǎn)單一些，我們認(rèn)為這些炮塔都是激光塔。激光塔的射速是 1 秒 / 次，它的攻擊傷害為 d/ 次，攻擊范圍為 r 。你可以認(rèn)為每秒螞蟻移動(dòng)完畢后，塔才開(kāi)始攻擊。并且，只有當(dāng)代表螞蟻的圓的圓心與塔的直線(xiàn)距離不超過(guò) r 時(shí)，塔才算打得到那只螞蟻。

3、? 如果一只螞蟻扛著蛋糕，那么它會(huì)成為 target ，也就是說(shuō)，任何打得到它的塔的炮口都會(huì)對(duì)準(zhǔn)它。如果蛋糕好好地呆在原位，那么每個(gè)塔都會(huì)挑離它最近的螞蟻進(jìn)行攻擊，如果有多只螞蟻，它會(huì)選出生較早的一只。

4、? 激光塔有個(gè)比較奇怪的特性：它在選定了打擊目標(biāo)后，只要目標(biāo)在其射程內(nèi)，塔到目標(biāo)螞蟻圓心的連線(xiàn)上的所有螞蟻（這里“被打到”的判定變成了表示激光的線(xiàn)段與表示螞蟻的圓有公共點(diǎn)）都會(huì)被打到并損 d 格血，但激光不會(huì)穿透它的打擊目標(biāo)打到后面的螞蟻。

5、? 盡管在真實(shí)游戲中，塔是可以升級(jí)的，但在這里我們認(rèn)為塔的布局和等級(jí)就此定了下來(lái)，不再變動(dòng) ?

再介紹一下螞蟻窩：

1、? 如果地圖上的螞蟻不足 6 只，并且洞口沒(méi)有螞蟻，那么窩中每秒會(huì)爬出一只螞蟻，直到地圖上的螞蟻數(shù)為 6 只。

2、? 剛出生的螞蟻站在洞口。

3、? 每只螞蟻有一個(gè)級(jí)別，級(jí)別決定了螞蟻的血量，級(jí)別為 k 的螞蟻的血量為 int(4*1.1^k) （ int(x) 表示對(duì) x 取下整）。每被塔打一次，螞蟻的血減少 d 。注意，血量為 0 的螞蟻仍能精力充沛地四處亂爬，只有一只螞蟻的血被打成負(fù)數(shù)時(shí)，它才算掛了。

4、? 螞蟻的級(jí)別是這樣算的：前 6 只出生的螞蟻是 1 級(jí)，第 7~12 只是 2 級(jí)，依此類(lèi)推。

?

最后給出關(guān)于蛋糕的介紹：

1、? 簡(jiǎn)單起見(jiàn)，你可以認(rèn)為此時(shí)只剩最后一塊蛋糕了。如果有螞蟻?zhàn)叩降案獾奈恢茫⑶掖藭r(shí)蛋糕沒(méi)有被扛走，那么這只螞蟻就扛上了蛋糕。螞蟻被打死后蛋糕歸位。

2、? 如果一只扛著蛋糕的螞蟻?zhàn)叩轿浵伕C的位置，我們就認(rèn)為螞蟻成功搶到了蛋糕，游戲結(jié)束。

3、? 螞蟻扛上蛋糕時(shí)，血量會(huì)增加 int （該螞蟻出生時(shí)血量 / 2 ），但不會(huì)超過(guò)上限。

?

整理一下 1 秒鐘內(nèi)發(fā)生的事件：

1 秒的最初，如果地圖上螞蟻數(shù)不足 6 ，一只螞蟻就會(huì)在洞口出生。

接著，螞蟻們?cè)谧约核邳c(diǎn)留下一些信息素后，考慮移動(dòng)。先出生的螞蟻先移動(dòng)。

移動(dòng)完畢后，如果有螞蟻在蛋糕的位置上并且蛋糕沒(méi)被拿走，它把蛋糕扛上，血量增加，并在這時(shí)被所有塔設(shè)成 target 。

然后所有塔同時(shí)開(kāi)始攻擊。如果攻擊結(jié)束后那只扛著蛋糕的螞蟻掛了，蛋糕瞬間歸位。

攻擊結(jié)束后，如果發(fā)現(xiàn)扛蛋糕的螞蟻沒(méi)死并在窩的位置，就認(rèn)為螞蟻搶到了蛋糕。游戲也在此時(shí)結(jié)束。

最后，地圖上所有點(diǎn)的信息素?fù)p失 1 單位。所有螞蟻的年齡加 1 。

漫長(zhǎng)的 1 秒到此結(jié)束。

?

輸入：

輸入的第一行是 2 個(gè)用空格隔開(kāi)的整數(shù)， n 、 m ，分別表示了地圖的長(zhǎng)和寬。

第二行是 3 個(gè)用空格隔開(kāi)的整數(shù)， s 、 d 、 r ，依次表示炮塔的個(gè)數(shù)、單次攻擊傷害以及攻擊范圍。

接下來(lái) s 行，每行是 2 個(gè)用空格隔開(kāi)的整數(shù) x 、 y ，描述了一個(gè)炮塔的位置。當(dāng)然，螞蟻窩的洞口以及蛋糕所在的位置上一定沒(méi)有炮塔。

最后一行是一個(gè)正整數(shù) t ，表示我們模擬游戲的前 t 秒鐘。

?

輸出：

如果在第 t 秒或之前螞蟻搶到了蛋糕，輸出一行“ Game over after x seconds ”，其中 x 為游戲結(jié)束的時(shí)間，否則輸出“ The game is going on ”。

如果游戲在 t 秒或之前結(jié)束，輸出游戲結(jié)束時(shí)所有螞蟻的信息，否則輸出 t 秒后所有螞蟻的信息。格式如下：

第一行是 1 個(gè)整數(shù) s ，表示此時(shí)活著的螞蟻的總數(shù)。

接下來(lái) s 行，每行 5 個(gè)整數(shù)，依次表示一只螞蟻的年齡（單位為秒）、等級(jí)、當(dāng)前血量，以及在地圖上的位置（ a ， b ）。輸出按螞蟻的年齡遞減排序。

?
?

輸入樣例：

3 5

1 1 2

2 2

5

?

輸出樣例：

The game is going on

5

5 1 3 1 4

4 1 3 0 4

3 1 3 0 3

2 1 3 0 2

1 1 4 0 1

?

樣例說(shuō)明：

??? 3*5 的地圖，有 1 個(gè)單次傷害為 1 、攻擊范圍為 2 的激光炮塔，它的位置為（ 2 ， 2 ），模擬游戲的前 5 秒。 5 秒內(nèi)有 5 只螞蟻出生，都是向東爬行，其中第 1~4 只在路過(guò)（ 0 ， 2 ）點(diǎn)時(shí)被激光塔傷了 1 格血。在第 5 秒的時(shí)候，最早出生的螞蟻按移動(dòng)規(guī)則 1~3 本來(lái)該向東移動(dòng)，但由于規(guī)則 4 的作用，它在發(fā)現(xiàn)向北和向西移動(dòng)都會(huì)到達(dá)不可達(dá)點(diǎn)后，最終選擇了向南移動(dòng)。

?

數(shù)據(jù)說(shuō)明：

100% 的數(shù)據(jù)滿(mǎn)足 1 ≤ n,m ≤ 8 ， s ≤ 20 ， t ≤ 200,000

?

?

試題二：泡泡堂

?

源程序名： bnb. pas/c/cpp

可執(zhí)行文件名： bnb.exe

輸入文件名： bnb.in

輸出文件名： bnb.out

時(shí)限： 1s

?

第 XXXX 屆 NOI 期間，為了加強(qiáng)各省選手之間的交流，組委會(huì)決定組織一場(chǎng)省際電子競(jìng)技大賽，每一個(gè)省的代表隊(duì)由 n 名選手組成，比賽的項(xiàng)目是老少咸宜的網(wǎng)絡(luò)游戲泡泡堂。每一場(chǎng)比賽前，對(duì)陣雙方的教練向組委會(huì)提交一份參賽選手的名單，決定了選手上場(chǎng)的順序，一經(jīng)確定，不得修改。比賽中，雙方的一號(hào)選手，二號(hào)選手……， n 號(hào)選手捉對(duì)廝殺，共進(jìn)行 n 場(chǎng)比賽。每勝一場(chǎng)比賽得 2 分，平一場(chǎng)得 1 分，輸一場(chǎng)不得分。最終將雙方的單場(chǎng)得分相加得出總分，總分高的隊(duì)伍晉級(jí) ( 總分相同抽簽決定 ) 。

作為浙江隊(duì)的領(lǐng)隊(duì)，你已經(jīng)在事先將各省所有選手的泡泡堂水平了解的一清二楚，并將其用一個(gè)實(shí)力值來(lái)衡量。為簡(jiǎn)化問(wèn)題，我們假定選手在游戲中完全不受任何外界因素干擾，即實(shí)力強(qiáng)的選手一定可以戰(zhàn)勝實(shí)力弱的選手，而兩個(gè)實(shí)力相同的選手一定會(huì)戰(zhàn)平。由于完全不知道對(duì)手會(huì)使用何種策略來(lái)確定出場(chǎng)順序，所以所有的隊(duì)伍都采取了這樣一種策略，就是完全隨機(jī)決定出場(chǎng)順序。

當(dāng)然你不想這樣不明不白的進(jìn)行比賽。你想事先了解一下在最好與最壞的情況下，浙江隊(duì)最終分別能得到多少分。

?

輸入：

?????? 輸入文件的第一行為一個(gè)整數(shù) n ，表示每支代表隊(duì)的人數(shù)。

?????? 接下來(lái) n 行，每行一個(gè)整數(shù)，描述了 n 位浙江隊(duì)的選手的實(shí)力值。

?????? 接下來(lái) n 行，每行一個(gè)整數(shù)，描述了你的對(duì)手的 n 位選手的實(shí)力值。

?????? 20 ％的數(shù)據(jù)中， 1<=n<=10 ；

40 ％的數(shù)據(jù)中， 1<=n<=100 ；

60 ％的數(shù)據(jù)中， 1<=n<=1000 ；

100 ％的數(shù)據(jù)中， 1<=n<=100000 ，且所有選手的實(shí)力值在 0 到 10000000 之間。

?

輸出：

				
						樣例1
				
		

輸入文件中包括兩個(gè)用空格隔開(kāi)的整數(shù)，分別表示浙江隊(duì)在最好與最壞的情況下分別能得多少分。不要在行末輸出多余的空白字符。

bnb.in

2

1

3

2

4

bnb.out

2 0

樣例說(shuō)明

我們分別稱(chēng) 4 位選手為 A,B,C,D 。則可能出現(xiàn)以下 4 種對(duì)戰(zhàn)方式，最好情況下可得 2 分，最壞情況下得 0 分。

?

樣例 2

bnb.in

6

10000000

10000000

10000000

10000000

10000000

10000000

0

0

0

0

0

0

bnb.out

12 12

樣例說(shuō)明

對(duì)手都是認(rèn)真學(xué)習(xí)的好孩子，不會(huì)打游戲。無(wú)論如何排列出場(chǎng)順序都無(wú)法改變被蹂躪的結(jié)果。浙江隊(duì)總能取得全勝的結(jié)果。

?

?

?

?

?

試題三 ： Risk

源程序名 :risk. pas/c/cpp

可執(zhí)行文件名 :risk.exe

輸入文件名 :risk.in

輸出文件名 :risk.out

時(shí)限 :1s

?

???? 經(jīng)過(guò)連續(xù)若干年的推廣， Risk 這個(gè)游戲已經(jīng)風(fēng)靡全國(guó)，成為大眾喜聞樂(lè)見(jiàn)的重要娛樂(lè)方式。 Risk 這個(gè)游戲可以理解為一種簡(jiǎn)易的策略游戲，游戲者的目的是占領(lǐng)所有的土地。由于游戲規(guī)則的規(guī)定，只要兩個(gè)國(guó)家相鄰，就認(rèn)為兩個(gè)國(guó)家有交戰(zhàn)的可能性。我們現(xiàn)在希望知道在當(dāng)前的局面下，哪些國(guó)家之間有交戰(zhàn)的可能性。注意，我們認(rèn)為只有當(dāng)兩個(gè)國(guó)家的國(guó)界線(xiàn)有公共邊的時(shí)候才認(rèn)為相鄰，若兩個(gè)國(guó)家的領(lǐng)土只有公共點(diǎn)，則認(rèn)為兩個(gè)國(guó)家不相鄰。

?????? 每一個(gè)國(guó)家的邊界由一系列線(xiàn)段組成，保證這個(gè)邊界是一個(gè)簡(jiǎn)單多邊形，即嚴(yán)格不自交。為了定位每個(gè)國(guó)家的位置，我們還給出每個(gè)國(guó)家最龐大的一支軍隊(duì)的位置，保證這個(gè)位置一定出現(xiàn)在某一個(gè)形內(nèi)，而不是出現(xiàn)在某條邊界上。

?

輸入：

輸入文件的第一行中包括兩個(gè)整數(shù) n,m 。分別表示地圖上的國(guó)家數(shù)和描述國(guó)家的邊界的線(xiàn)段的數(shù)量。 1<=n<=600 ， 1<=m<=4000 。接下來(lái) n 行，每行用一對(duì)數(shù)描述了某個(gè)國(guó)家的主力軍隊(duì)的坐標(biāo)。接下來(lái) m 行，每行有 4 個(gè)數(shù) x1,y1,x2,y2 ，（ x1,y1 ） -(x2,y2) 描述了一條國(guó)界線(xiàn)。所有點(diǎn)的坐標(biāo)都是 0-10000 之間的整數(shù)。

保證輸入的所有線(xiàn)段至多只會(huì)在線(xiàn)段交點(diǎn)處相交。整張地圖上有且僅有一塊面積無(wú)限的空白區(qū)域不屬于任何國(guó)家。每一條國(guó)界線(xiàn)兩側(cè)的區(qū)域或者隸屬于兩個(gè)不同的國(guó)家，或者分隔了一個(gè)國(guó)家與那塊無(wú)窮大的空白區(qū)域。即保證一條國(guó)界線(xiàn)兩側(cè)的區(qū)域不同時(shí)屬于同一個(gè)國(guó)家或是同時(shí)都是空白區(qū)域。所有封閉區(qū)域內(nèi)部包含且僅包含一支主力軍隊(duì)，表示了該區(qū)域的歸屬。

?

輸入說(shuō)明：

?????? 例如上圖中第一行的數(shù)據(jù)是合法的。而第二行中的數(shù)據(jù)都是不合法的。左邊的那幅圖包含線(xiàn)段兩側(cè)都是空白區(qū)域；中間的圖包含線(xiàn)段兩側(cè)區(qū)域同時(shí)屬于同一個(gè)國(guó)家；右邊的圖中軍隊(duì)被布置在了國(guó)界線(xiàn)上，因此非法；此外若最右側(cè)的圖中若沒(méi)有軍隊(duì)也是非法的。保證輸入文件提供的數(shù)據(jù)都是合法的，你的程序不需要進(jìn)行數(shù)據(jù)合法性的判定。

?

輸出：

?????? 輸出文件包括 n 行，每行第一個(gè)數(shù)字 x 表示有 x 個(gè)國(guó)家可能與這個(gè)國(guó)家交戰(zhàn)，接著在同一行中升序輸出 x 個(gè)整數(shù)，表示可能與這個(gè)國(guó)家交戰(zhàn)的國(guó)家的編號(hào)。國(guó)家按輸入中給出的順序從 1 到 n 編號(hào)。注意數(shù)字間嚴(yán)格以一個(gè)空格隔開(kāi)，并且不要在行末輸出多余的空白字符。

				
						樣例1
				
		

risk.in

4 12

3 2

11 8

12 17

1 19

0 0 10 0

10 0 20 0

20 0 20 10

20 10 20 20

20 20 10 20

10 20 0 20

0 20 0 10

0 10 0 0

10 0 10 10

0 10 10 10

20 10 10 10

10 20 10 10

?

risk.out

2 2 4

2 1 3

2 2 4

2 1 3

				
						樣例2
				
		

risk.in

4 16

170 13

24 88

152 49

110 130

60 60 140 60

140 60 140 140

140 140 60 140

60 140 60 60

0 0 200 0

200 0 200 200

200 200 0 200

0 200 0 0

40 40 160 40

160 40 160 160

160 160 40 160

40 160 40 40

20 20 180 20

180 20 180 180

180 180 20 180

20 180 20 20

?

risk.out

1 2

2 1 3

2 2 4

1 3

?

試題四：樹(shù)的統(tǒng)計(jì)

?

源程序名 :count. pas/c/cpp

可執(zhí)行文件名 : count.exe

輸入文件名 :count.in

輸出文件名 : count.out

時(shí)限 : 2s

?

一棵樹(shù)上有 n 個(gè)節(jié)點(diǎn)，編號(hào)分別為 1 到 n ，每個(gè)節(jié)點(diǎn)都有一個(gè)權(quán)值 w 。

我們將以下面的形式來(lái)要求你對(duì)這棵樹(shù)完成一些操作：

I.?????????????????? CHANGE u t : 把結(jié)點(diǎn) u 的權(quán)值改為 t

II.??????????????? QMAX u v: 詢(xún)問(wèn)從點(diǎn) u 到點(diǎn) v 的路徑上的節(jié)點(diǎn)的最大權(quán)值

III.???????????? QSUM u v: 詢(xún)問(wèn)從點(diǎn) u 到點(diǎn) v 的路徑上的節(jié)點(diǎn)的權(quán)值和

?

注意：從點(diǎn) u 到點(diǎn) v 的路徑上的節(jié)點(diǎn)包括 u 和 v 本身

?

輸入：

輸入文件的第一行為一個(gè)整數(shù) n ，表示節(jié)點(diǎn)的個(gè)數(shù)。

?????? 接下來(lái) n – 1 行，每行 2 個(gè)整數(shù) a 和 b ，表示節(jié)點(diǎn) a 和節(jié)點(diǎn) b 之間有一條邊相連。

?????? 接下來(lái) n 行，每行一個(gè)整數(shù)，第 i 行的整數(shù) wi 表示節(jié)點(diǎn) i 的權(quán)值。

?????? 接下來(lái) 1 行，為一個(gè)整數(shù) q ，表示操作的總數(shù)。

接下來(lái) q 行，每行一個(gè)操作，以“ CHANGE u t ”或者“ QMAX u v ”或者“ QSUM u v ”的形式給出。

?

對(duì)于 100 ％的數(shù)據(jù)，保證 1<=n<=30000 ， 0<=q<=200000 ；中途操作中保證每個(gè)節(jié)點(diǎn)的權(quán)值 w 在 -30000 到 30000 之間。

輸出：

?????? 對(duì)于每個(gè)“ QMAX ”或者“ QSUM ”的操作，每行輸出一個(gè)整數(shù)表示要求輸出的結(jié)果。

				
						樣例
				
		

count.in

4

1 2

2 3

4 1

4 2 1 3

12

QMAX 3 4

QMAX 3 3

QMAX 3 2

QMAX 2 3

QSUM 3 4

QSUM 2 1

CHANGE 1 5

QMAX 3 4

CHANGE 3 6

QMAX 3 4

QMAX 2 4

QSUM 3 4

count.out

4

1

2

2

10

6

5

6

5

16

?

?

?

?

?

?

?

?