Eserciti galattici

di

Fase Territoriale 2011

L’esercito della Signoria e riuscito a costruire un’arma segreta: il temibile Sarcofago Nero.

Esso legge una parola segreta S costituita da lettere minuscole dell’alfabeto: a, b, c, …, z (ogni lettera può comparire zero, una o più volte).

Il Sarcofago Nero può assumere N configurazioni al suo interno, numerate da 1 a N.
La parola segreta S viene accettata se raggiunge la configurazione finale (avente numero N) a partire dalla configurazione iniziale (avente numero 1) dopo aver letto tutte le lettere in S una alla volta.
Per ogni configurazione I del Sarcofago Nero, la tripletta (I, J, c) indica che la lettera c lo fa transitare dalla configurazione I alla configurazione J.

L’esercito rivale ha carpito una parola segreta S, ma non sa se è quella del Sarcofago Nero.
Il tuo compito è quello di trovare la configurazione interna Q che esso raggiunge, dopo aver letto S, a partire dalla configurazione iniziale.

Dati di input

Il file input.txt e composto da M+2 righe.

  • La prima riga contiene tre interi positivi separati da uno spazio, che rappresentano il numero M delle triplette, il numero N di configurazioni e il numero K di lettere nella sequenza S.
  • La seconda riga contiene K lettere separate da uno spazio, le quali formano la sequenza S.
  • Ciascuna delle rimanenti M righe contiene due interi positivi I e J e una lettera c, separati da una spazio, che rappresentano la tripletta (I, J, c) per la transizione del Sarcofago Nero.

Dati di output

Il file output.txt è composto da una sola riga contenente il numero Q della configurazione raggiunta dal Sarcofago Nero a partire dalla sua configurazione iniziale (avente numero 1), dopo aver letto tutta la sequenza S.

Assunzioni

  • 2 ≤ M ≤ 100
  • 2 ≤ N ≤ 100
  • 2 ≤ K ≤ 10
  • 1 ≤ Q ≤ N.

Esempi di input/output

input.txt output.txt
5 3 6
a a a b a b
1 3 a
1 2 b
2 1 a
3 2 b
3 3 a		 2

Note

  1. Se il Sarcofago Nero si trova nella configurazione I e arriva la lettera c, viene garantita l’esistenza della tripletta (I, J, c) per una qualche configurazione J.
  2. Per completare la storia, chiaramente S e una parola segreta se Q=N, altrimenti non lo è.
    Ai fini della risoluzione corretta dell’esercizio, è sufficiente restituire il valore di Q.
/*
	www.valcon.it
	OII 2011 - Fase territoriale - Eserciti galattici
*/
#include
#include

using namespace std;

#define MMAX 100
#define NMAX 100
#define KMAX 10

int  transizioni[NMAX+1][26];
char S[KMAX+1];

int main()
{
	int  M,      // numero transizioni
	     N,      // numero stati
		 K,      // lunghezza della sequenza
		 Q;      // stato
	int  I, J;   // input delle triple
	char c;      //

	ifstream fin ( "input.txt");
	ofstream fout("output.txt");

	fin >> M >> N >> K;						
	for(int i=0; i < K; i++)
		fin >> S[i];	
	for(int i=0; i < M; i++)
	{
		fin >> I >> J >> c;	
		transizioni[I][c-'a']=J;
    }
    
    Q=1;
    for(int i=0; i < K; i++)
    	Q=transizioni[Q][S[i]-'a'];

	fout << Q;
    return 0;
}