試題一：殺螞蟻

程序名： antbuster.pas/c/cpp

可執行文件名： antbuster.exe

輸入文件名： antbuster.in

輸出文件名： antbuster.out

時間限制： 3s

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

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

下附一張游戲截圖：

為了拿到盡可能高的分數，佳佳設計了很多種造塔的方案，但在嘗試了其中的一小部分后，佳佳發現，這個游戲實在是太費時間了。為了節省時間，佳佳決定寫個程序，對于每一種方案，模擬游戲進程，根據效果來判斷方案的優劣。

根據自己在游戲中積累的一些經驗，以及上網搜到的一些參數，佳佳猜了螞蟻爬行的算法，并且假設游戲中的螞蟻也是按這個規則選擇路線：

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

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

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

4 、如果將每只螞蟻在洞口出現的時間作為它的活動時間的第 1 秒，那么每當這只螞蟻的活動時間秒數為 5 的倍數的時候，它先按規則 1~3 確定一個方向，面對該方向后逆時針轉 90 °，若它沿當前方向會走到一個不可達點，它會不停地每次逆時針轉 90 °，直到它面對著一個可達的點，這樣定下的方向才是螞蟻最終要爬去的方向。

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

6 、你可以認為螞蟻在選定方向后，瞬間移動到它的目標點，這一秒鐘剩下的時間里，它就停留在目標點。

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

?

然后，是一些有關地圖的信息：

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

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

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

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

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

?

一些有關炮塔的信息：

1、? 炮塔被放置在地圖上的整點處。

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

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

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

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

再介紹一下螞蟻窩：

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

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

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

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

?

最后給出關于蛋糕的介紹：

1、? 簡單起見，你可以認為此時只剩最后一塊蛋糕了。如果有螞蟻走到蛋糕的位置，并且此時蛋糕沒有被扛走，那么這只螞蟻就扛上了蛋糕。螞蟻被打死后蛋糕歸位。

2、? 如果一只扛著蛋糕的螞蟻走到螞蟻窩的位置，我們就認為螞蟻成功搶到了蛋糕，游戲結束。

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

?

整理一下 1 秒鐘內發生的事件：

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

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

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

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

攻擊結束后，如果發現扛蛋糕的螞蟻沒死并在窩的位置，就認為螞蟻搶到了蛋糕。游戲也在此時結束。

最后，地圖上所有點的信息素損失 1 單位。所有螞蟻的年齡加 1 。

漫長的 1 秒到此結束。

?

輸入：

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

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

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

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

?

輸出：

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

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

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

接下來 s 行，每行 5 個整數，依次表示一只螞蟻的年齡（單位為秒）、等級、當前血量，以及在地圖上的位置（ 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 秒內有 5 只螞蟻出生，都是向東爬行，其中第 1~4 只在路過（ 0 ， 2 ）點時被激光塔傷了 1 格血。在第 5 秒的時候，最早出生的螞蟻按移動規則 1~3 本來該向東移動，但由于規則 4 的作用，它在發現向北和向西移動都會到達不可達點后，最終選擇了向南移動。

?

數據說明：

100% 的數據滿足 1 ≤ n,m ≤ 8 ， s ≤ 20 ， t ≤ 200,000

?

?

試題二：泡泡堂

?

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

可執行文件名： bnb.exe

輸入文件名： bnb.in

輸出文件名： bnb.out

時限： 1s

?

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

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

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

?

輸入：

?????? 輸入文件的第一行為一個整數 n ，表示每支代表隊的人數。

?????? 接下來 n 行，每行一個整數，描述了 n 位浙江隊的選手的實力值。

?????? 接下來 n 行，每行一個整數，描述了你的對手的 n 位選手的實力值。

?????? 20 ％的數據中， 1<=n<=10 ；

40 ％的數據中， 1<=n<=100 ；

60 ％的數據中， 1<=n<=1000 ；

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

?

輸出：

				
						樣例1
				
		

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

bnb.in

2

1

3

2

4

bnb.out

2 0

樣例說明

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

?

樣例 2

bnb.in

6

10000000

10000000

10000000

10000000

10000000

10000000

0

0

0

0

0

0

bnb.out

12 12

樣例說明

對手都是認真學習的好孩子，不會打游戲。無論如何排列出場順序都無法改變被蹂躪的結果。浙江隊總能取得全勝的結果。

?

?

?

?

?

試題三 ： Risk

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

可執行文件名 :risk.exe

輸入文件名 :risk.in

輸出文件名 :risk.out

時限 :1s

?

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

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

?

輸入：

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

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

?

輸入說明：

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

?

輸出：

?????? 輸出文件包括 n 行，每行第一個數字 x 表示有 x 個國家可能與這個國家交戰，接著在同一行中升序輸出 x 個整數，表示可能與這個國家交戰的國家的編號。國家按輸入中給出的順序從 1 到 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

?

試題四：樹的統計

?

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

可執行文件名 : count.exe

輸入文件名 :count.in

輸出文件名 : count.out

時限 : 2s

?

一棵樹上有 n 個節點，編號分別為 1 到 n ，每個節點都有一個權值 w 。

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

I.?????????????????? CHANGE u t : 把結點 u 的權值改為 t

II.??????????????? QMAX u v: 詢問從點 u 到點 v 的路徑上的節點的最大權值

III.???????????? QSUM u v: 詢問從點 u 到點 v 的路徑上的節點的權值和

?

注意：從點 u 到點 v 的路徑上的節點包括 u 和 v 本身

?

輸入：

輸入文件的第一行為一個整數 n ，表示節點的個數。

?????? 接下來 n – 1 行，每行 2 個整數 a 和 b ，表示節點 a 和節點 b 之間有一條邊相連。

?????? 接下來 n 行，每行一個整數，第 i 行的整數 wi 表示節點 i 的權值。

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

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

?

對于 100 ％的數據，保證 1<=n<=30000 ， 0<=q<=200000 ；中途操作中保證每個節點的權值 w 在 -30000 到 30000 之間。

輸出：

?????? 對于每個“ QMAX ”或者“ QSUM ”的操作，每行輸出一個整數表示要求輸出的結果。

				
						樣例
				
		

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

?

?

?

?

?

?

?

?