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
#include
using namespace std; int main(){ ifstream fLegggi("input.txt"); int M, N; fLegggi>>N; fLegggi>>M; if (M
>primo; fLegggi>>secondo; cout<<"\n"<
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<
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