ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1240. Heroes of Might and Magic

I think my solution is correct, but it keep WA3...
Posted by fOrgIvE 1 Jun 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...
Posted by Denis Koshman 9 Aug 2008 22:47
I had WA4 and it was 4th example test, so your WA3 might be 3rd example test given inside problem statement.