Олимпиадный тренинг

Задача . Reordering the Cows


Задача

Темы: графы

N (1 <= N <= 100) коров Фермера Джона, последовательно пронумерованных от 1 до N, стоят в ряд. Их порядок описан массивом A, где A(i) это номер коровы на позиции i. ФД реорганизовать их в другом порядке, описанном в массиве B, где B(i) – номер коровы, которая должна оказаться на позиции i.
Например, предположим, что изначальный порядок таков:
A = 5 1 4 2 3
И предположим, что ФД хочет переупорядочить их так:
B = 2 5 3 1 4
Переупорядочивание от “A” к “B” осуществляется посредством некоторого количества «циклических» сдвигов. Каждый такой циклический сдвиг начинается с коровы, которая перемещается на свою позицию в “B”-порядке, замещая корову, которая затем движется на свою позицию и т.д, пока какая-то корова не попадёт в место, которая занимала первая корова в этом цикле.
Например, для данных, описанных выше, мы начинаем цикл с коровы 5, которая должна переместиться на позицию 2, замещая корову 1, которая перейдёт на позицию 4, замещая корову 2, которая перейдёт на позицию 1, завершая цикл.
Коровы продолжают выполнять циклические сдвиги, пока все коровы не окажутся на своём месте, определённом B-упорядочиванием.
Пожалуйста, вычислите количество различных циклических сдвигов, а также длину наибольшего циклического сдвига, во время такого переупорядочивания коров.
PROBLEM NAME: reorder
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит целое число A(i).
* Строки 2+N..1+2N: Строка 1+N+i содержит целое число B(i).
Формат выходных данных
* Строка 1: Два разделённых пробелом целых числа, первое даёт количество циклических сдвигов, второе даёт количество коров, которые поучаствовали в самом длинном сдвиге. Если нет циклических сдвигов, выведите -1 в качестве второго числа.
Примечание
Всего имеется два циклических сдвига, один включает коров 5 1 2, а второй включает коров 3 4.
Примеры
№Входные данныеВыходные данные
1 
5
5
1
4
2
3
2
5
3
1
4
 
2 3
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет