#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int leggiFile(int **p_freccie);
int calcolaScambi(int *freccie, int delimS, int delimD);
int BottomUp(int N, int *freccia, FILE* fp);
void display(int** freccie, int **s, int delimS, int delimD, FILE* fp);
void allocaMatrici(int ***p_matr, int ***p_s, int N);



int main(){

     FILE *fp = fopen("output.txt", "w");
    int nFreccie, *freccie, res;

    nFreccie = leggiFile(&freccie);

    res = BottomUp(nFreccie, freccie, fp);

    fprintf(fp, "\n\n in totale sono state invertite: %d freccie\n\n", res);
}

int leggiFile(int **p_freccie){

   FILE *fpx = fopen("input.txt", "r");
   int nFreccie, i;
   int *tmp;

   fscanf(fpx,"%d",&nFreccie);
   tmp = malloc(nFreccie * sizeof(int));

   for(i=0;i<nFreccie;i++)
    fscanf(fpx,"%d",&tmp[i]);

    *p_freccie=tmp;
    return nFreccie;
}

void stampaFreccie(int *freccie, int delimS, int delimD, FILE* fp){

   int k, i;

   k = (delimD - delimS+1)/2;

   for(i=delimS;i<k+delimS;i++){
        if(freccie[i]==1)
          fprintf(fp,"%d ", i);
   }
   for(i=k+delimS;i<=delimD;i++){
        if(freccie[i]==0)
          fprintf(fp,"%d ", i);
   }
   return;
}

int calcolaScambi(int *freccie, int delimS, int delimD){

   int k, i, scambi=0;

   k = (delimD - delimS+1)/2;

   for(i=delimS;i<k+delimS;i++){
        if(freccie[i]==1)
          scambi++;
   }
   for(i=k+delimS;i<=delimD;i++){
        if(freccie[i]==0)
          scambi++;
   }
   return scambi;
}

void display(int** freccie, int **s, int delimS, int delimD, FILE *fp){

   if(s[delimS][delimD] == 0){
    stampaFreccie(freccie, delimS, delimD, fp);
    return;
   }
   else{
    display(freccie, s, delimS, s[delimS][delimD], fp);
    display(freccie, s, s[delimS][delimD]+1, delimD, fp);
    return;
   }
}

void allocaMatrici(int ***p_matr, int ***p_s, int N){

   int **tmp1,**tmp2;
   int i;

   tmp1 = malloc(N * sizeof(int*));
   tmp2 = malloc(N * sizeof(int*));
   for(i=0;i<N;i++){
     tmp1[i] = malloc(N * sizeof(int));
     tmp2[i] = malloc(N * sizeof(int));
   }

   *p_matr=tmp1;
   *p_s=tmp2;
}

int BottomUp(int N, int *freccie, FILE *fp){


   int **matr, **s, l, j, i, q, c, min, k;

   allocaMatrici(&matr, &s , N);

   for (l = 1; l < N; l=l+2)
     for (i = 0, j=l; j < N; i=i+2, j=j+2) {
            fprintf(fp,"calcolo scambi sul vettore da (%d,%d) (compresi)\n", i, j);
         q = calcolaScambi(freccie, i, j);
         fprintf(fp,"considerando tutto il vettore sono necessari %d scambi\n", q);

         min=INT_MAX;

         if( j-i != 1)
         for(k=i+1;k<j;k=k+2){
            c = matr[i][k] + matr[k+1][j];
            fprintf(fp,"(solo memorizzati) spezzando il vettore in (%d,%d) e (%d,%d) sono necessari %d scambi \n", 0,k,k+1,j, c);
            if(c<min){
                min=c;
                s[i][j]=k;
            }
          }

         if(min<q)
            matr[i][j] = min;
         else{
            matr[i][j]=q;
            s[i][j]= 0;
         }
         fprintf(fp, "\n\n\n");
       }

      fprintf(fp,"Le posizioni delle freccie da invertire sono: ");
      display(freccie, s, 0, N-1, fp);

      return(matr[0][N-1]);
}