lib/Documentation/docs-sonyckson/fence8.cpp

   1 // MULTI - KNAPSACK   PROBLEM :)
   2
   3 /*
   4 ID: edestef1
   5 LANG: C++
   6 TASK: fence8
   7 */
   8 #include <cstdio>
   9 #include <cstdlib>
  10 #include <vector>
  11 #include <algorithm>
  12 #include <utility>
  13 using namespace std;
  14 FILE *fin, *fout;
  15 #define N 1030
  16 int board[51], numb;
  17 int numr;
  18 int rail[N];
  19 vector<int> Rail;
  20 int tot[139];
  21 int SUMA;
  22 int SB;
  23 int desperdicio = 0;
  24 int cortado = 0;
  25 int mx;
  26 int mini;
  27 int go(int quedan, int R, int nb){
  28         if( quedan == 0 ) return 1; // RIGHT
  29         if( nb == numb ) return 0;  // RIGHT
  30         if( R == 0 )return go ( quedan, mx, nb+1);
  31         if( SUMA - cortado > board[nb] + tot[nb+1]) return 0;
  32         if( board[nb] < mini )return go ( quedan, mx, nb+1);
  33
  34         if( rail[R] == 0 || board[nb] < R) return go ( quedan , R - 1 , nb );
  35
  36         cortado += R;
  37         board[nb] -= R;
  38         rail[R]--;
  39         if( rail[R] == 0  && R == mini ){
  40                 int a  = R;
  41                 while(a < N && rail[a] == 0 ) a++;
  42                 mini = a;
  43         }
  44         if( go ( quedan - 1 , R , nb ) ) return 1;
  45         mini = min( mini, R);
  46         rail[R]++;
  47         board[nb] += R;
  48         cortado -= R;
  49
  50
  51         if( go(quedan, R, nb+1) ) return 1;
  52         if( go( quedan, R-1, nb) ) return 1;
  53         return 0;
  54 }
  55 bool se_puede(int cant){
  56         int i,j ,k;
  57         memset(rail, 0, sizeof(rail));
  58         mx = -1; SUMA = 0;
  59         mini = INT_MAX;
  60         for(i = 0 ; i < cant;i++){
  61                 rail[Rail[i]]++;
  62                 SUMA += Rail[i];
  63                 mx = max( mx, Rail[i]);
  64                 mini = min(  mini, Rail[i] );
  65         }
  66         SB = 0; for(i = 0 ; i < numb ; i++) SB += board[i];
  67         if( SB < SUMA ) return 0;
  68         cortado = 0;
  69         return go(cant, mx, 0);
  70 }
  71 int main(){
  72         int i, j,k;
  73         fin = fopen("fence8.in", "r"); fout = fopen("fence8.out", "w");
  74         memset(rail, 0, sizeof(rail));
  75         fscanf(fin, "%i", &numb);
  76         for(i=0;i<numb;i++) fscanf(fin, "%i", &board[i]);
  77         fscanf(fin, "%i", &numr);int a;
  78         for(i=0;i<numr;i++){fscanf(fin, "%i", &a);if(a==0)continue;Rail.push_back(a);}
  79         sort(board, board+numb);
  80         sort(Rail.begin(), Rail.end());
  81
  82         tot[numb] = 0;
  83         for(i = numb-1; i>=0;i--) tot[i] = tot[i+1] + board[i];
  84
  85         for(int i = numr; i ; i-- ){
  86                 printf("%i\n", i);
  87                 if( se_puede(i) ){
  88                         fprintf(fout, "%i\n", i);
  89                         return 0;
  90                 }
  91         }
  92         fprintf(fout, "%i\n", 0);
  93         return 0;
  94 }