Olimpiadi di Informatica - Selezione Regionale 2006 problema Le pesate di Bilancino (BILANCINO) - livello difficoltà 2 soluzione in C++ proposta da Paola Masin

/* Selezione Regionale 2006 - Le pesate di Bilancino (BILANCINO) Difficoltà D = 3 Descrizione del problema Bilancino è un bambino con una passione maniacale, quella di mettere gli oggetti in ordine crescente di peso. I suoi genitori posseggono un'antica e rara bilancia con due bracci uguali: posti due oggetti, uno per braccio, la bilancia permette di stabilire quale dei due oggetti è più pesante, ma non permette di trovarne il peso assoluto. Oggi Bilancino vuole mettere in ordine crescente di peso N oggetti e, a tale scopo, ha già effettuato una serie di M pesate, trascrivendone i risultati. Infatti, numerati tali oggetti da 1 a N, egli ha pesato M coppie di oggetti distinti x e y, dove 1 <= x, y <= N, scrivendo i due interi x e y in questo ordine su una riga per indicare che x è più leggero di y e, invece, scrivendo y e x in quest'ordine per indicare che y è più leggero di x. Da notare che non esistono due oggetti con lo stesso peso (siano essi stati pesati o meno da Bilancino) e che la stessa coppia di oggetti non può essere pesata più di una volta. Esaminate le M pesate finora eseguite da Bilancino e aiutatelo a decidere quale, tra le seguenti alternative, consente di stabilire l'ordine crescente di peso tra gli N oggetti: * le M pesate sono sufficienti; * è necessaria un'ulteriore pesata; * sono necessarie due o più pesate. Dati di input Il file input.txt è composto da M+1 righe. La prima riga contiene due interi positivi separati da uno spazio: il primo intero rappresenta il numero N di oggetti da ordinare in base al peso mentre il secondo intero rappresenta il numero M di pesate effettuate da Bilancino. Le successive M righe contengono coppie di interi positivi: la j-esima di tali righe è composta da due interi distinti a e b separati da uno spazio, a rappresentare la j-esima pesata effettuata da Bilancino, in cui egli scopre che l'oggetto a è più leggero dell'oggetto b (dove 1 <= j <= M e 1 <= a, b <= N). Da notare che la stessa pesata non può apparire in più di una riga. Dati di output Il file output.txt è composto da una riga contenente un solo intero come dalla seguente tabella. 0 : nessuna ulteriore pesata è necessaria per stabilire l'ordine crescente di tutti gli oggetti. 1 : serve e basta un'ulteriore pesata per stabilire l'ordine crescente di tutti gli oggetti. 2 : due o più pesate sono ulteriormente necessarie per stabilire l'ordine crescente di tutti gli oggetti. Assunzioni: * 1 < N < 100. * 1 <= M <= N(N-1)/2. * I dati in input.txt garantiscono sempre che esiste almeno un ordinamento degli oggetti compatibile con tutte le pesate trascritte da Bilancino. Esempi di input/output +---------+----------+ +---------+----------+ +---------+----------+ |input.txt|output.txt| |input.txt|output.txt| |input.txt|output.txt| +---------+----------+ +---------+----------+ +---------+----------+ | 3 2 | 0 | | 4 4 | 1 | | 4 3 | 2 | | 1 2 | | | 2 3 | | | 2 3 | | | 3 1 | | | 1 4 | | | 1 4 | | +---------+----------+ | 1 3 | | | 2 1 | | | 2 1 | | +---------+----------+ +---------+----------+ Note: un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio rilevante. ----------------------------------------------------------------------------*/ /* Selezione Regionale 2006 - BILANCINO - soluzione di Paola Masin La soluzione si basa sulla proprietà transitiva: se A<B e B<C, allora A<C. Costruisco una matrice di interi: su ciascuna riga metto 1 se l'elemento in colonna è maggiore dell'elemento di riga, nella colonna 0 conto quanti sono gli elementi più grandi; se nella colonna 0 ci saranno tutti i valori da 0 a N-1 scrivo in output 0; se manca un valore metto 1 altrimenti 2; la riga 0 la uso per verificare se ho pesato almeno una volta tutti gli oggetti; posso già scrivere 2 sull'output se ho meno di n-1 pesate o se non ho pesato mai un oggetto */ #include <fstream> #include <iostream> using namespace std; int main(){ ifstream fLegggi("input.txt"); int M, N; fLegggi>>N; fLegggi>>M; if (M<N-1) { fLegggi.close(); ofstream fScrivi("output.txt"); fScrivi<< 2; fScrivi.close(); return 0; } int row,col, primo, secondo, risultato; int minoreDi[N+1][N+1]; // nella colonna 0 il numero di elementi maggiori // nella riga 0 per controllare se sono stati pesati tutti for (row=0;row<=N;row++) { //inizializzo la matrice a 0 for (col=0;col<=N;col++) minoreDi[row][col]=0; } for (row=1; row<=M; row++) { //carico i dati delle pesate fLegggi>>primo; fLegggi>>secondo; cout<<"\n"<<primo<<" "<<secondo; minoreDi[primo][secondo]=1; minoreDi[0][primo]++; //ho pesato l'oggetto primo minoreDi[0][secondo]++;//ho pesato l'oggetto secondo minoreDi[primo][0]++; //l'oggetto primo ha un elemento più grande in più } fLegggi.close(); for (col=1; col<=N; col++) {//l'elemento in posizione 0 non conta if (minoreDi[0][col]==0){//allora non ho pesato l'oggetto!!! ofstream fScrivi("output.txt"); fScrivi<< 2; fScrivi.close(); return 0; } }//non ho pesato un oggetto //adesso incomincia il vero calcolo for ( row=1 ; row<=N; row++) { for (col=1; col<=N; col++) { if (row!=col) // la digonale non conta { if (minoreDi[row][col]==1 && minoreDi[col][0]>0) { for (int j=1;j<=N;j++) { if (minoreDi[col][j]==1 && minoreDi[row][j]==0) { minoreDi[row][j]=1; //la proprietà transitiva... minoreDi[row][0]++; //ne ho un altro più grande } } } } } } for (row=0;row<=N;row++) { //vediamo come siamo messi cout<<"\n"; for (col=0;col<=N;col++) cout<<minoreDi[row][col]<<" "; } int valoreEsistente[N]; // devo sapere chi ha N-1 elementi pù grandi ed N-2 ed N-3... fino a 0 // e l'informazione si trova sulla colonna 0 for (row=0;row<N;row++) valoreEsistente[row]=0; for (row=0;row<N;row++) valoreEsistente[minoreDi[row+1][0]]++; risultato=0; int dubbio=0; for (row=0;row<N;row++) if (valoreEsistente[row]==1) risultato++; else if (valoreEsistente[row]>2||(valoreEsistente[row]==2 && dubbio ==1)) { ofstream fScrivi("output.txt"); fScrivi<< 2; fScrivi.close(); return 0; } else { // non finito: devo vedere se c'e' un elemento piu' piccolo //in comune immediatamente precedente alla prossima } if (risultato==N-1) risultato=0; else risultato=1; // risultato=M*N %3; //prima di finire intanto ci provavo così (NON con rand).. ofstream fScrivi("output.txt"); fScrivi<< risultato; fScrivi.close(); return 0; }

Testo del problema