Il nobile chimico

Il nobile chimico Alfredo produce nel suo laboratorio due sostanze liquide potenzialmente inquinanti: l’Aminozalina e il Brinofulo.
A fine giornata le deve smaltire in appositi contenitori, dislocati lungo il tragitto che parte dal laboratorio e arriva alla sua abitazione.

Per limitare le possibilità d’inquinamento, Alfredo deve distribuire l’Aminozalina nel maggior numero possibile di contenitori mentre deve dividere il Brinofulo nel minor numero possibile di contenitori.
Tuttavia Aminozalina e Brinofulo non possono essere assolutamente mescolati nel medesimo contenitore, altrimenti la loro miscela esplode.

Ogni volta che raggiunge un contenitore per lo smaltimento dei liquidi, Alfredo deve eseguire una sola delle tre seguenti azioni:

  1. versare Aminozalina fino al riempimento del contenitore;
  2. versare Brinofulo fino al riempimento del contenitore;
  3. non versare nulla nel contenitore.

Data la quantità A di litri di Aminozalina e la quantità B di litri di Brinofulo da smaltire, e conoscendo l’elenco degli N contenitori (con rispettiva capacità) nell’ordine secondo cui sono incontrati lungo il tragitto dal laboratorio alla sua abitazione, Alfredo deve decidere se e quale sostanza versare in ciascun contenitore.

Dati di input

Il file input.txt contiene nella prima riga gli interi A e B (rispettivamente i litri di Aminozalina e di Brinofulo da smaltire) e il numero N di contenitori disponibili.
Tali valori sono separati da uno spazio.
Nelle successive N righe (usando una riga per ogni contenitore) è contenuto un numero per riga: tali numeri rappresentano le capacità dei singoli contenitori elencati nell’ordine in cui vengono incontrati da Alfredo.

Dati di output

Il file output.txt deve contenere N righe, una per ogni contenitore.
Ogni riga contiene due numeri separati da uno spazio, rispettivamente il numero di litri di Aminozalina e di Brinofulo smaltiti nel corrispondente contenitore.
Si noti che ogni riga deve contenere a seconda dei casi

  1. uno 0
  2. uno 0
  3. due 0.

Assunzioni

  • 1 < A,B < 10000
  • 1 < N < 100
  • Le singole capacità dei contenitori sono degli interi positivi di valore inferiore a 10000.
  • Le capacità dei contenitori sono sicuramente sufficienti per smaltire tutta l’Aminozalina e il Brinofulo prodotti.
  • I dati in input garantiscono l’esistenza di una (e una sola) soluzione ottima, quindi Alfredo ha un unico modo ottimo per smaltire le sostanze.
  • La soluzione ottima prevede che tutti i contenitori utilizzati vengano riempiti completamente (non può succedere che l’Aminozalina o il Brinofulo terminino prima che i contenitori effettivamente usati per lo smaltimento siano tutti completamente riempiti).

Esempi

input.txt output.txt
20 25 7
1
13
4
5
8
2
12
1 0
0 13
4 0
5 0
8 0
2 0
0 12
70 3000 5
100
1000
50
2000
20
0 0
0 1000
50 0
0 2000
20 0

Le assunzioni del problema spingono il risolutore verso l’algoritmo più semplice

  1. ordinare i contenitori per capacità
  2. versare Aminozalina a partire dal contenitore più piccolo
  3. versare Brinofulo a partire dal contenitore più grande
  4. gli eventuali contenitori inutilizzati saranno di capacità intermedia.
#include 
#define NMAX 100

int CONTENITORI[NMAX];        
int ordCONTENITORI[NMAX];  
int quantoA[NMAX];            
int quantoB[NMAX];            

int N,    
    A,
    B;

void SCAMBIA(int *v, int a, int b)
{
    int temp=v[a];
    v[a]=v[b];
    v[b]=temp;
}

void ordina()
{
    for(int i=0; i < N; i++)
       ordCONTENITORI[i]=i;

    for(int i=0; i < N-1; i++)
    {
       int posMinimo=i;
       int minimo=CONTENITORI[ordCONTENITORI[posMinimo]];
       for(int j=i+1; j < N; j++)
       {
          int nuovoMinimo=CONTENITORI[ordCONTENITORI[j]];
          if(nuovoMinimo < minimo)
          {
              minimo=nuovoMinimo;
              posMinimo=j;
          }
       }
       SCAMBIA(ordCONTENITORI, i, posMinimo);          
    }    
}

void versa()
{
    int i=0;                            
    while (A > 0)
    {
         int pos=ordCONTENITORI[i];
         quantoA[pos] = CONTENITORI[pos];
         A -= CONTENITORI[pos];
         i++;
    }
    i=N-1;                              
    while (B > 0)
    {
         int pos=ordCONTENITORI[i];
         quantoB[pos] = CONTENITORI[pos];
         B -= CONTENITORI[pos];
         i--;
    }
}

int main()
{
    FILE *fileIN=fopen("input.txt", "r");
    fscanf(fileIN, "%d %d %d", &A, &B, &N);
    for(int i=0; i < N; i++)
    {
        fscanf(fileIN, "%d", &(CONTENITORI[i]));
        quantoA[i]=0;
        quantoB[i]=0;
    }
    fclose(fileIN);

    ordina();  
    versa();

    FILE *fileOUT;
    fileOUT = fopen("output.txt", "w");
    for(int i=0; i < N; i++)
        fprintf(fileOUT, "%d %dn", quantoA[i], quantoB[i]);
    fclose(fileOUT);
    return 0;
}

Osserva

  1. Non è necessario ordinare preventivamente le capacità dei contenitori ma è sufficiente
    • individuare il contenitore con capacità minima, tra quelli disponibili, prima di versare Aminozalina
    • individuare il contenitore con capacità massima, tra quelli disponibili, prima di versare Brinofulo
  2. L'algoritmo è più intuitivo ma la complessità peggiora...
#include 
#define NMAX 100

int CONTENITORI[NMAX];  
int quantoA[NMAX];          
int quantoB[NMAX];          

int N,    
    A,  
    B;  

void versa()
{
    while (A > 0)            
    {
         int pos=0;
         while(quantoA[pos] != 0)
             pos++;

         for(int j=pos+1; j < N; j++)
             if(quantoA[j] == 0 && CONTENITORI[j] < CONTENITORI[pos])
                 pos=j;
                         
         quantoA[pos] = CONTENITORI[pos];
         A -= CONTENITORI[pos];
    }

    while (B > 0)    
    {
         int pos=0;
         while(quantoA[pos] != 0 || quantoB[pos] != 0)
             pos++;

         for(int j=pos+1; j < N; j++)
             if(quantoA[j] == 0 && quantoB[j] == 0 && CONTENITORI[j] > CONTENITORI[pos])
                 pos=j;
                         
         quantoB[pos] = CONTENITORI[pos];
         B -= CONTENITORI[pos];
    }
}

int main()
{
    FILE *fileIN=fopen("input.txt", "r");
    fscanf(fileIN, "%d %d %d", &A, &B, &N);
    for(int i=0; i < N; i++)
    {
        fscanf(fileIN, "%d", &(CONTENITORI[i]));
        quantoA[i]=0;
        quantoB[i]=0;
    }
    fclose(fileIN);

    versa();
 
    FILE *fileOUT;
    fileOUT = fopen("output.txt", "w");
    for(int i=0; i < N; i++)
        fprintf(fileOUT, "%d %dn", quantoA[i], quantoB[i]);
    fclose(fileOUT);

    return 0;
}