← 返回题目列表

Codeforces · 1239/E

E. 乌龟

中文机器翻译题面 查看原题

Kolya 有一只乌龟和一块大小为 $$$2 \times n$$$ 的田地。字段行从上到下编号为 $$$1$$$ 到 $$$2$$$,而列从左到右编号为 $$$1$$$ 到 $$$n$$$。

假设田地的每个单元格中有一片生菜叶。 $$$i$$$行、$$$j$$$列的生菜叶子的能量值等于$$$a_{i,j}$$$。海龟最初位于左上角的单元格中,并且想要到达右下角的单元格。乌龟只能向右和向下移动,它会在所有可能的路径中选择一条使生菜叶子的总能量值最大化的路径(如果有多个这样的路径,它会选择其中任何一个)。

Kolya 担心,如果乌龟吃太多生菜,可能会对其健康不利。所以他想重新排列田间的生菜叶子,这样海龟吃掉叶子的能量消耗就会降到最低。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 25$$$) — 字段的长度。

第二行包含 $$$n$$$ 整数 $$$a_{1, i}$$$ ($$$0 \le a_{1, i} \le 50\,000$$$),即田地第一行生菜叶的能量消耗。

第三行包含 $$$n$$$ 整数 $$$a_{2, i}$$$ ($$$0 \le a_{2, i} \le 50\,000$$$),即该字段第二行生菜叶子的能量消耗。

输出

打印两行,每行包含 $$$n$$$ 整数 - 根据输入数据对生菜进行最佳重新排序。

如果有多种重新订购生菜的最佳方法,请打印其中任何一种。

示例

输入 #1

2
1 4
2 3

输出 #1

1 3 
4 2

输入 #2

3
0 0 0
0 0 0

输出 #2

0 0 0 
0 0 0

输入 #3

3
1 0 1
0 0 0

输出 #3

0 0 1
0 1 0

注意

在第一个示例中,重新排序后,乌龟将吃生菜,总能量消耗为 $$$1+4+2 = 7$$$。

在第二个例子中,乌龟会吃生菜,能量消耗等于 $$$0$$$。

在第三个示例中,重新排序后,乌龟将吃生菜,总能量消耗等于 $$$1$$$。