試題一：殺螞蟻

程序名： antbuster.pas/c/cpp

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

輸入文件名： antbuster.in

輸出文件名： antbuster.out

時間限制： 3s

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

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

下附一張游戲截圖：

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

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

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

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

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

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

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

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

7 、螞蟻按出生的順序移動，出生得比較早的螞蟻先移動。

?

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

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

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

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

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

5、? 游戲開始時，地圖上沒有螞蟻，每個點(diǎn)上的信息素含量均為 0 。

?

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

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

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

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

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

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

再介紹一下螞蟻窩：

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

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

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

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

?

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

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

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

3、? 螞蟻扛上蛋糕時，血量會增加 int （該螞蟻出生時血量 / 2 ），但不會超過上限。

?

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

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

接著，螞蟻們在自己所在點(diǎn)留下一些信息素后，考慮移動。先出生的螞蟻先移動。

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

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

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

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

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

?

輸入：

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

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

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

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

?

輸出：

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

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

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

接下來 s 行，每行 5 個整數(shù)，依次表示一只螞蟻的年齡（單位為秒）、等級、當(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

?

樣例說明：

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

?

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

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

?

?

試題二：泡泡堂

?

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

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

輸入文件名： bnb.in

輸出文件名： bnb.out

時限： 1s

?

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

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

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

?

輸入：

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

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

?????? 接下來 n 行，每行一個整數(shù)，描述了你的對手的 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
				
		

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

bnb.in

2

1

3

2

4

bnb.out

2 0

樣例說明

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

?

樣例 2

bnb.in

6

10000000

10000000

10000000

10000000

10000000

10000000

0

0

0

0

0

0

bnb.out

12 12

樣例說明

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

?

?

?

?

?

試題三 ： Risk

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

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

輸入文件名 :risk.in

輸出文件名 :risk.out

時限 :1s

?

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

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

?

輸入：

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

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

?

輸入說明：

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

?

輸出：

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

				
						樣例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

?

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

?

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

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

輸入文件名 :count.in

輸出文件名 : count.out

時限 : 2s

?

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

我們將以下面的形式來要求你對這棵樹完成一些操作：

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

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

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

?

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

?

輸入：

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

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

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

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

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

?

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

輸出：

?????? 對于每個“ QMAX ”或者“ QSUM ”的操作，每行輸出一個整數(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

?

?

?

?

?

?

?

?