Решение задачи Обмен книгами (простая версия) с Codeforces

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

Единственное отличие между простой и сложной версиями — ограничения.

Есть n детей, каждый из которых читает уникальную книгу. В конце каждого дня i-й ребёнок отдаёт свою книгу pi-му ребёнку (в случае, когда i=pi ребенок отдает свою книгу самому себе). Гарантируется, что все значения pi — различные целые числа от 1 до n (то есть p — перестановка). Последовательность p не меняется изо дня в день, она фиксированная.

Например, если n=6 и p=[4,6,1,3,5,2], то в конце первого дня книга 1-го ребёнка будет у 4-го ребёнка, книга 2-го ребёнка будет у 6-го ребёнка и так далее. В конце второго дня книга 1-го ребёнка будет у 3-го ребёнка, книга 2-го ребёнка будет у 2-го ребёнка и так далее.

Перед вами стоит задача — для каждого i от 1 до n определить число дней, через которое книга i-го ребёнка вернётся обратно к нему в первый раз.

Предположим что p=[5,1,2,4,3]. Книга 1-го ребёнка будет передана следующим детям:

после 1-го дня она будет у 5-го ребёнка,
после 2-го дня она будет у 3-го ребёнка,
после 3-го дня она будет у 2-го ребёнка,
после 4-го дня она будет у 1-го ребёнка.
Таким образом, после четвертого дня книга первого ребёнка вернётся к своему владельцу. Книга четвёртого ребёнка вернётся к нему в первый раз сразу после первого дня.

Вы должны ответить на q независимых запросов.

Код 

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int q,n,a[205];
	cin>>q;
	while(q--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		    cin>>a[i];
		for(int i=1;i<=n;i++)
		{
			int m=a[i],ans=1;
			while(m!=i)
			{
				ans++;
				m=a[m];
			}
			cout<<ans<<" ";
		}
		cout<<endl;
	}
	return 0;
}

         

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



Комментарии

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



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp