Advanced Search

Dwarves solution

/ Published in: C++
Save to your folder(s)
Probably not correct, but passed tests http://www.liis.ro/~lotinfo2008/probleme/pitici.zip

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct Dwarf{
  6.     int l, h;
  7.     bool sacrificed;
  8.     bool operator < (const Dwarf& d) const
  9.     {
  10.         return l + h > d.l + d.h;
  11.     }
  12. };
  13.  
  14. const int N = 2000;
  15. Dwarf d[N];
  16. int n;
  17. int H;
  18.  
  19. int main()
  20. {
  21.     scanf("%d", &n);
  22.     for (int i = 0; i < n; ++i)
  23.     {
  24.         scanf("%d %d", &d[i].h, &d[i].l);
  25.         d[i].sacrificed = false;
  26.     }
  27.     scanf("%d", &H);
  28.     sort(d, d + n);
  29.     int h_s = 0;
  30.     for (int i = n-1; i >= 0; --i)
  31.     {
  32.         int h_p = 0;
  33.         for (int j = 0; j < i; ++j) h_p += d[j].h;
  34.         if (d[i].h + d[i].l + h_s + h_p < H)
  35.         {
  36.             int k = i;
  37.             for (int j = i + 1; j < n; ++j)
  38.             if (!d[j].sacrificed)
  39.             {
  40.                 if (d[j].h > d[k].h) k = j;
  41.             }
  42.             d[k].sacrificed = true;
  43.             h_s += d[k].h;
  44.         }
  45.     }   
  46.     int res = 0;
  47.     for (int i = 0; i < n; ++i)
  48.         if (d[i].sacrificed) res++;
  49.     printf("%d\n", n - res);
  50.     return 0;
  51. }

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

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.