Advanced Search

Return to Snippet

Revision: 6960
at June 26, 2008 05:30 by u1ik
Initial Code 
#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;
}
Initial URL 
http://infoweekly.blogspot.com/2008/06/dwarves.html
Initial Description 
Probably not correct, but passed tests http://www.liis.ro/~lotinfo2008/probleme/pitici.zip
Initial Title 
Dwarves solution
Initial Tags 

                                

                                                            

                                    

                                        

                                        Initial Language
                                        

                                    

                                    
C++