Posted By

u1ik on 06/26/08

Tagged

Versions (?)

Last Edited at 06/26/08 05:30am

Statistics

Viewed 208 times

Favorited by 0 user(s)

Related snippets

Dwarves solution

/ Published in: C++

Probably not correct, but passed tests http://www.liis.ro/~lotinfo2008/probleme/pitici.zip

Highlighted TextExpand

#include <cstdio>
#include <algorithm>
using namespace std;

struct Dwarf{
    int l, h;
    bool sacrificed;
    bool operator < (const Dwarf& d) const
    {
        return l + h > d.l + d.h;
    }
};

const int N = 2000;
Dwarf d[N];
int n;
int H;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &d[i].h, &d[i].l);
        d[i].sacrificed = false;
    }
    scanf("%d", &H);
    sort(d, d + n);
    int h_s = 0;
    for (int i = n-1; i >= 0; --i)
    {
        int h_p = 0;
        for (int j = 0; j < i; ++j) h_p += d[j].h;
        if (d[i].h + d[i].l + h_s + h_p < H)
        {
            int k = i;
            for (int j = i + 1; j < n; ++j)
            if (!d[j].sacrificed)
            {
                if (d[j].h > d[k].h) k = j;
            }
            d[k].sacrificed = true;
            h_s += d[k].h;
        }
    }   
    int res = 0;
    for (int i = 0; i < n; ++i)
        if (d[i].sacrificed) res++;
    printf("%d\n", n - res);
    return 0;
}

URL: http://infoweekly.blogspot.com/2008/06/dwarves.html

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.