TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

72.7% (8/11)

Submission's AC Ratio

38.7% (74/191)

Tags

Description

本題限用C++11作答。

你玩過Charles嗎?

就算你沒玩過,看完影片之後,你也應該了解這個遊戲在做甚麼了。
是的,沒錯,現在你就是要來玩這個遊戲,但是不是用手玩,而是寫一個程式玩。

要AC這題其實沒有你想像的那麼困難。你只要能在以下的題目中看到重點就好了。

以下將會敘述在本題的Charles遊戲。若與實際遊戲有所出入,一律以題目敘述為準。

這個遊戲在一個二維空間中進行,遊戲當中,會有很多隨機出現的小球不斷地朝角色(以下稱為Charles,雖然它沒有特殊能力,應該要視為Zeus或Thomas才對)逼近,而遊戲目標是操控Charles移動使得不要被任何一個小球碰到,持續愈久愈好。為了簡化實作,我們將小球視為沒有大小的點,而「碰到小球」的定義則是Charles與小球的距離小於1單位。另外,小球在剛生成的0.5秒內不會移動、也不會影響Charles,也就是說在這段時間就算Charles與小球距離小於1單位,遊戲也不會結束。
理所當然地,隨著遊戲的進行,小球出現的頻率將會愈來愈高。但無論如何,小球不會在離Charles距離小於1.5單位的地方生成。

遊戲的基本數據如下:
遊戲空間:$100\times 50$單位(左上角為(0,0)、右下角為(100, 50),朝下為正x方向、朝右為正y方向)
Charles最高移動速度:每秒50單位(Charles的移動還有其它限制,詳細請見下方之實作細節。)
小球的壽命:13秒
小球的移動速度:每秒6單位

為了增加遊戲的難度,在(10, 10)到(30, 40)這一塊區域會不定期出現「驚嘆號」。驚嘆號出現之後3秒,將會有大量的小球從驚嘆號的位置射出,並且這些小球和一般的小球不一樣,它們不一定會往Charles的方向移動,而是各自具有自己的速度與加速度(也就是說,這些小球會以拋物線或直線的軌跡行進;這點與原始遊戲不太一樣)。當然,驚嘆號發射的小球必定具有某種規則,這點可以從影片中看出。如果你要了解驚嘆號發射出的小球規則是甚麼,你可以自己用測試標頭檔玩遊戲,或觀察測試標頭檔的程式碼。在驚嘆號發射小球的期間,不會有其他小球出現。

你可能會注意到,Charles沒有任何攻擊小球的方法。因此,在遊戲的過程中,每4秒會生成一個「道具」供Charles使用。所謂的道具,是在遊戲空間中一個固定不動、半徑為2的球。當Charles移到道具範圍內的時刻,就視為使用了該道具。以下列出所有道具的編號與功能:

編號0:NULL
沒錯,這個道具只是用來占空間的,沒有任何用處。

編號1:防護罩
使用防護罩之後,Charles將會進入防護罩狀態。防護罩狀態將會持續,直到有任何小球與Charles的距離小於2的瞬間才解除。在防護罩解除的瞬間,該位置將會產生一個半徑為8的防護網,持續2.5秒,任何進入防護網範圍的小球將被消滅。

編號2:機關槍
使用機關槍之後,Charles將會連續7秒處於機關槍狀態,在此期間Charles無法移動,但可以指定機關槍的方向。機關槍將會每80ms從Charles當前位置朝指定方向射出一發$6\times 6$單位(方向恆與座標軸同向)、移動速度為每秒80單位的子彈,子彈飛行過程中將會消滅所有進入其範圍的小球。另外,在機關槍狀態的期間,所有不是由驚嘆號發射的小球將改為往遠離Charles的方向移動,而且所有距離Charles小於6的小球都會被消滅。

編號3:飛刀
使用飛刀之後,Charles將會連續6秒處於飛刀狀態,在此期間所有與Charles距離小於4的小球都會被消滅。另外,在飛刀狀態的期間,所有不是由驚嘆號發射的小球將改為往遠離Charles的方向移動。

編號4:火焰
使用火焰之後,Charles將會連續3秒處於火焰狀態,在此期間Charles將會每60ms在當前位置留下一團$3\times 3$單位(方向恆與座標軸同向)的火焰,火焰將會持續4秒,並消滅所有進入其範圍的小球。需要注意的是,火焰開始作用的時間是Charles留下火焰的時間後40ms。

編號5:紅色能量
使用紅色能量的瞬間,會有三道半徑為8、速度為每秒40單位的紅色能量分別往60度、180度、300度方向發射,並消滅所有進入能量範圍的小球。

編號6:藍色能量
使用藍色能量後,Charles將開始蓄積藍色能量。1秒後,Charles會朝它當前的前進方向(定義為上一回合的位置指向當前回合的位置)發射半徑為12、速度為每秒40單位的藍色能量,並消滅所有進入能量範圍的小球。

編號7:蜘蛛網
使用蜘蛛網後,遊戲將會連續4秒處於蜘蛛網狀態,在此期間所有的小球將會進入緩速狀態,速度減為原先的20%。對於從驚嘆號發射的小球,其速度會受蜘蛛網影響,但加速度不受其影響。緩速狀態將會持續到小球的壽命結束或被消滅為止。

編號8:吃貨
使用吃貨後,將會有一個吃貨從原先的道具位置出現。吃貨的壽命為8秒、半徑為3.5,每0.16秒會移動到離它最接近的一個小球的位置,並消滅所有進入其範圍的小球。

編號9:毒藥
使用毒藥後,會以原先的道具位置為中心產生一個半徑為10的毒藥範圍,持續2.5秒,任何進入該範圍的小球都會被消滅。

編號10:拖把
使用拖把後,會有一個大小為$100\times 8$的拖把從y=0往正y方向以每秒鐘30單位的速度前進,任何進入該範圍的小球都會被消滅。

以上所有的狀態都是可以疊加的。注意,如果要生成道具時,遊戲空間中已經有三個道具,那麼該道具就不會生成。

到這裡,遊戲的內容應該十分清楚明瞭了。接著,就交給你玩囉(?

本題是互動題,請#include "lib2000.h"之後實作以下函數。該標頭檔已有引入<algorithm> <bitset> <chrono> <cstdint> <cstdio> <cstdlib> <cstring> <ctime> <random> <vector>十個標頭檔。

void init();:評分程式將會在遊戲開始前呼叫這個函數。
pos_type play();:評分程式每隔遊戲時間的20ms會呼叫一次這個函數。為了實作方便,我們將遊戲時間的20ms當作「一回合」,並且在與評分程式互動的過程一律以回合作為單位。這個函數必須回傳Charles的新位置。如果回傳的值並非實數(nan、inf),你會獲得一個RE。
在本遊戲當中,Charles的移動除了有最高速度的限制外,還有加速度的限制。具體來說,如果上兩回合的位置是$X$、上一回合的位置是$Y$,令$X$對$Y$的對稱點為$X'$,則本回合的位置$S$必須滿足:(1)$\overline{YS}\leq 1$、(2)$\overline{X'S}\leq 0.2$、(3)$S$在遊戲空間之內。如果你回傳的位置並不符合條件,評分程式會自動依照(1)(2)(3)的順序修正Charles的新位置。((3)的修正規則是,如果經(1)(2)修正的點在遊戲空間以外,則Charles將會移動到在遊戲空間之內離該點最近的點。注意就算符合三者的點存在,Charles最終的位置仍可能會不符合(2)。也就是說,你可以透過撞牆在一定範圍內規避加速度的限制。)

例如在上圖中,紫色點是上兩回合的位置、黑色點是上一回合的位置、藍色圓半徑為1、黃色圓半徑為0.2,則本回合Charles的位置只能落在綠色範圍內。若函數回傳的點是深綠色點,經過(1)修正後得到淺綠色點、經過(2)修正後得到橘色點,此為Charles真正移動到的位置。

另外,如果當前Charles處於機關槍狀態,則無論如何Charles將保持在原位。

注意,為了模擬實際情況,本函數每執行4ms,就會有一個回合被跳過,期間Charles將以上一回合的速度進行等速直線運動。

評分程式執行一回合的流程如下:
(1) 呼叫play取得新位置。(如果上一次play用掉過多時間,此步跳過)
(2) 根據移動規則移動Charles。
(3) 判斷有能力消滅小球的道具是否過期(編號2, 4, 5, 6, 8, 9, 10),若該道具會移動則移動之。
(4) 判斷Charles與小球之間的互動(包含編號1, 3的道具與遊戲是否結束)、小球壽命是否結束,並結算被消滅的小球(若防護罩於本回合觸發,下一回合才會結算被消滅的小球)。
(5) 改變小球速度並移動小球。
(6) 生成新的小球。
(7) 判斷Charles是否使用了道具,並改變Charles、小球或遊戲的狀態(編號1, 3, 7)、生成即時性道具產生的東西(編號5, 8, 9, 10)。
(8) 生成新的道具,與生成使用道具後產生的東西(編號2, 4, 6)。

在標頭檔中,有幾個特定的型別:
struct pos_type { float x, y; };:遊戲中所有的座標都以這個型別表示,其中x, y分別是兩座標。
struct tool_type { pos_type pos; int type; };:代表一個道具。pos代表其位置、type代表其編號。
struct spec_infor { int time; pos_type pos; };:代表驚嘆號出現的資訊。time是離驚嘆號開始作用還有多久、pos指明其中心位置。
你可以自行加載這些型別的比較、算術運算子。

有很多個函數可以呼叫(只能在play()當中呼叫這些函數):
int get_time();:這個函數回傳當前的遊戲時間,以回合計(也就是當前分數*50)。
const std::vector<pos_type>& get_ball();:這個函數回傳所有不是由驚嘆號發射的小球的位置,按照x座標排序。
const std::vector<pos_type>& get_ball_spec();:這個函數回傳所有由驚嘆號發射的小球的位置,按照x座標排序。
std::vector<tool_type> get_tool();:這個函數回傳所有當前出現的道具資訊。
std::vector<spec_infor> get_spec();:這個函數回傳所有當前出現的驚嘆號資訊。
pos_type get_pos();:這個函數回傳當前Charles的位置。
bool is_protected();:這個函數回傳當前Charles是否被防護罩保護。
int gun_time();:如果Charles當前不處於機關槍狀態,回傳-1。否則回傳機關槍狀態還會持續多久。
int sword_time();:如果Charles當前不處於飛刀狀態,回傳-1。否則回傳飛刀狀態還會持續多久。
int fire_time();:如果Charles當前不處於火焰狀態,回傳-1。否則回傳火焰狀態還會持續多久。
int blue_energy();:如果Charles當前沒有蓄積藍色能量,回傳-1。否則回傳還有多久才會發射藍色能量。
int spider_web();:如果當前遊戲不處於蜘蛛網狀態,回傳-1。否則回傳蜘蛛網狀態還會持續多久。
spec_infor pacman();:如果當前沒有小精靈出現在場上,回傳的time值是-1。否則回傳的time值是小精靈還會持續多久,pos值是小精靈當前中心位置。
void set_gun(float angle);:這個函數僅Charles處於機關槍狀態時有效,設定機關槍朝向的方向(以正x方向為0、正y方向為$\pi/2$,單位為弧度)。

評分程式將在分數滿800分或者Game Over的時候自動結束,並結算分數。

評分規則如下:最終獲得的分數是遊戲持續了幾秒(以遊戲時間計算)。如果分數小於8,或者系統發現你透過某些手法修改了評測系統的資料,你會獲得一個RE。
否則,執行時間將會等於$55000+\max(T, 500)-\left(\frac{S^ 2}{25}+28S\right)$(毫秒),其中$T$是所有initplay的執行時間,$S$是分數。
如果這個結果算出來小於等於$59213$,你會獲得一個AC。

本題的隨機產生器12小時會更換一次。也就是說,同一份程式碼如果過了12小時之後再傳一次,你可能會得到不同的結果。

Input Format

本題沒有輸入。所要引入的標頭檔、要實作的函數與可以呼叫的函數皆已於題目敘述中說明。

附上測試標頭檔Python顯示程式。測試標頭檔在執行之前需要輸入一個整數,代表亂數產生器的種子值。
若在引入測試標頭檔前定義_PRINT_PYTHON這個巨集,執行時程式將會輸出遊戲過程,你可以用Python 2.7執行顯示程式將遊戲過程圖像化(必須安裝VPython 6.11);若在引入測試標頭檔前定義_NO_DEATH這個巨集,遊戲將不考慮Game Over並持續進行直到分數滿800分為止;若在引入測試標頭檔前定義_TIME_LIMIT這個巨集為一個整數$t$,代表限制每回合執行時間為$t$毫秒;若$t\leq 0$,代表不限制執行時間。

你也可以把程式執行輸出的charles_output.txt丟到這個網站執行(感謝willypillow提供)。

2021/7/18 8e7 補充: 由於上面的Python顯示程式已經過舊(python 2.7 停用,pip 不支援vpython 6.11),可以使用這個連結的程式碼。

如果你有認真看題目,你可能會發現,其實隨便寫就可以AC了。

Output Format

本題沒有輸出。如果你輸出了任何東西,你將會獲得一個WA。

Hints

好好搶TopCoder吧(?

由於這題的Interactive Library有點大(總行數是1300餘行,同時也是TIOJ目前最長的),裡面可能有一些未知的bug。
如果你發現了一個bug,並且經過出題者的確認之後,你將可以獲得特別獎勵:指定一個這題的AC submission(不一定要是自己的),使得它的執行時間在排行榜上加或減$x$ ms,其中$0\leq x\leq 870$,前提是不能減到負數。
(注意,就算改了之後超過時間也不會TLE。神奇吧?)

你的每「次」回報成功的bug都可以獲得獎勵。所謂「次」的定義是「從回報到出題者確認並修正」,並且同一個人每「次」的期間皆不能重疊。如果有很多人提出相同的bug,只有第一次提出的人能獲得獎勵。
(換句話說:出題者沒辦法平行處理,只能一次處理一個bug。你如果發現一個大bug,你可以把它拆成小bug後一個一個回報,獲得很多次獎勵,或一次回報所有的bug,並只獲得一次獎勵。但別忘了,出題者在修正一個bug的同時,也有可能會發現其他的bug。)

獎勵列表:

日期使用者對象(submission#)$\Delta$
2017/10/03willypillow82677-870

Problem Source

TIOJ 2000 紀念。
Problem Set by Yihda Yol,感謝IOI 2017國手群提供想法。

Subtasks

No. Testdata Range Score
1 0 2000

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 59213 1048576 262144 1