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


void ordena_decrescente(int *vetor, int tamanho);
void insertion_sort(int *vetor, int tamanho);
void merge_sort(int *vetor, int tamanho);
void merge(int *vetor, int *esquerda, int contEsquerda, int *direita, int contDireita);
void metodo_guloso(int *vetor,int tamanho);
void mostrar_vetor(int *vetor,int tamanho);
int programacao_dinamica(int *vetor,int tamanho);

int main(int argc, char *argv [ ] ){
    /* Criando variaveis do sistema*/
    int tamanho,respDinamica;
    FILE *arq;

    /* Abrindo arquivo para leitura*/
    arq = fopen(argv[1],"r");

    /* Verificando se o arquivo existe, se não existir é emitida uma mensagem de erro caso contrário lemos o arquivo*/
    if(arq == NULL){
        printf("Erro, nao foi possivel abrir o arquivo\n");
    }
    else{
        /* Instanciando a variavei tamanho com as informações do arquivo */
        fscanf(arq,"%d",&tamanho);
        int i,vetor[tamanho];
        /*Criando e preenchendo o vetor com os valores do arquivo */
        for(i=0; i< tamanho; i++){
            fscanf(arq,"%d",&vetor[i]);
        }

        fclose(arq);
        /*Ordena o vetor em ordem decrescente de valores inteiros*/


        /*Método guloso*/
        printf("Solucao do problema pelo algoritmo guloso:\n\n");
        ordena_decrescente(vetor,tamanho);
        metodo_guloso(vetor,tamanho);
        printf("\n\n-----------------------------------------\n\n");
        /*Método de programação dinâmica*/
        printf("Solucao do problema pelo algoritmo com programacao dinamina:\n\n");
        respDinamica = programacao_dinamica(vetor,tamanho);
        if(respDinamica==0){
            printf("Achou!!");
        }else{
            printf("Nao achou!!");
        }
    }
    return 0;
}

void metodo_guloso(int *vetor,int tamanho){
    int somaA, somaB,i,j,k;
    somaA=somaB=j=k=0;

    /*Caso o tamanho do vetor original tenha tamanho 2 basta criar um vetor com a posicao 0 do vetor original e outro com a posicao 1
    e a soma de cada vetor novo é o valor do elemento contido nele*/
    if(tamanho == 2){
        int vetorA,vetorB;
        vetorA=somaA=vetor[0];
        vetorB=somaB=vetor[1];
        printf("Vetor original tem tamanho 2\n");
        printf("Soma do vetor A = %d \nVetorA = %d\n",vetorA,vetorA);
        printf("Soma do vetor B = %d \nVetorB = %d\n",vetorB,vetorB);
    }else if(tamanho>2){
        /*Cria-se os vetores A e B que terão a  resposta final*/
        int vetorA[tamanho],vetorB[tamanho];
        /*Varrer o vetor original ordenado em ordem decrescente*/
        for(i=0;i<tamanho;i++){
            /*Caso a soma do vetor A novo seja menor ou igual que a do vetor B o elemento do vetor
             original correspondente ao indice i será adicionado a ele e somado em sua soma, esse elemento
              será adicionado a B e somado a sua soma caso a soma de B seja menor q a de A*/
            if(somaA<=somaB){
                vetorA[j]=vetor[i];
                somaA = somaA + vetor[i];
                j++;
            }else{
                vetorB[k]=vetor[i];
                somaB = somaB + vetor[i];
                k++;
            }
        }
        printf("Soma do vetor A = %d\nVetorA = ",somaA);
        mostrar_vetor(vetorA,j);
        printf("\nSoma do vetor B = %d\nVetorB = ",somaB);
        mostrar_vetor(vetorB,k);
    }
}

int programacao_dinamica(int *vetor,int tamanho){
    int i,j, somaTotal,metade;
    somaTotal = 0;

    for(i=0;i<tamanho;i++){
        somaTotal += vetor[i];
    }

    if(somaTotal%2 !=0){
        return 1;
    }

    metade = somaTotal/2;

    int matriz[metade+1][tamanho+1];
    // 0 é true e 1 é false
    for(i=0;i<=tamanho;i++){
        matriz[0][i] = 0;
    }
    for(i=1;i<=metade;i++){
        matriz[i][0] = 1;
    }

    for(i=1;i<=metade;i++){
        for(j=1;j<=tamanho;j++){
            matriz[i][j] = matriz[i][j-1];
            if(i>=vetor[j-1]){
                if(matriz[i][j-1] == 0 || matriz[i-vetor[j-1]][j-1] == 0){
                    matriz[i][j] = 0;
                    //printf("Entrou aqui\n");
                }

                //matriz[i][j] ==matriz[i][j] || matriz[i-vetor[j-1]][j-1];
            }
        }

    }
    /*1
    printf("\n");
    for(i=0;i<metade;i++){
        for(j=0;j<tamanho;j++){
            printf("%d",matriz[i][j]);
        }
        printf("\n");
    }
    */

    return matriz[metade][tamanho];
}


void mostrar_vetor(int *vetor,int tamanho){
    int i;
    printf("[");
    for(i=0;i<tamanho;i++){
        if(i==tamanho-1){
            printf("%d]\n",vetor[i]);
        }else{
            printf("%d,",vetor[i]);
        }
    }
}

void ordena_decrescente(int *vetor, int tamanho){
    int i,j,aux;
    /*Para o caso da entrada ter um numero de valores inteiro menores que cinco mil o algoritmo ordena pelo insertion sort,
    caso contrario o algoritmo ordena o vetor pelo merge sort*/
    if(tamanho<5000){
        insertion_sort(vetor,tamanho);
    }else{
        merge_sort(vetor,tamanho);
    }
    /*Após a ordenação o algoritmo coloca o vetor ordenado em ordem decrescente usando um passo O(n)*/
    j=tamanho-1;
    for(i=0;i<tamanho/2;i++){
        aux = vetor[i];
        vetor[i]=vetor[j];
        vetor[j]=aux;
        j--;
    }
}
void insertion_sort(int *vetor, int tamanho){
    int i, j, menor_atual;

    for(i = 1; i<tamanho; i++){
        menor_atual = vetor[i];
        for(j = i-1; (j>=0)&&(menor_atual < vetor[j]); j--){
            vetor[j+1] = vetor[j];
        }
        vetor[j+1] = menor_atual;
    }
}

void merge(int *vetor, int *esquerda, int contEsquerda, int *direita, int contDireita){
    int i, j, k;
    i= j= k= 0;

    while(i<contEsquerda && j< contDireita){
        if(esquerda[i] < direita[j]){
            vetor[k++] = esquerda[i++];
        }else{
            vetor[k++] = direita[j++];
        }
    }

    while(i<contEsquerda){
        vetor[k++] = esquerda[i++];
    }

    while(j<contDireita){
        vetor[k++] = direita[j++];
    }
}

void merge_sort(int *vetor, int tamanho){
    int *esquerda, *direita, i, meio;
    if(tamanho <2){
        return;
    }

    meio =  tamanho/2;

    esquerda = (int *) malloc(sizeof(int) * (meio));
    direita = (int *) malloc(sizeof(int) * (tamanho - meio));

    for(i = 0; i< meio; i++){
        esquerda[i] =
        vetor[i];
    }

    for(i=meio; i<tamanho; i++){
        direita[i - meio] = vetor[i];
    }

    merge_sort(esquerda,meio);
    merge_sort(direita, (tamanho-meio));
    merge(vetor, esquerda, meio, direita, (tamanho-meio));

    free(esquerda);
    free(direita);
}