Решение задачи Найди шарик с Codeforces

Без пояснения   Просмотров: 26


Петя и Вася играют в следующую игру. У Пети есть n непрозрачных стаканов, стоящих в ряд. Места, на которых стоят стаканы, пронумерованы целыми числами от 1 до n слева направо. Обратите внимание, что пронумерованы места, а не сами стаканы.

Сначала Петя кладет шарик под стакан, стоящий на месте номер s. Затем Петя совершает некоторое (возможно, нулевое) количество операций перемешивания. Одна операция перемешивания состоит в перемещении стакана на первом месте на место p 1, стакана на втором месте на место p 2 и так далее. То есть стакан с места i переместится на место p i. Считайте, что все перемещения стаканов происходят одновременно. Во время перемешивания стаканов шарик не перекатывается из стакана в стакан, он перемещается вместе с тем стаканом, в который его положили изначально.

После всех операций перемешивания Петя показывает Васе, что шарик оказался на месте t. Задача Васи состоит в том, чтобы сказать, какое минимальное количество операций перемешивания совершил Петя, или определить, что Петя совершил ошибку, и шарик не мог попасть из позиции s в позицию t.

Код

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,s,t;
	cin>>n>>s>>t;
	int p[n+1];
	for(int i=1; i<=n; i++)
		cin>>p[i];
	int k;
	for(k=0 ; s!=t&&p[s]!=0 ; k++)
	{
		int temp=p[s];
		p[s]=0;
		s=temp; 
	}
	if(s==t)
		cout<<k;
	else
		cout<<-1;
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться