ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1240. Heroes of Might and Magic

I think my solution is correct, but it keep WA3...
Послано fOrgIvE 1 июн 2007 12:59
#include <iostream>
#include <queue>
#include <string>

using    namespace    std;

const    int    maxn = 10;
const    int    maxhph = 100;
const    int    maxmph = 50;

struct    state
{
    state()    {}
    state(int vhp, int vmp, int vpos)
    :hp(vhp), mp(vmp), pos(vpos)    {}
    int    hp, mp, pos;
};

int    n, hph, hpm, v, dh;
int    l[maxn + 1];
int    f[maxhph + 1][maxmph + 1][maxn + 1];
pair<state, int>    g[maxhph + 1][maxmph + 1][maxn + 1];
queue<state>    q;

inline    void    init()
{
    int    mph, nm;
    cin >> n >> hph >> mph >> hpm >> nm >> v >> dh;
    for (int i = 1; i <= n; ++i)    cin >> l[i];
    for (int i = 1; i <= hph; ++i)
        for (int j = 1; j <= mph; ++j)
            for (int k = 1; k <= n; ++k)
                f[i][j][k] = INT_MAX;
    q.push(state(hph, mph, n));
    f[hph][mph][n] = hpm * nm;
}

inline    int    getk(int h)
{
    if (h % hpm)
        return    h / hpm + 1;
    else
        return    h / hpm;
}

inline    void    monster(state &x, const int h)
{
    x.pos -= min(v, x.pos - 1);
    if (x.pos == 1)    x.hp -= getk(h);
}

inline    void    update(const state &x, const state &from, int h, int id)
{
    if (x.hp <= 0 || x.mp <= 0)    return;
    if (h < f[x.hp][x.mp][x.pos])
    {
        f[x.hp][x.mp][x.pos] = h;
        g[x.hp][x.mp][x.pos] = make_pair(from, id);
        q.push(x);
    }
}

inline    string    itos(int x)
{
    char    s[10];
    sprintf(s, "%d", x);
    return    string(s);
}

void    show(state x, int id)
{
    string    ans;
    while (id != 0)
    {
        switch (id)
        {
        case -1:
            ans = "L\n" + ans;
            break;
        case -2:
            ans = "H\n" + ans;
            break;
        default:
            ans = "T " + itos(id) + '\n' + ans;
            break;
        }
        id = g[x.hp][x.mp][x.pos].second;
        x = g[x.hp][x.mp][x.pos].first;
    }
    cout << "VICTORIOUS\n" << ans << endl;
    exit(0);
}

void    solve()
{
    while (!q.empty())
    {
        state    x = q.front();
        int    h = f[x.hp][x.mp][x.pos];
        --x.mp;    h -= l[x.pos];
        if (h <= 0)    show(q.front(), -1);
        monster(x, h);    update(x, q.front(), h, -1);

        x = q.front();
        h = f[x.hp][x.mp][x.pos];
        --x.mp;    x.hp = min(hph, x.hp + dh);
        monster(x, h);    update(x, q.front(), h, -2);

        for (int i = n; i >= 1; --i)
        {
            x = q.front();
            h = f[x.hp][x.mp][x.pos];
            --x.mp;    x.pos = i;
            monster(x, h);    update(x, q.front(), h, i);
        }
        q.pop();
    }
    cout << "DEFEATED" << endl;
}

int    main()
{
    init();
    solve();
    return    0;
}
Re: I think my solution is correct, but it keep WA3...
Послано Denis Koshman 9 авг 2008 22:47
I had WA4 and it was 4th example test, so your WA3 might be 3rd example test given inside problem statement.