uva 410 - Station Balance

  1 /*
  2  Problem link
  3  Type: Recursion - Greedy
  4  Algorithm:
  5      For this problem, all I care about is the number of chamber
  6      that contains 2 specimens, the other chambers contain 0 or 1
  7      specimens so just put in all the specimens left, each in one
  8      chamber. For s specimens, what is the minimum
  9      and maximum number of chambers that contains 2 specimens (2-chamber)?
 10  
 11      Let's imagine this, we put one specimen in each chamber starting
 12      from 1. If the number of specimens is bigger, we continue to put
 13      specimens in from the first chamber, therefore (s-c) chamber will
 14      contains 2 specimens and the others contain 1.
 15      It is obviously that s specimens will need s/2 chambers or s/2+1
 16      chambers to take care of them. If s is odd, 1 more chamber will
 17      contain 1 specimen and the other 0. Otherwise, all other chambers
 18      will contain 0.
 19      -> min (2-chamber) = s-c;
 20      -> max (2-chamber) = s/2;
 21  
 22      For each of the 2-chamber = k. We generate k pairs of specimens,
 23      one pair in 1 2-chamber and calculate the imbalance.
 24  
 25      My function Attempt to generate k pairs:
 26          nIndex: the current index to choose
 27          full: the number of 2-chambers which are full.
 28          half: the number of 2-chambers which are half (1 specimens)
 29  */
 30  #include <iostream>
 31  #include <cstdio>
 32  #include <cstring>
 33  #include <cmath>
 34  #include <vector>
 35  
 36  using namespace std;
 37  const int maxn = 11;
 38  
 39  int s,c;
 40  int left;
 41  double am, result;
 42  vector<int> a;
 43  int cnt[maxn], chamberOf[maxn], chamberMass[maxn];
 44  vector<int> ans[maxn];
 45  
 46  bool ReadFile();
 47  void Attempt(int nIndex, int k, int full, int half);
 48  
 49  int main()
 50  {
 51      int nTest = 0;
 52      while (ReadFile())
 53      {
 54          result = 1000000;
 55          nTest++;
 56  
 57          for (int i = max(0,s-c); i <= s/2; i++)
 58          {
 59              for (int j = 0; j<=maxn; j++) cnt[j] = 0;
 60              for (int j = 1; j <= i; j++) cnt[j] = 2;
 61  
 62              Attempt(0,i,0,0);
 63          }
 64  
 65          printf("Set #%d\n",nTest);
 66          for (int i = 0; i < c; i++)
 67          {
 68              cout << " " << i << ":";
 69              for (unsigned int j = 0; j < ans[i].size(); j++)
 70                  cout << " " << ans[i][j];
 71              cout << endl;
 72          }
 73          printf("IMBALANCE = %0.5f\n\n",result);
 74      }
 75      return 0;
 76  }
 77  
 78  bool ReadFile()
 79  {
 80      am = 0;
 81      cin >> c >> s;
 82      a.clear();
 83      if (cin.eof()) return false;
 84  
 85      for (int i=1; i<=s; i++)
 86      {
 87          int value;
 88          cin >> value;
 89          a.push_back(value);
 90          am += value;
 91      }
 92      am = (double)am/c;
 93      return true;
 94  }
 95  
 96  void Attempt(int nIndex, int k, int full, int half)
 97  {
 98      if ((unsigned int)nIndex == a.size())   // At the end, just do the calculation
 99      {
100          int eps = 0;
101          for (int i = 1; i <= c; i++) chamberMass[i] = 0;
102          for (unsigned int i = 0; i < a.size(); i++)
103              if (chamberOf[i] != 0) chamberMass[chamberOf[i]] += a[i];
104              else
105              {
106                  chamberMass[k+1+eps] = a[i];
107                  eps++;
108              }
109  
110          double imbalance = 0;
111          for (int i = 1; i <= c; i++) imbalance += (double)abs(chamberMass[i] - am);
112          if (imbalance < result)
113          {
114              for (int i = 0; i < maxn; i++) ans[i].clear();
115              result = imbalance;
116  
117              eps = 0;
118              for (unsigned int i = 0; i < a.size(); i++)
119                  if (chamberOf[i] != 0) ans[chamberOf[i]-1].push_back(a[i]);
120                  else
121                  {
122                      ans[k+eps].push_back(a[i]);
123                      eps++;
124                  }
125          }
126          return;
127      }
128  
129      for (int i=0; i<=k; i++)
130      {
131          if (cnt[i]>0 && i>0)
132          {
133              chamberOf[nIndex] = i;
134              cnt[i]--;
135              if (cnt[i] == 0) { full++; half--; }            // Update full and half
136              else if (cnt[i] == 1) half++;                   // Update half
137              if ((k-full)*2 - half <= s-nIndex-1) Attempt(nIndex+1,k,full,half); // My condition
138              cnt[i]++;
139              if (cnt[i] == 2) full--;                        // Update full and half
140              else if (cnt[i] == 1) half--;
141          }
142          else if (i == 0)            // 0 means no 2-chamber for current index
143          {
144              chamberOf[nIndex] = i;
145              if ((k-full)*2 - half <= s-nIndex-1) Attempt(nIndex+1,k,full,half);
146          }
147      }
148  
149  }