以下是原始的題目敘述(經過不專業翻譯)。
國際塔防大賽的規則如下。
戰場是連續的 10 個格子,編號從 1 到 10,每個格子當中至多可以蓋一座塔。而你要防守的對象是 10 隻血量為 $h$ 的怪物,分別在第一秒、第二秒、…、第十秒進入第一個格子。每隻怪物還會有一個會被緩速塔所影響的獨立屬性 $delay$,初始值為 1。假設某隻怪物的 delay 值現在是 $d$,且他在第 $t$ 秒進入這個格子,那麼他會在第 $t+d$ 秒的時候進入下一個格子。
塔的規則可以分為下列三種:
- 砲塔:每秒鐘砲塔會對最先進入自己格子的怪物造成一點傷害。每個砲塔要價 3 元。砲塔在地圖上被標示成
G
。- 火箭塔:每三秒火箭塔會對所有在自己格子的怪物造成四點傷害(第一次攻擊是在第 3 秒)。每個火箭塔要價 10 元,標示為
R
。- 緩速塔:每個緩速塔會對所有在他自身那格以及後面四格,總共五格的怪物增加 delay 值 1。舉個例子,假設緩速塔放在 1,2,4 三格,那麼對於在第六格的怪物的 delay 值就是 3。每個緩速塔要價 5 元,標示為
S
。怪物走出這個戰場的方式是從活著第十格離開,而一旦血量降到 0 或以下就會立刻死亡。遊戲的目標是在遊戲開始前放好塔並殺死盡可能多的怪物。
請找出所有能夠殺死嚴格比使用小於 $s$ 元更多隻怪物的金額 $s$ 並輸出一些相關資訊。
以上是原始的題目敘述。為了某些方便,題目做了一些小更改:總格子數為 6 而非 10,而總怪物數也降為 6。
請給出與以下的程式碼 edit distance 不超過 1 的解。
// =^● ⋏ ●^=
#include <bits/stdc++.h>
using namespace std;
int HP;
struct towers {
int cost;
string tower;
towers(int c = 1000000000, string t = ""): cost(c), tower(t) {}
void update(const string &s) {
int t = 0;
for (int i = 0; i < 6; ++i) {
if (s[i] == 'G') t += 3;
else if (s[i] == 'R') t += 10;
else if (s[i] == 'S') t += 5;
}
if (t < cost) cost = t, tower = s;
else if (t == cost && s < tower) tower = s;
}
} ans[10];
struct monster {
int hp, stay;
monster(int a = 0, int b = 0): hp(a), stay(b) {}
};
int delay[10];
deque<monster> grid[10];
void hit(string s) {
memset(delay, 0, sizeof(delay));
for (int i = 1; i <= 6; ++i) delay[i] = 1;
for (int i = 1; i <= 6; ++i) if (s[i - 1] == 'S') for (int z = 0; z < 5 && i + z <= 6; ++z) ++delay[i + z];
for (int i = 1; i <= 6; ++i) grid[i].clear();
int monster_on_grid = 0, nowt = 0;
while (monster_on_grid > 0 || nowt == 0) {
++nowt;
for (int i = 6; i >= 1; --i) {
while (grid[i].size()) {
if (grid[i].front().stay == delay[i] - 1) {
grid[i + 1].emplace_back(grid[i].front().hp, 0);
grid[i].pop_front();
if (i == 6) --monster_on_grid;
}
else break;
}
for (auto &m : grid[i]) ++m.stay;
}
if (nowt <= 6) {
grid[1].emplace_back(HP, 0);
++monster_on_grid;
}
for (int i = 1; i <= 6; ++i) {
if (s[i - 1] == 'G') {
if (grid[i].size()) {
--grid[i].front().hp;
if (grid[i].front().hp <= 0) {
grid[i].pop_front();
--monster_on_grid;
}
}
}
else if (s[i - 1] == 'R' && nowt % 3 == 0) {
for (int j = 0; j < int(grid[i].size()); ++j) grid[i][j].hp -= 4;
deque<monster> tmp;
for (int j = 0; j < int(grid[i].size()); ++j) {
if (grid[i][j].hp <= 0) --monster_on_grid;
else tmp.push_back(grid[i][j]);
}
grid[i] = tmp;
}
}
}
int killed = 6 - grid[7].size();
ans[killed].update(s);
}
void generate(string s) {
if (s.size() == 6u) {
hit(s);
return;
}
generate(s + '.');
generate(s + 'G');
generate(s + 'S');
generate(s + 'R');
return;
}
void meow() {
for (int i = 0; i <= 6; ++i) ans[i] = towers();
generate("");
stack<int> print;
print.push(6);
int lac = ans[6].cost;
for (int i = 5; i >= 1; --i) if (ans[i].cost < lac) print.push(i), lac = ans[i].cost;
while (print.size()) {
if (ans[print.top()].cost > 1000) break;
cout << "$" << ans[print.top()].cost << " -> kill " << print.top() << " with " << ans[print.top()].tower << endl;
print.pop();
}
}
int main() {
cin >> HP;
meow();
}
一個整數 $h$。
對於任何一個不可能使用小於 $s$ 元殺死大於等於 $k$ 隻怪物且能殺死 $k$ 隻怪物的金額 $s$ 輸出一行。
每一行的格式必須要像是 $s -> kill k with t
,其中 $t$ 是關於塔的擺設資訊。.
代表沒有放塔的格子。如果有多種擺法,請輸出字典序最小的那種。
No. | Testdata Range | Score |
---|---|---|
1 | 0~17 | 1 |