Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Delphi - Problema - Programma di un corso di I°anno di programmazione
Forum - Delphi - Problema - Programma di un corso di I°anno di programmazione

Avatar
FranCich (Normal User)
Newbie


Messaggi: 9
Iscritto: 09/06/2008

Segnala al moderatore
Postato alle 20:08
Lunedì, 09/06/2008
Aiuto!!! ho un esercizio di programmazione sui grafi.
Il problema è intitolato "IL CHIMICO".

TESTO DEL PROBLEMA:
Il chimico Alferedo produce nel suo laboratorio due sostanze 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à di 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 seguire una sola delle tre azioni: (i) versare l’Aminozalina fino al riempimento del contenitore; (ii) versare Brinofulo fino al riempimento del contenitore; (iii) 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  Brinofulo smaltiti nel corrispondente contenitore. Si noti che ogni riga deve contenere uno zero nei casi (i) e (ii) descritti sopra, ed e zeri nel caso (iii).

Assunzioni
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 di input/output
File input.txt
20 25 7
1
13
4
5
8
2
12


File output.txt
1 0
0 13
4 0
5 0
8 0
2 0
0 12

Esempio2
File input.txt
70 3000 5
100
1000
50
2000
20

File output.txt
0 0
0 1000
50 0
0 2000
20 0



secondo me il problema dovrebbe essere risolto con i grafi (utilizzando la BFS con qualche modifica).

Spero che qualcino mi possa aiutare!!!
Vi ringrazio in anticipo per un vostro aiuto.

Ultima modifica effettuata da FranCich il 13/06/2008 alle 13:41
PM Quote
Avatar
FranCich (Normal User)
Newbie


Messaggi: 9
Iscritto: 09/06/2008

Segnala al moderatore
Postato alle 23:46
Lunedì, 09/06/2008
Esempi di input/output
File input.txt  
20 25 7          
1                
13              
4                
5                
8                
2                
12


File output.txt
1 0
0 13
4 0
5 0
8 0
2 0
0 12

Esempio2
File input.txt  
70 3000 5        
100              
1000            
50              
2000            
20

File output.txt
0 0
0 1000
50 0
0 2000
20 0

Ultima modifica effettuata da FranCich il 09/06/2008 alle 23:50
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 23:49
Lunedì, 09/06/2008
Ma lol, reciclano i testi dalle olimpiadi di informatica... comunque hai provato a scrivere una bozza? Dove esattamente ti blocchi?


Il mio blog: https://piero.dev
PM Quote
Avatar
FranCich (Normal User)
Newbie


Messaggi: 9
Iscritto: 09/06/2008

Segnala al moderatore
Postato alle 12:25
Martedì, 10/06/2008
il mio problema nasce proprio alla base... che tipo di struttura di grafo devo utilizzare? orientato/non orientato? completo/sparso?... come lo dichiaro (con l'array delle adiacenze o con la matrice delle adiacenze)???

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 19:26
Martedì, 10/06/2008
Io ricordo di averlo risolto in C++ (nei casi di esempio l'output elaborato dal programma era corretto, ma ciò vuol dire che la mia soluzione sia stata corretta al 100%) e non usavo i grafi.

Vedi se ti è d'aiuto:

Codice sorgente - presumibilmente C++

  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. #define MAX 100
  5.  
  6. using namespace std;
  7. int a,b;
  8. int n;
  9. int cont[MAX];
  10. int resa[MAX];
  11. int resb[MAX];
  12. bool selected[MAX];
  13.  
  14. int maxIndex(){
  15.    int max = cont[0];
  16.    int ind = 0;
  17.    for (int c = 0; c<n; c++){
  18.      if (cont[c] > max && !selected[c]){
  19.                   max = cont[c];
  20.                   ind = c;
  21.      }
  22.    }
  23.    selected[ind] = true;
  24.    return ind;
  25. }
  26.  
  27. int minIndex(){
  28.    int min = 0xFFFF;
  29.    int ind = -1;
  30.    for (int c = 0; c<n; c++){
  31.      if (cont[c] < min && !selected[c]){
  32.                   min = cont[c];
  33.                   ind = c;
  34.      }
  35.    }
  36.    selected[ind] = true;
  37.    return ind;
  38. }
  39.  
  40. int main(){
  41. int c;
  42.  
  43.   ifstream f("input.txt");
  44.  
  45.   f >> a;
  46.   f >> b;
  47.   f >> n;
  48.  
  49.   for (c = 0; c<n; c++) f >> cont[c];
  50.   for (c = 0; c<n; c++) selected[c] = false;
  51.  
  52.   while(b > 0){
  53.      int indx = maxIndex();
  54.      if (b >= cont[indx]){
  55.             resb[indx] = cont[indx];
  56.             b -= cont[indx];
  57.      }    
  58.   }
  59.  
  60.   while(a > 0){
  61.      int indx = minIndex();
  62.      if (a >= cont[indx]){
  63.             resa[indx] = cont[indx];
  64.             a -= cont[indx];
  65.      }  
  66.   }
  67.  
  68.  
  69.   for (c=0; c<n; c++) cout << resa[c] << " " << resb[c] << endl;    
  70.  
  71.   system("pause");
  72.    
  73.  
  74.   return 0;  
  75. }



Il mio blog: https://piero.dev
PM Quote
Avatar
FranCich (Normal User)
Newbie


Messaggi: 9
Iscritto: 09/06/2008

Segnala al moderatore
Postato alle 0:27
Mercoledì, 11/06/2008
Mi dispiace... ma questo linguaggio non lo capisco (purtroppo sino ad ora ho lavorato solo con il delphi7) :(
Mica mi potresti spiegare quest'algoritmo? (e che tipo di struttura hai usato?)

PM Quote