Olimpiadi di Informatica - Selezione Regionale 2006
problema
Teste di serie (SERIE)
- livello difficoltà 2
soluzione in C++ proposta da Paola Masin
/* Selezione Regionale 2006 - Teste di serie (SERIE) - Difficoltà D = 2 Descrizione del problema Un torneo è composto da K gironi, con N squadre partecipanti in ciascun girone (per un totale di KxN squadre nel torneo). Dopo le eliminatorie, passa soltanto la prima classificata di ogni girone. A ogni squadra è associato un "coefficiente di bravura", ovvero un intero positivo che è tanto maggiore quanto più la squadra è forte. Per rendere più vivace il torneo, gli organizzatori vogliono far gareggiare le squadre più forti tra loro soltanto dopo le eliminatorie: in altre parole, le K squadre con i coefficienti di bravura più alti devono giocare in gironi distinti. Aiutate gli organizzatori a verificare che la composizione del torneo rispetti il loro volere: prese le K squadre con il più alto coefficiente di bravura, ciascun girone deve contenere esattamente una di esse (da notare che due o più squadre possono avere lo stesso coefficiente). Dati di input Il file input.txt è composto da K+1 righe. La prima riga contiene due interi positivi separati da uno spazio: il numero K di gironi e il numero N di squadre per girone. Le successive K righe contengono i coefficienti di bravura delle squadre: la j-esima di tale righe contiene N interi positivi separati da uno spazio che sono i coefficienti di bravura delle N squadre nel j-esimo girone, per 1 <= j <= K. Dati di output Il file output.txt è composto di una riga contenente un solo intero: 1 se il torneo rispetta i vincoli imposti dagli organizzatori, 0 altrimenti. Assunzioni * 1 < N <= 100. * 1 < K <= 100. Esempi di input/output +-------------+------------+ +-------------+------------+ | input.txt | output.txt | | input.txt | output.txt | +-------------+------------+ +-------------+------------+ | 3 4 | 0 | | 3 4 | 1 | | 3 5 7 9 | | | 2 2 2 1 | | | 3 6 78 90 | | | 2 1 3 1 | | | 43 78 71 32 | | | 2 4 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 - Teste di serie (SERIE) - soluzione di Paola Masin #include
using namespace std; int main(){ ifstream fLegggi("input.txt"); ofstream fScrivi("output.txt"); int K, N; fLegggi>>K; fLegggi>>N; int aPosto=1; int primo, secondo; //su ciascun girone mi interessano solo i //due valori maggiori int testeDiSerie[K][2]; //a me basta memorizzare le teste di serie int coeffBravura; int h; for (int row=0; row
>coeffBravura; if ( coeffBravura > primo){ secondo=primo; primo=coeffBravura; } else if ( coeffBravura > secondo){ secondo=coeffBravura; } } testeDiSerie[row][0]=primo; testeDiSerie[row][1]=secondo; h=row-1; while (h>=0&&secondo<=testeDiSerie[h][0]&&primo>=testeDiSerie[h][1])h--; if (h>=0) //significa che un secondo ha un coeff. maggiore //oppure che l'attuale testa di serie e` minore di un secondo { fScrivi<< 0; fScrivi.close(); fLegggi.close(); return 0; } } fScrivi<< 1; fScrivi.close(); fLegggi.close(); return 0; }
Testo del problema