Olimpiadi di Informatica - Selezione Regionale 2007
problema
Torero Escamillo
- livello difficoltà 2
soluzione in C++ proposta da ...
/* Selezione Regionale 2007 - Torero Escamillo (TORERO) - Difficoltà D = 2 Descrizione del problema Il celebre torero Escamillo deve indossare il proprio costume prima di entrare nell'arena. Egli è costretto a rispettare un dato numero di precedenze, indossando certi indumenti prima di altri, mentre alcuni indumenti possono essere liberamente indossati in un ordine qualsiasi. Per esempio, le "medias" (calze) vanno indossate prima delle "zapatillas" (scarpe), ma non vi è alcun vincolo sull'ordine con cui indossare la "chaquetilla" (giacca) e la "montera" (cappello). Il costume di Escamillo è particolarmente raffinato ed elaborato e si compone di N indumenti. Sfortunatamente, Carmen non ha ancora consegnato uno degli N indumenti necessari alla vestizione di Escamillo. Aiutalo a vestirsi il più possibile, calcolando il massimo numero di indumenti che può indossare in attesa che Carmen gli consegni l'indumento mancante. Dati di input Il file input.txt contiene nella prima riga una tripla di interi, separati da uno spazio: l'intero positivo N che indica il numero di indumenti per la vestizione di Escamillo, dove gli indumenti sono numerati da 1 a N; l'intero positivo M che indica il numero di precedenze tra coppie di indumenti da rispettare durante la vestizione; l'intero Q, compreso tra 1 e N, che indica l'indumento non ancora consegnato da Carmen. Ognuna delle successive M righe contiene una coppia di interi, compresi tra 1 e N, separati da uno spazio. Tale coppia di interi I e J rappresenta la precedenza in cui l'indumento numero I deve essere indossato prima dell'indumento numero J. Dati di output Il file output.txt è composto da una riga contenente un solo intero, che rappresenta il massimo numero di indumenti che Escamillo riesce a indossare in attesa dell'indumento Q che Carmen deve ancora consegnargli. Assunzioni * 1 < N < 100000. * 1 < M < 100000. * 1 = Q = N. Esempi di input/output +----------+------------+ |input.txt | output.txt | +----------+------------+ | 4 5 3 | 1 | | 1 3 | | | 1 4 | | | 3 2 | | | 3 4 | | | 4 2 | | +----------+------------+ Note * Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio rilevante. ----------------------------------------------------------------------------*/ // Selezione regionale 2007 - Torero Escamillo (TORERO) - Difficoltà D = 2 #include
using namespace std; int main(){ ifstream input("input.txt"); int n,m,q; input>>n; input>>m; input>>q; int matrice[n][n+1]; for(int i=0;i
>a; input>>b; matrice[a-1][b-1]=1; } input.close(); bool finito=false; while(!finito){ finito=true; for(int i=0;i
Testo del problema