uva 311 - Packets

  1  /*
  2  Problem link
  3  Type: Ad hoc, Greedy
  4  Algorithm:
  5      Let p[i] is the number of parcels need to carry box size i
  6      Let d[i] is the space left of the parcels that carry box size i
  7      For the box of size 6, 5, 1, each of them has to be carried in 1 parcel
  8      -> p[i] = i for i = 4 to 6;
  9      Parcels carry box size 5 leave 11 space in each of them -> d[5] = p[5]*11
 10      Parcels carry box size 4 leave 20 space in each of them -> d[4] = p[4]*20
 11      Parcels carry box size 3 can carry 4 of them each parcel without any space,
 12      hence the space left is only in the last box d[3] = 36-(a[3]%4)*9, d[3] = 36-> d[3] = 0
 13  
 14      Now box size 2 can only put in the parcels that carry box size 4 and 3,
 15      we consider these two case and update d[3],d[4] and a[2]
 16      If there are still box size 2 then we must put them in new parcel
 17      and calculate d[2]
 18  
 19      For box size 1, try to put them in the space from d[6] to d[2],
 20      if there are still box size 1 left, we must put them in new parcel.
 21  
 22      result = sum(p[i]) for i = 1 to 6
 23  */
 24  #include <iostream>
 25  #include <cstdio>
 26  #include <cstring>
 27  
 28  using namespace std;
 29  const int n = 6;
 30  
 31  int a[7], p[7], d[7];
 32  
 33  int Cell(int x, int y) { return (x%y==0? x/y: x/y+1); }
 34  bool ReadFile();
 35  int Solve();
 36  
 37  int main()
 38  {
 39      while (ReadFile()) cout << Solve() << endl;
 40      return 0;
 41  }
 42  
 43  bool ReadFile()
 44  {
 45      memset(a,0,sizeof(a));
 46      memset(p,0,sizeof(p));
 47      memset(d,0,sizeof(d));
 48      for (int i=1; i<=n; i++) cin >> a[i];
 49      int s = 0;
 50      for (int i=1; i<=n; i++) s+=a[i];
 51      return(s!=0);
 52  }
 53  
 54  int Solve()
 55  {
 56      p[6] = a[6];
 57      p[5] = a[5];
 58      p[4] = a[4];
 59      p[3] = Cell(a[3],4);
 60      d[5] = 11*p[5];
 61      d[3] = 36-  (a[3]%4)*9;
 62      if (d[3]==36) d[3] = 0;
 63      d[4] = 20*p[4];
 64      int t2 = Cell(a[2],5);
 65      if (t2>p[4])
 66      {
 67          a[2] -= p[4]*5;
 68          d[4] = 0;
 69      }
 70      else
 71      {
 72          d[4] = d[4] - 4*a[2];
 73          a[2] = 0;
 74      }
 75  
 76      if (d[3]<36 && a[2]>0)
 77      {
 78          if (d[3] == 27)
 79          {
 80              if (a[2]<=5)
 81              {
 82                  d[3] = d[3]-4*a[2];
 83                  a[2] = 0;
 84              }
 85              else
 86              {
 87                  d[3] = 7;
 88                  a[2] = a[2]-5;
 89              }
 90          }
 91          else if (d[3] == 18)
 92          {
 93               if (a[2]<=3)
 94              {
 95                  d[3] = d[3]-4*a[2];
 96                  a[2] = 0;
 97              }
 98              else
 99              {
100                  d[3] = 6;
101                  a[2] = a[2]-3;
102              }
103          }
104          else if (d[3] == 9)
105          {
106               if (a[2]<=1)
107              {
108                  d[3] = d[3]-4*a[2];
109                  a[2] = 0;
110              }
111              else
112              {
113                  d[3] = 5;
114                  a[2] = a[2]-1;
115              }
116          }
117      }
118  
119      if (a[2]>0)
120      {
121          p[2] = Cell(a[2],9);
122          d[2] = 36-4*(a[2]%9);
123          if (d[2]==36) d[2] = 0;
124      }
125  
126      for (int i=6; i>=2; i--) a[1] = a[1] - d[i];
127  
128      if (a[1]>0) p[1] = Cell(a[1],36);
129      int result = 0;
130      for (int i=1; i<=n; i++) result+=p[i];
131      return result;
132  }