P8387 - Reordering the Cows

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：1 通过：1

Farmer John's N cows (1 <= N <= 100), conveniently numbered 1..N, are standing in a row. Their ordering is described by an array A, where A(i) is the number of the cow in position i. Farmer John wants to rearrange them into a different ordering for a group photo, described by an array B, where B(i) is the number of the cow that should end up in position i. For example, suppose the cows start out ordered as follows: A = 5 1 4 2 3 and suppose Farmer John would like them instead to be ordered like this: B = 2 5 3 1 4 To re-arrange themselves from the "A" ordering to the "B" ordering, the cows perform a number of "cyclic" shifts. Each of these cyclic shifts begins with a cow moving to her proper location in the "B" ordering, displacing another cow, who then moves to her proper location, displacing another cow, and so on, until eventually a cow ends up in the position initially occupied by the first cow on the cycle. For example, in the ordering above, if we start a cycle with cow 5, then cow 5 would move to position 2, displacing cow 1, who moves to position 4, displacing cow 2, who moves to position 1, ending the cycle. The cows keep performing cyclic shifts until every cow eventually ends up in her proper location in the "B" ordering. Observe that each cow participates in exactly one cyclic shift, unless she occupies the same position in the "A" and "B" orderings. Please compute the number of different cyclic shifts, as well as the length of the longest cyclic shift, as the cows rearrange themselves.
农夫约翰的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”订单中的适当位置开始，

替换另一头母牛，然后母牛移动到适当的位置，替换

另一头母牛，依此类推，直到最后一头母牛到达这个位置

最初由自行车上的第一头牛占据。例如，在

在上面的排序中，如果我们用cow 5开始一个循环，那么cow 5将移动到

位置2，取代奶牛1，奶牛1移动到位置4，取代奶牛2，

移动到位置1，结束循环。奶牛继续循环

直到每头牛最终在“B”中的适当位置

订购。观察每头奶牛只参与一次循环移位，

除非她在“A”和“B”排序中占据相同的位置。

请计算不同循环移位的数量以及长度

最长的周期性变化，因为奶牛会重新安排自己。

* Line 1: The integer N. * Lines 2..1+N: Line i+1 contains the integer A(i). * Lines 2+N..1+2N: Line 1+N+i contains the integer B(i).

* Line 1: Two space-separated integers, the first giving the number of cyclic shifts and the second giving the number cows involved in the longest such shift. If there are no cyclic shifts, output -1 for the second number.

There are two cyclic shifts, one involving cows 5, 1, and 2, and the other involving cows 3 and 4.

2 3

2014 March Contest Bronze

8387: Reordering the Cows

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签