Codeforces Round 192 (Div. 1)
D
The Evil Temple and the Moving Rocks
Codeforces
2500
原题
← CE →
翻译中…

Important: All possible tests are in the pretest, so you shouldn't hack on this problem. So, if you passed pretests, you will also pass the system test.

翻译中…

You are an adventurer currently journeying inside an evil temple. After defeating a couple of weak monsters, you arrived at a square room consisting of tiles forming an $*n* × *n*$ grid, surrounded entirely by walls. At the end of the room lies a door locked with evil magical forces. The following inscriptions are written on the door:

翻译中…

The sound of clashing rocks will awaken the door!

翻译中…

Being a very senior adventurer, you immediately realize what this means. In the room next door lies an infinite number of magical rocks. There are four types of rocks:

翻译中…
  • '^': this rock moves upwards;
  • '<': this rock moves leftwards;
  • '>': this rock moves rightwards;
  • 'v': this rock moves downwards.
翻译中…

To open the door, you first need to place the rocks on some of the tiles (one tile can be occupied by at most one rock). Then, you select a single rock that you have placed and activate it. The activated rock will then move in its direction until it hits another rock or hits the walls of the room (the rock will not move if something already blocks it in its chosen direction). The rock then deactivates. If it hits the walls, or if there have been already $10^{7}$ events of rock becoming activated, the movements end. Otherwise, the rock that was hit becomes activated and this procedure is repeated.

翻译中…

If a rock moves at least one cell before hitting either the wall or another rock, the hit produces a sound. The door will open once the number of produced sounds is at least $*x*$. It is okay for the rocks to continue moving after producing $*x*$ sounds.

翻译中…

The following picture illustrates the four possible scenarios of moving rocks.

翻译中…
  • Moves at least one cell, then hits another rock. A sound is produced, the hit rock becomes activated. image
  • Moves at least one cell, then hits the wall (i.e., the side of the room). A sound is produced, the movements end. image
  • Does not move because a rock is already standing in the path. The blocking rock becomes activated, but no sounds are produced. image
  • Does not move because the wall is in the way. No sounds are produced and the movements end. image
翻译中…

Assume there's an infinite number of rocks of each type in the neighboring room. You know what to do: place the rocks and open the door!

翻译中…

Input

翻译中…

The first line will consists of two integers $*n*$ and $*x*$, denoting the size of the room and the number of sounds required to open the door. There will be exactly three test cases for this problem:

翻译中…
  • $*n* = 5, *x* = 5$;
  • $*n* = 3, *x* = 2$;
  • $*n* = 100, *x* = 10^{5}$.
翻译中…

All of these testcases are in pretest.

翻译中…

Output

翻译中…

Output $*n*$ lines. Each line consists of $*n*$ characters — the $*j*$-th character of the $*i*$-th line represents the content of the tile at the $*i*$-th row and the $*j*$-th column, and should be one of these:

翻译中…
  • '^', '<', '>', or 'v': a rock as described in the problem statement.
  • '.': an empty tile.
翻译中…

Then, output two integers $*r*$ and $*c*$ ($1 ≤ *r*, *c* ≤ *n*$) on the next line — this means that the rock you activate first is located at the $*r*$-th row from above and $*c*$-th column from the left. There must be a rock in this cell.

翻译中…

If there are multiple solutions, you may output any of them.

翻译中…

Note

翻译中…

Here's a simulation of the first example, accompanied with the number of sounds produced so far.

翻译中…

image 0 sound

翻译中…

image 1 sound

翻译中…

image 2 sounds

翻译中…

image 3 sounds

翻译中…

image 4 sounds

翻译中…

image still 4 sounds

翻译中…

In the picture above, the activated rock switches between the '^' rock and the '<' rock. However, no sound is produced since the '^' rock didn't move even a single tile. So, still 4 sound.

翻译中…

image 5 sounds

翻译中…

At this point, 5 sound are already produced, so this solution is already correct. However, for the sake of example, we will continue simulating what happens.

翻译中…

image 6 sounds

翻译中…

image 7 sounds

翻译中…

image still 7 sounds

翻译中…

image 8 sounds

翻译中…

And the movement stops. In total, it produces 8 sounds. Notice that the last move produced sound.

翻译中…

Here's a simulation of the second example:

翻译中…

image 0 sound

翻译中…

image 1 sound

翻译中…

image 2 sounds

翻译中…

Now, the activated stone will switch continuously from one to another without producing a sound until it reaches the $10^{7}$ limit, after which the movement will cease.

翻译中…

image

翻译中…

In total, it produced exactly 2 sounds, so the solution is correct.

翻译中…

样例

Input #1
5 5
Output #1
>...v
v.<..
..^..
>....
..^.<
1 1
InputCopy OutputCopy
Input #2
3 2
Output #2
>vv
^<.
^.<
1 3
InputCopy OutputCopy
题目信息
题号
329D
时间限制
2 s
内存限制
256 MB
标签
构造

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。