hjroh loves the classic game, "Snake". "Snake" is played by the following rules.
The game is played on a $n \times m$ grid. $n$ is the $x$-axis length, and $m$ is the $y$-axis length.
The player controls the snake in four (Up, Down, Left, Right) directions. The snake is a sequence of an arbitrary number of connected cells $c_1, c_2, \dots, c_l$. Here, "connected" means that for each $1<i \le l$, $c_{i-1}$ and $c_i$ are adjacent side-by-side.
Each turn, the snake moves either upwards, downwards, left or right. Then, the head ($c_1$) moves towards the direction, and the rest of the cells are superseded by the one previously "in front of it".
The snake cannot occupy the same cell twice at the same time. Therefore, the head cannot move towards any occupied cell other than its tail ($c_l$).
The head of the snake cannot move towards the second cell of the snake ($c_2$).
This game is very simple and famous, an ideal strategy is widely known. The strategy is to keep moving while preserving the invariant property that the head and tail are adjacent. hjroh was curious to know how long a snake he can keep alive using the "ideal strategy". Given the dimensions of the grid, $n$ and $m$, output the maximum length of the snake that can be kept alive infinitely using the "ideal strategy". Also, output any possible arrangement of the longest snake, possible at any point while keeping the "ideal strategy".
입력 (Input)
In one line, $n$ and $m$ are given, separated by spaces. ($2 \le n,m \le 200$) Do note that $n$ is the $x$-axis length, and $m$ is the $y$-axis length.
출력 (Output)
On the first line, output $l$, the longest possible length of the snake.
From the second line, output $l$ lines in total. On the $i+1$th line, you should output two integers $x_i$ and $y_i$, denoting coordinates of the cell $c_i$, separated by spaces.
If there are more than one possible arrangement, you may output any of them.
hjroh0315 3년 전 1
Snake, Constructive
문제 (Description)
hjroh loves the classic game, "Snake". "Snake" is played by the following rules.
This game is very simple and famous, an ideal strategy is widely known. The strategy is to keep moving while preserving the invariant property that the head and tail are adjacent. hjroh was curious to know how long a snake he can keep alive using the "ideal strategy". Given the dimensions of the grid, $n$ and $m$, output the maximum length of the snake that can be kept alive infinitely using the "ideal strategy". Also, output any possible arrangement of the longest snake, possible at any point while keeping the "ideal strategy".
입력 (Input)
In one line, $n$ and $m$ are given, separated by spaces. ($2 \le n,m \le 200$) Do note that $n$ is the $x$-axis length, and $m$ is the $y$-axis length.
출력 (Output)
On the first line, output $l$, the longest possible length of the snake.
From the second line, output $l$ lines in total. On the $i+1$th line, you should output two integers $x_i$ and $y_i$, denoting coordinates of the cell $c_i$, separated by spaces.
If there are more than one possible arrangement, you may output any of them.