奶牛重排序

时间限制:1s 内存限制:64M

问题描述

农夫John的N(1 <= N <= 100)头编号从1到N的奶牛站成了一排。她们的顺序由一个数组A描述,其中A(i)表示站在位置i的奶牛的编号。农夫John想要对这些奶牛进行重新排序,新顺序由数组B描述,B(i)表示最终站在位置i的奶牛的编号。

例如,假设奶牛们的初始顺序如下:

A = 5 1 4 2 3

而农夫John想让她们的顺序变成如下这样:

B = 2 5 3 1 4

为了将她们的队伍从“A”顺序变成“B”顺序,奶牛们进行了多次“回环”移动。一次回环移动是指:开始时一头奶牛移动到她最终在“B”中的位置上,将该位置处的奶牛替换出来;然后被替换出来的奶牛也移动到她最终在“B”中的位置,将另一头奶牛替换出来;如此往复,直到一头奶牛移动到的位置是开始时第一头移动的奶牛的初始位置。例如,在上面的例子中,如果我们从奶牛5处开始一次回环移动,那么奶牛5将移动到位置2,替换出奶牛1,奶牛1移动到位置4,替换出奶牛2,奶牛2移动到位置1,本次移动结束。这群奶牛不断地进行着回环移动,直到每头奶牛的位置都符合”B“的要求。看以发现,每头奶牛都恰好参与到一次回环移动中,除非她在”A“中与”B“中的位置原本就相同。

请计算奶牛们重新排列队伍时进行回环移动的次数,以及最长的一次回环移动的长度。

输入描述

第1行:整数N。

第2..1+N行:第i+1行包含整数A(i)。

第2+N..1+2N行:第1+N+i行包含整数B(i)。

输出描述

第1行:两个空格隔开的整数,其中第一个数表示回环移动的次数,第二个表示最长的一次回环移动有多少头奶牛参与。如果没有进行回环移动,第二个数输出-1。

样例输入

5
5
1
4
2
3
2
5
3
1
4

样例输出

2 3

样例说明

【输出说明】

有2次回环移动,一次涉及奶牛5,1和2,一次涉及奶牛3和4。

附加说明

原文题面:

Problem 1: Reordering the Cows [Brian Dean, 2014]

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.

PROBLEM NAME: reorder

INPUT FORMAT:

  • 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).

SAMPLE INPUT (file reorder.in):

5
5
1
4
2
3
2
5
3
1
4

OUTPUT FORMAT:

  • 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.

SAMPLE OUTPUT (file reorder.out):

2 3

OUTPUT DETAILS:

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

题目来源

USACO 2014 March Contest, Bronze