#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include <stddef.h>

// Exercice 1

int monnaie(int s) // Version simple retournant le nombre de pièces et billets sans détails.
{
  int pieces[15] = { 50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };
  int rep = 0;
  for ( int i = 0; i < 15; i++ )
  {
    rep += s / pieces[i];
    s = s%pieces[i];
  };
  assert (s==0);
  return rep;
}

int main1()
{
  int n = 33300;
  printf("Le nombre optimal de pièces et billets pour rendre %d centimes est %d", n, monnaie(n));
}

// Exercice 2

int* activites(int** tab, int taille) // Renvoie un tableau aplati donnant les activités retenues.
{
  if (taille == 0) return NULL;
  int* rep = malloc(2 * taille * sizeof(int));
  rep[0] = tab[0][0];
  rep[1] = tab[0][1];
  int nbr_activites = 1;
  int fin = rep[1];
  for (int i = 1; i < taille; i++)
  {
    if (tab[i][0] >= fin) // > si on exclut qu'une activité ne commence quand une autre se termine
    {
      rep[nbr_activites * 2] = tab[i][0];
      rep[nbr_activites * 2 + 1] = tab[i][1];
      fin = tab[i][1];
      nbr_activites++;
    }
  }
  int* rep_fin = malloc((2 * nbr_activites + 1) * sizeof(int));
  rep_fin[0] = nbr_activites;
  for (int i = 1; i < 2 * nbr_activites + 1; i++) rep_fin[i] = rep[i-1];
  free(rep);
  return rep_fin;
}

int main2()
{
  int** tab = malloc(6 * sizeof(int*));
  tab[0] = malloc(2 * sizeof(int));
  tab[0][0] = 1;
  tab[0][1] = 3;
  tab[1] = malloc(2 * sizeof(int));
  tab[1][0] = 2;
  tab[1][1] = 4;
  tab[2] = malloc(2 * sizeof(int));
  tab[2][0] = 3;
  tab[2][1] = 5;
  tab[3] = malloc(2 * sizeof(int));
  tab[3][0] = 4;
  tab[3][1] = 6;
  tab[4] = malloc(2 * sizeof(int));
  tab[4][0] = 5;
  tab[4][1] = 7;
  tab[5] = malloc(2 * sizeof(int));
  tab[5][0] = 6;
  tab[5][1] = 8;
  int* rep = activites(tab, 6);
  printf("[");
  for (int i = 0; i < rep[0]; i++) printf("(%d, %d) ", rep[2*i+1], rep[2*i+2]);
  printf("]\n");
  free(rep);
  for (int i = 0; i < 6; i++) free(tab[i]);
  free(tab);
  return 0;
}

// Exercice 3

int* allocation_salles(int** tab, int taille) // Renvoie le tableau des numéros de salle pour chaque indice. On suppose les intervalles triés par début croissant.
{
  int* reponse = malloc(taille * sizeof(int));
  bool* dispo = malloc(taille * sizeof(bool));
  for (int i = 0 ; i < taille ; i += 1)
  {
    for (int j = 0 ; j < taille ; j += 1) dispo[j] = true;
    for (int j = 0 ; j < i ; j += 1) // après, la valeur est encore inconnue
    {
      if (tab[j][1] > tab[i][0]) dispo[reponse[j]] = false; // >= si on exclut qu'une activité ne commence dans une salle au moment où une autre s'y termine
    }
    int j = 0;
    while (j < taille && !dispo[j]) j += 1; // aucun risque de dépassement d'après le principe des tiroirs
    reponse[i] = j;
  }
  free(dispo);
  return reponse;
}

int main3()
{
  int** tab = malloc(9 * sizeof(int*)); // Exemple de Centale adapté à C.
  tab[0] = malloc(2 * sizeof(int));
  tab[0][0] = 0;
  tab[0][1] = 2;
  tab[1] = malloc(2 * sizeof(int));
  tab[1][0] = 1;
  tab[1][1] = 4;
  tab[2] = malloc(2 * sizeof(int));
  tab[2][0] = 1;
  tab[2][1] = 5;
  tab[3] = malloc(2 * sizeof(int));
  tab[3][0] = 3;
  tab[3][1] = 7;
  tab[4] = malloc(2 * sizeof(int));
  tab[4][0] = 6;
  tab[4][1] = 9;
  tab[5] = malloc(2 * sizeof(int));
  tab[5][0] = 8;
  tab[5][1] = 11;
  tab[6] = malloc(2 * sizeof(int));
  tab[6][0] = 8;
  tab[6][1] = 13;
  tab[7] = malloc(2 * sizeof(int));
  tab[7][0] = 10;
  tab[7][1] = 14;
  tab[8] = malloc(2 * sizeof(int));
  tab[8][0] = 12;
  tab[8][1] = 15;
  int* rep = allocation_salles(tab, 9);
  for (int i = 0; i < 9; i++) printf("Salle pour l'activité numéro %d : %d.\n", i,  rep[i]);
  free(rep);
  for (int i = 0; i < 9; i++) free(tab[i]);
  free(tab);
  return 0;
}

// Exercice 4

int ppp2(int n)
{
  int rep = 1;
  while (rep < n) rep *= 2;
  return rep;
}

int* aux(int* p, int* q, int tn)
{
  if (tn == 1)
  {
    int* rep = malloc(2 * sizeof(int));
    rep[0] = p[0] * q[0];
    rep[1] = 0;
    return rep;  
  }
  else
  {
    int* p1 = malloc((tn/2) * sizeof(int));
    int* p2 = malloc((tn/2) * sizeof(int));
    int* q1 = malloc((tn/2) * sizeof(int));
    int* q2 = malloc((tn/2) * sizeof(int));
    for (int i = 0 ; i < tn/2 ; i += 1)
    {
      p2[i] = p[i];
      q2[i] = q[i];
      p1[i] = p[i + tn/2];
      q1[i] = q[i + tn/2];
    }
    int* p1q1 = aux(p1, q1, tn/2);
    int* p2q2 = aux(p2, q2, tn/2);
    for (int i = 0 ; i < tn/2 ; i += 1)
    {
      p2[i] += p1[i];
      q2[i] += q1[i];
    }
    int* p12q12 = aux(p2, q2, tn/2);
    int* rep = malloc(2*tn * sizeof(int));
    for (int i = 0 ; i < 2*tn ; i += 1)
    {
      rep[i] = 0;
    }
    for (int i = 0 ; i < tn ; i += 1)
    {
      rep[i] += p2q2[i];
      rep[i + tn/2] += p12q12[i] - p1q1[i] - p2q2[i];
      rep[i + tn] += p1q1[i];
    }
    free(p1);
    free(p2);
    free(q1);
    free(q2);
    free(p1q1);
    free(p2q2);
    free(p12q12);
    return rep;
  }
}

int* karatsuba(int* p, int* q, int taille) // On suppose p et q de même taille, et on utilise le type int ici
{
  int n = ppp2(taille);
  int* pn = malloc(n * sizeof(int));
  int* qn = malloc(n * sizeof(int));
  for (int i = 0 ; i < taille ; i += 1)
  {
    pn[i] = p[i];
    qn[i] = q[i];
  }
  for (int i = taille ; i < n ; i += 1)
  {
    pn[i] = 0;
    qn[i] = 0;
  }
  int* rep = aux(pn, qn, n);
  int vraie_fin = 2*n-1;
  while (vraie_fin > 0 && rep[vraie_fin] == 0) vraie_fin -= 1;
  int* vraie_rep = malloc((vraie_fin+1) * sizeof(int));
  for (int i = 0 ; i <= vraie_fin ; i += 1) vraie_rep[i] = rep[i];
  free(pn);
  free(qn);
  free(rep);
  return vraie_rep;
}

int main4()
{
  int p[4] = { 1, 2, 1 };
  int q[4] = { 1, 3, 3, 1 };
  int* pq = karatsuba(p, q, 4);
  for (int i = 5 ; i >= 0 ; i -= 1)
  {
    printf("%d X^%d", pq[i], i);
    if (i > 0) printf(" +");
  }
  printf("\n");
  free(pq);
}

// Exercices 5 à 7 en OCaml

// Fonction main

int main()
{
  int zero = main1();
  exit(zero);
}