Questo topic e' stato chiuso dal moderatore.
25/10/09 10:32
aazzarone
#include <fstream>
using namespace std;
/* Costanti */
const int MAX_N = 1000000;
const int MAX_K = MAX_N-1;
/* Variabili globali */
int N, K, T;
int adj[MAX_N];
int vetK1[MAX_K]; /* dove si trova l'amico i */
bool vetK2[MAX_K]; /* nella posizione i si trova qualche amico ? */
int vetK3[MAX_K]; /* nella posizione i quale amico si trova?*/
bool madeK[MAX_N]; /* é già stata calcolato precedentemente? */
/* dist1 e dist2 si riferiscono a seconda del ciclo a origini diverse (in questo
* modo evitiamo di creare matrici di grosse dimensioni */
int dist1[MAX_N]; /* la posizione x a quale distanza si trova? */
int dist2[MAX_N]; /* alla distanza x quale posizione del tavolo si trova? */
int sol1[MAX_N]; /* utilizzato nel momento in cui più amici si trovano nello stesso ciclo */
bool sol2[MAX_N]; /* alla fine se sol2[i] == true allora sappiamo che nella posizione i si trova un 'amico */
int main ()
{
/* Variabili di input */
ifstream in ("input.txt");
/* Variabili di output */
ofstream out ("output.txt");
/* Variabili contatore */
int i, j, k, l;
/* Variabili di lavoro */
int a;
/* Lettura file di input */
in >> N >> K >> T;
for (i=0; i<N; i++)
{
in >> adj[i];
adj[i]--;
}
for (i=0; i<K; i++)
{
in >> vetK1[i];
vetK1[i]--; /* consideriamo gli indici a partire da 0 e nn da 1 */
vetK2[vetK1[i]] = true;
vetK3[vetK1[i]] = i;
}
/* Fine lettura file di input */
l = 0;
for (i=0; i<K; i++)
{
if (!madeK[i])
{
k = 0;
dist1[vetK1[i]] = 0;
dist2[0] = vetK1[i];
sol1[0] = vetK1[i];
l = 0;
for (j=adj[vetK1[i]]; j!=vetK1[i]; j=adj[j])
{
dist1[j] = ++k;
dist2[k] = j;
if (vetK2[j])
sol1[++l] = j;
}
/* ... e se due amici si trovassero nello stesso ciclo? */
for (j=0; j<=l; j++)
{
a = (dist1[sol1[j]] + T) % (k+1);
sol2[dist2[a]] = true;
madeK[vetK3[sol1[j]]] = true;
}
}
}
if (sol2[N-1])
{
for (i=N-1; sol2[i]; i--) ;
i++;
}
else
for (i=0; !sol2[i]; i++) ;
/* Stampa le soluzioni */
out << i+1 << endl; /* Ricorda che nel programma gli indici partivano da 0 e non da 1 */
/* Fine programma */
in.close ();
out.close ();
return 0;
}
Ultima modifica effettuata da aazzarone 25/10/09 10:35
aaa
