Dwarves solution


/ Published in: C++
Save to your folder(s)

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


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.