TopCoder

AWfulsome
It's so $\huge{AW_{fulsome}}$

100.0% (5/5)

83.3% (5/6)

Description

• 砲塔：每秒鐘砲塔會對最先進入自己格子的怪物造成一點傷害。每個砲塔要價 3 元。砲塔在地圖上被標示成 G
• 火箭塔：每三秒火箭塔會對所有在自己格子的怪物造成四點傷害（第一次攻擊是在第 3 秒）。每個火箭塔要價 10 元，標示為 R
• 緩速塔：每個緩速塔會對所有在他自身那格以及後面四格，總共五格的怪物增加 delay 值 1。舉個例子，假設緩速塔放在 1，2，4 三格，那麼對於在第六格的怪物的 delay 值就是 3。每個緩速塔要價 5 元，標示為 S

// =＾● ⋏ ●＾=
#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;

5

Sample Output 1

\$13 -> kill 2 with ....GR \$15 -> kill 6 with .GGGGG

Problem Source

No. Testdata Range Score
1 0~17 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1