#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <float.h>

int genparams ( int n, int *c, int *s, int *t, int *r, double *p, double *q )
{
   int C;
   int i;

   C = 0;
   for (i=0; i<n; ++i) {
      c[i] = 20 + rand() % 80; C += c[i];
      s[i] = 50 + rand() % 50;
      t[i] = 10 + rand() % 30;
      p[i] = 0.5 + (double)rand() / ((double)RAND_MAX * 2);
      q[i] = p[i] * (double)rand() / (double)RAND_MAX;
      r[i] = 1 + rand() % 5;
   }
   C <<= 1;
   C += rand() % C;

   printf("Capital          (C) : %d\n", C);
   printf("Costs            (c) :"); for (i=0; i<n; ++i) printf(" %2d", c[i]); printf("\n");
   printf("Selling price    (s) :"); for (i=0; i<n; ++i) printf(" %2d", s[i]); printf("\n");
   printf("Selling price    (t) :"); for (i=0; i<n; ++i) printf(" %2d", t[i]); printf("\n");
   printf("Maintenance cost (r) :"); for (i=0; i<n; ++i) printf(" %2d", r[i]); printf("\n");
   printf("Probabilities    (p) :"); for (i=0; i<n; ++i) printf(" %12.10lf", p[i]); printf("\n");
   printf("Probabilities    (q) :"); for (i=0; i<n; ++i) printf(" %12.10lf", q[i]); printf("\n");

   return C;
}

void optimalbuy1 ( int n, int C, int *c, int *s, int *t, double *p )
{
   int *m;
   int **B;
   double **T, q, best, curr;
   int i, j, k, count;

   m = (int *)malloc(n * sizeof(int));
   B = (int **)malloc(n * sizeof(int *));
   T = (double **)malloc(n * sizeof(double *));

   for (i=0; i<n; ++i) {
      B[i] = (int *)malloc((C+1) * sizeof(int));
      T[i] = (double *)malloc((C+1) * sizeof(double));
   }

   for (j=0; j<c[0]; ++j) {
      B[0][j] = 0;
      T[0][j] = -DBL_MAX;
   }
   for (j=c[0]; j<=C; ++j) {
      B[0][j] = j / c[0];
      q = 1; for (k=0; k<B[0][j]; ++k) q *= p[0];
      T[0][j] = q*t[0] + (1-q)*s[0];
   }

   for (i=1; i<n; ++i) {
      for (j=0; j<c[i]; ++j) {
         B[i][j] = 0;
         T[i][j] = -DBL_MAX;
      }

      for (j=c[i]; j<=C; ++j) {
         best = 0; count = 0;
         q = 1;
         for (k=1; k<=j/c[i]; ++k) {
            q *= p[i];
            curr = T[i-1][j-k*c[i]] + q*t[i] + (1-q)*s[i];
            if (curr > best) {
               best = curr;
               count = k;
            }
         }
         B[i][j] = count;
         T[i][j] = best;
      }
   }

   j = C;
   for (i=n-1; i>=0; --i) {
      m[i] = B[i][j];
      j -= m[i] * c[i];
   }

   printf("\n+++ Part 1: Best buying option\n");
   j = 0;
   for (i=0; i<n; ++i) {
      printf("    Machine %3d: %3d copies, cost = %6d\n", i, m[i], m[i] * c[i]);
      j += m[i] * c[i];
   }
   printf("--- Total buying cost             = %6d\n", j);
   printf("--- Expected total profit         = %15.8lf\n", T[n-1][C]);

   for (i=0; i<n; ++i) {
      free(B[i]);
      free(T[i]);
   }
   free(m);
   free(B);
   free(T);
}

void optimalbuy2 ( int n, int C, int *c, int *s, int *t, int *r, double *p, double *q )
{
   int *m, *u;
   int **B;
   int **U;
   double **T, q1, q2, best, curr;
   int i, j, k, count, maintain;

   m = (int *)malloc(n * sizeof(int));
   u = (int *)malloc(n * sizeof(int));
   B = (int **)malloc(n * sizeof(int *));
   U = (int **)malloc(n * sizeof(int *));
   T = (double **)malloc(n * sizeof(double *));

   for (i=0; i<n; ++i) {
      B[i] = (int *)malloc((C+1) * sizeof(int));
      U[i] = (int *)malloc((C+1) * sizeof(int));
      T[i] = (double *)malloc((C+1) * sizeof(double));
   }

   for (j=0; j<c[0]; ++j) {
      B[0][j] = 0;
      T[0][j] = -DBL_MAX;
      U[0][j] = -1;
   }
   for (j=c[0]; j<=C; ++j) {
      B[0][j] = j / c[0];
      q1 = 1; for (k=0; k<B[0][j]; ++k) q1 *= p[0];
      best = q1*t[0] + (1-q1)*s[0];
      T[0][j] = best;
      U[0][j] = 0;
      q2 = 1; for (k=0; k<B[0][j]; ++k) q2 *= q[0];
      best = q2*t[0] + (1-q2)*s[0] - B[0][j]*r[0];
      if (best > T[0][j]) {
         T[0][j] = best;
         U[0][j] = 1;
      }
   }

   for (i=1; i<n; ++i) {
      for (j=0; j<c[i]; ++j) {
         B[i][j] = 0;
         T[i][j] = -DBL_MAX;
         U[i][j] = -1;
      }

      for (j=c[i]; j<=C; ++j) {
         best = 0; count = 0; maintain = -1;
         q1 = q2 = 1;
         for (k=1; k<=j/c[i]; ++k) {
            q1 *= p[i];
            curr = T[i-1][j-k*c[i]] + q1*t[i] + (1-q1)*s[i];
            if (curr > best) {
               best = curr;
               count = k;
               maintain = 0;
            }
            q2 *= q[i];
            curr = T[i-1][j-k*c[i]] + q2*t[i] + (1-q2)*s[i] - k*r[i];
            if (curr > best) {
               best = curr;
               count = k; 
               maintain = 1;
            }
         }
         B[i][j] = count;
         T[i][j] = best;
         U[i][j] = maintain;
      }
   }

   j = C;
   for (i=n-1; i>=0; --i) {
      m[i] = B[i][j];
      u[i] = U[i][j];
      j -= m[i] * c[i];
   }

   printf("\n+++ Part 2: Best buying option\n");
   j = 0;
   for (i=0; i<n; ++i) {
      printf("    Machine %3d: %3d copies, cost = %6d  ", i, m[i], m[i] * c[i]);
      printf("[Maintenance%sneeded]\n", (u[i]) ? " " : " not ");
      j += m[i] * c[i];
   }
   printf("--- Total buying cost             = %6d\n", j);
   printf("--- Expected total profit         = %15.8lf\n", T[n-1][C]);

   for (i=0; i<n; ++i) {
      free(B[i]);
      free(T[i]);
   }
   free(m);
   free(u);
   free(B);
   free(T);
}

int main ( int argc, char *argv[] )
{
   int n;
   int *c, C;
   int *s, *t, *r;
   double *p, *q;

   srand((unsigned int)time(NULL));
   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("n                    : %d\n", n);
   c = (int *)malloc(n * sizeof(int));
   s = (int *)malloc(n * sizeof(int));
   t = (int *)malloc(n * sizeof(int));
   r = (int *)malloc(n * sizeof(int));
   p = (double *)malloc(n * sizeof(double));
   q = (double *)malloc(n * sizeof(double));
   C = genparams(n,c,s,t,r,p,q);

   optimalbuy1(n,C,c,s,t,p);

   optimalbuy2(n,C,c,s,t,r,p,q);

   exit(0);
}