TopCoder

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

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

83.3% (5/6)

Tags

Description

以下是原始的題目敘述(經過不專業翻譯)。

國際塔防大賽的規則如下。

戰場是連續的 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();
}

Input Format

一個整數 $h$。

  • $1 \leq h \leq 18$

Output Format

對於任何一個不可能使用小於 $s$ 元殺死大於等於 $k$ 隻怪物且能殺死 $k$ 隻怪物的金額 $s$ 輸出一行。

每一行的格式必須要像是 $s -> kill k with t ,其中 $t$ 是關於塔的擺設資訊。. 代表沒有放塔的格子。如果有多種擺法,請輸出字典序最小的那種。

Sample Input 1

5

Sample Output 1

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

Hints

Problem Source

Subtasks

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