Cod sursa(job #107822)

Utilizator FlorianFlorian Marcu Florian Data 20 noiembrie 2007 15:34:00
Problema Stramosi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#define Max 250003
FILE*f=fopen("stramosi.in","r");
FILE*g=fopen("stramosi.out","w");
long a[Max],m,n,q,b[17][Max];;
void read()
	{
	fscanf(f,"%ld %ld",&n,&m);
	for(int i=1;i<=n;++i) fscanf(f,"%ld",&a[i]);
	}
long stramos(long p, long x, long q)   // (3,1,9)
	{
	long k,sol;
	k=1<<x;
	if(x==0) return a[q];
	else sol=b[x][q];
	while(k<p)
		{
		sol=a[sol];
		++k;
		}
	return sol;

	}
void precalc()
	{
	int i,j,k=2;
	for(i=1;i<=n;++i)
		b[1][i]=a[a[i]];
	while(1<<k<=n)
		{
		for(i=1;i<=n;++i) b[k][i]=b[k-1][b[k-1][i]];
		++k;
		}
	}
long cauta(long p)
	{
	long k=1;
	while((1<<k)<=p) k++;
	return k-1;
	}
long solve(long p, long q)
	{
	long sol,x;
	x=cauta(p);
	sol=stramos(p,x,q);
	return sol;
	}
int main()
	{
	long i,p;
	long sol;
	read();
	precalc();
	for(i=1;i<=m;++i)
		{
		fscanf(f,"%ld %ld",&q,&p);
		sol=solve(p,q);
		fprintf(g,"%ld\n",sol);
		}
	return 0;
	}