← 返回题目列表

Codeforces · 329/D

D. 邪恶的神庙和移动的岩石

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

重要提示:所有可能的测试都在预测试中,因此您不应该破解此问题。因此,如果您通过了预测试,您也将通过系统测试。

你是一名冒险家,目前正在一座邪恶的神庙中旅行。击败几个弱小的怪物后,你到达一个方形房间,房间由瓷砖组成 n × n 网格,完全被墙壁包围。房间的尽头有一扇被邪恶魔法力量锁着的门。门上刻有以下铭文:

岩石碰撞的声音会唤醒门!

作为一名非常资深的冒险家,你会立即意识到这意味着什么。隔壁的房间里有无数的魔法岩石。岩石有四种类型:

- '^':这块岩石向上移动;
- '<':这块岩石向左移动;
- '>':这块岩石向右移动;
- 'v':这块岩石向下移动。

要打开门,你首先需要将石头放在一些瓷砖上(一块瓷砖最多可以被一块石头占据)。然后,您选择已放置的一块岩石并激活它。然后,激活的岩石将朝它的方向移动,直到它撞到另一块岩石或撞到房间的墙壁(如果有东西已经在其选定的方向上阻挡了它,则岩石将不会移动)。然后岩石就会失活。如果它撞到墙壁,或者已经有 107 次岩石事件被激活,则运动结束。否则,被击中的岩石就会被激活,并重复此过程。

如果一块岩石在撞击墙壁或另一块岩石之前至少移动了一个单元格,则撞击会产生声音。一旦产生的声音数量至少为 x,门就会打开。发出x声后,岩石继续移动是可以的。

下图说明了移动岩石的四种可能情况。

- 移动至少一个单元格,然后击中另一块岩石。发出声音,被击中的岩石被激活。
- 移动至少一个单元格,然后撞到墙壁(即房间的一侧)。发出声音,动作结束。
- 不动,因为路上已经有一块石头了。阻挡岩石被激活,但没有发出任何声音。
- 由于墙壁挡住而无法移动。没有声音产生,动作结束。

假设相邻房间中每种类型的岩石都有无限数量。你知道该怎么做:放置石头并打开门!

输入

第一行由两个整数 n 和 x 组成,表示房间的大小和开门所需的声音数量。这个问题将有三个测试用例:

- n = 5, x = 5;
- n = 3, x = 2;
- n = 100, x = 105。

所有这些测试用例都处于预测试中。

输出

输出n行。每行由 n 个字符组成 - 第 i 行的第 j 个字符代表第 i 行第 j 列的图块内容,并且应该是以下之一:

- '^'、'<'、'>' 或 'v':问题陈述中描述的岩石。
- '.':一个空的图块。

然后,在下一行输出两个整数 r 和 c (1 ≤ r, c ≤ n) - 这意味着你首先激活的岩石位于上数第 r 行、左数第 c 列。这个牢房里一定有一块石头。

如果有多个解,则可以输出其中任何一个。

示例

输入 #1

5 5

输出 #1

>...v
v.<..
..^..
>....
..^.<
1 1

输入 #2

3 2

输出 #2

>vv
^<.
^.<
1 3

注意

这是第一个示例的模拟,并附有迄今为止产生的声音数量。

0 声音

1 声音

2 声

3 声

4 声

仍然有4声

在上图中,激活的岩石在“^”岩石和“<”岩石之间切换。然而,没有发出任何声音,因为‘^’岩石连一块瓷砖都没有移动。所以,还是4声。

5 声

此时,已经产生了5个声音,所以这个解决方案已经是正确的。然而,为了举例,我们将继续模拟发生的情况。

6 声

7 声

仍然有7个声音

8 声音

运动停止。它总共产生 8 种声音。请注意,最后一个动作发出了声音。

这是第二个示例的模拟:

0 声音

1 声音

2 声

现在,激活的石头会不断地从一个石头切换到另一个石头,并且不会发出声音,直到达到107个极限,之后移动就会停止。

总共,它发出了 2 种声音,所以解法是正确的。