USACO 2017 December Contest, Bronze

问题 2. 奶牛舞步

农场主 John 确信快乐的奶牛会产生更多的牛奶，所以他在牛棚里安装了一个巨大的迪斯科球，并计划教他的奶牛跳舞！ 在查阅了流行的奶牛舞蹈之后，农场主 John 决定教他的奶牛们跳“奶牛舞步”。奶牛舞步要求他所有的 N 头奶牛（1 ≤ N ≤ 100）排成一行，按照某个顺序排列，然后进行三次“舞步”操作，每次舞步都会改变奶牛们的位置。最后，奶牛们会排成一个可能不同的顺序。为了让奶牛们更容易找到自己，农场主 John 在牛群的位置上标记了 1 到 N 的编号，所以第一头奶牛排在第 1 号位置，第二头排在第 2 号位置，依此类推，直到第 N 号位置。

一个舞步的描述包含 N 个数字，a1, a2, ..., aN，其中第 i 号位置的奶牛会在这一轮舞步中移动到位置 ai（每个 ai 都在 1 到 N 之间）。每个奶牛都会按照舞步的描述，移动到新的位置。幸运的是，所有的 ai 都是不同的，因此在一次舞步中，不会有两头奶牛移动到同一个位置。

农场主 John 给每头奶牛分配了独一无二的 7 位数字 ID。如果给定了奶牛在三次舞步后的顺序，请你推算出它们最初的顺序。

输入格式 (文件 shuffle.in)：

• 第一行输入一个整数 N，表示奶牛的数量。
• 第二行输入 N 个整数 a1, a2, ..., aN，描述了一次舞步的奶牛位置变化。
• 第三行输入 N 个整数，表示三次舞步后奶牛的顺序，每个数字是奶牛的 ID。

输出格式 (文件 shuffle.out)：

输出 N 行，每行输出一个奶牛的 ID，表示奶牛在三次舞步前的顺序。

示例输入：

5
1 3 4 5 2
1234567 2222222 3333333 4444444 5555555

示例输出：

1234567
5555555
2222222
3333333
4444444

题目分析：

这个问题的关键是逆推舞步操作。每次舞步后，奶牛们的排列顺序会根据给定的映射发生改变。如果我们知道三次舞步后的顺序，和每次舞步的映射规则，我们可以通过逆推来找出三次舞步前奶牛们的顺序。

具体的做法是：

1. 从最后一次舞步开始，根据给定的三次舞步后的顺序，逆推奶牛们原本的位置。
2. 每次逆推时，反转当前的舞步映射。
3. 最终得到的就是奶牛们在三次舞步前的顺序。