Grand Prix

di

Fase Territoriale 2012

State assistendo a un Gran Premio di Formula 1.
Prima dell’inizio, il tabellone riporta la griglia di partenza, ovvero l’ordine in cui le vetture partiranno dalla linea del traguardo.
Non appena inizia il gran premio, per ogni sorpasso, il tabellone scrive due numeri: quello della vettura che ha effettuato il sorpasso, e quello della vettura che è stata superata.
Il vostro compito è di scrivere un programma che, ricevuti in ingresso l’ordine di partenza e la lista dei sorpassi, calcoli chi ha vinto il gran premio.

Per esempio, considerate il seguente gran premio, con 3 macchine e 4 sorpassi.
L’ordine iniziale di partenza è stato: la vettura numero 2, poi la vettura numero 1 e infine la vettura numero 3.
I sorpassi sono stati, nell’ordine:

  • la numero 3 ha superato la numero 1;
  • la numero 3 ha superato la numero 2;
  • la numero 1 ha superato la numero 2;
  • la numero 2 ha superato la numero 1.

In questo caso, è facile vedere che la vettura numero 3 ha vinto il gran premio.
Come si può notare dall’esempio, i sorpassi avvengono sempre tra due vetture consecutive.

Dati di input

Il file input.txt è composto da 1+N+M righe.
La prima riga contiene due interi positivi separati da uno spazio: N che è il numero di vetture e M che è il numero di sorpassi.
Le successive N righe contengono l’ordine di partenza: per ogni riga c’è un numero intero K che rappresenta una
vettura, con 1 ≤ K ≤ N.
La vettura che parte in i-esima posizione nell’ordine di partenza si trova quindi nella riga (i+1) del file.
Le restanti M righe contengono tutti i sorpassi, nell’ordine in cui sono avvenuti, uno in ogni riga.
Ogni riga contiene due interi separati da uno spazio: A, ovvero il numero della vettura che ha effettuato il sorpasso, e B, ovvero il numero della vettura che ha subito il sorpasso.

Dati di output

Il file di output deve contenere un solo intero: il numero della vettura che ha vinto il gran premio.

Assunzioni

  • 1 ≤ N ≤ 30
  • 1 ≤ M ≤ 100.

Esempio

input.txt output.txt
3 4
2
1
3
3 1
3 2
1 2
2 1		 3
3 6
3
1
2
2 1
1 2
1 3
2 3
2 1
3 1		 2 
/*
	www.valcon.it
	OII 2012 - Fase territoriale - Grand Prix
*/
#include
#include
#define NMAX 30

using namespace std;

int posizione[NMAX+1];       // le posizioni delle vetture

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
	int N,		            	// n. di vetture
	    M;	                	// n. di sorpassi
	fin >> N >> M;
	int K;				    	
	for(int i=1; i <= N; i++)	// ordine di partenza
	{
		fin >> K;
		posizione[K]=i;     	// la vettura K è alla posizione i
	}
		
	int A,B;
	int temp;
	for(int i=1; i <= M; i++)
	{
		fin >> A >> B;			// A sorpassa B
		temp=posizione[A];		// le vetture A e B si scambiano le posizioni
		posizione[A]=posizione[B];
		posizione[B]=temp;
	}
							
	for(int i=1; i <= N; i++)	// chi è arrivato primo?
		if(posizione[i] == 1)
		{
			fout << i;			// la vettura i è prima!
			break;
		}
	
	return 0;
}

Soluzione senza array

/*
	www.valcon.it
	OII 2012 - Fase territoriale - Grand Prix
*/
#include
#include
#define NMAX 30

using namespace std;

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");
	
	int N,		            // n. di vetture
	    M;	                // n. di sorpassi	    
	fin >> N >> M;
	
	int K;				    // ordine di partenza
	fin >> K;				// in prima posizione...
	int primo=K;
							// le altre posizioni non interessano
	for(int i=2; i <= N; i++)
		fin >> K;
		
	int A,B;				// A sorpassa B
	for(int i=1; i <= M; i++)
	{
		fin >> A >> B;
		if(B == primo)		// se A sorpassa il primo...
		{
			primo=A;		// il primo diventa A
		}
	}
	fout << primo;
	return 0;
}