← 返回题目列表

Codeforces · 995/A

A. 特斯拉

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

艾伦梦想有一天拥有一支庞大的电动汽车车队,这是未来的汽车!他知道,这会给他带来巨大的地位提升。当艾伦正在规划他将拥有的所有不同类型的汽车以及如何安排它们时,他意识到自己遇到了问题。

艾伦未来的停车场可以表示为一个具有 $$$4$$$ 行和 $$$n$$$ ($$$n \le 50$$$) 列矩形空间的矩形,每个矩形空间在任何时候最多可以容纳一辆车。他想象网格中有 $$$k$$$ ($$$k \le 2n$$$) 辆汽车,并且所有汽车最初都位于第二排和第三排。每辆车在第一排或第四排也有不同的指定停车位。艾伦必须将汽车放入相应的停车位。

第一个示例的说明。

然而,由于艾伦永远不会把他的车托付给其他人,所以一次只能移动一辆车。他可以将汽车从四个基本方向中任意一个的空间驾驶到邻近的空地。此外,艾伦只能将他的一辆车移动到第一排或第四排的车位(如果该车位是该车的指定停车位)。

艾伦知道他将是一个非常忙碌的人,并且最多只有 $$$20000$$$ 次的时间来移动汽车,然后他才意识到移动汽车不值得他花时间。帮助艾伦确定他是否应该费心停车,还是把车留给不那么重要的人。

输入

输入的第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le k \le 2n$$$),分别代表列数和汽车数。

接下来的四行将包含 $$$n$$$ 整数,每个整数在 $$$0$$$ 和 $$$k$$$ 之间(包括 $$$0$$$ 和 $$$k$$$),表示停车场的初始状态。行从上到下编号为 $$$1$$$ 到 $$$4$$$,列从左到右编号为 $$$1$$$ 到 $$$n$$$。

在第一行和最后一行中,整数 $$$1 \le x \le k$$$ 代表分配给汽车 $$$x$$$ 的停车位(你只能将这辆车移动到这个地方),而整数 $$$0$$$ 代表一个空位(你不能将任何汽车移动到这个地方)。

在第二行和第三行中,整数 $$$1 \le x \le k$$$ 代表汽车 $$$x$$$ 的初始位置,而整数 $$$0$$$ 代表空位(您可以将任何汽车移动到该位置)。

$$$1$$$ 和 $$$k$$$ 之间的每个 $$$x$$$ 在第二行和第三行中恰好出现一次,在第一行和第四行中恰好出现一次。

输出

如果有一系列移动将所有汽车带到其停车位,最多移动 $$$20000$$$ 汽车,则在第一行打印移动次数 $$$m$$$。在接下来的 $$$m$$$ 行中,以 $$$i$$$ $$$r$$$ $$$c$$$ 格式打印移动(每行一次),这对应于 Allen 将汽车 $$$i$$$ 移动到 $$$r$$$ 行和 $$$c$$$ 列的相邻空间。

如果 Allen 不可能通过最多 $$$20000$$$ 的汽车移动将所有汽车移动到正确的位置,请打印一行包含整数 $$$-1$$$ 的行。

示例

输入 #1

4 5
1 2 0 4
1 2 0 4
5 0 0 3
0 5 0 3

输出 #1

6
1 1 1
2 1 2
4 1 4
3 4 4
5 3 2
5 4 2

输入 #2

1 2
1
2
1
2

输出 #2

-1

输入 #3

1 2
1
1
2
2

输出 #3

2
1 1 1
2 4 1

注意

在第一个示例测试用例中,除了 $$$5$$$ 车位于相邻停车位前面之外,所有汽车都位于其停车位前面。该示例显示了最短的可能移动序列,但任何长度最多 $$$20000$$$ 的序列都将被接受。

在第二个示例测试用例中,只有一列,并且汽车的顺序错误,因此没有汽车可以移动,任务是不可能的。