eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Langton`s Ant

Langton`s Ant

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Langton's ant, after the mathematician Christopher Langton, is a cellular automaton with a very simple set of rules but interesting emergent behavior; this behavior is currently the matter of research for some mathematicians. The analogy between ants and Langton's cellular automaton comes from the observation that one can arbitrarily identify the state of the automaton as the "ant", and the dynamics of the automaton with the ability of the ant to travel in a special world.

x

The ant world's is an nn plane where the squares (or cells) on the plane are colored variously either blue or red. The number n is called the size of the world. A cell is denoted with a pair (i, j), (1 ≤ i, j ≤ n). The ant lives and moves in single steps following the rules below:

  • if it is on a blue cell, it flips the color of the cell, turns

    to the left, and moves forward to the next cell in the direction it is facing;

  • if it is on a red cell, it flips the color of the cell, turns

    to the right, and moves forward to the next cell in the direction it is facing; and

  • if a movement is impossible (because the ant cannot move out of the world), then the ant dies.

For example, let us assume the ant is in a red cell while facing east. If there is not a cell immediately to its south, then the ant dies. On the contrary, if there is a cell immediately to its south, then the ant takes a single step by moving to this cell to which it arrives facing south and the color of its source cell flips to blue. Then, the ant will try to take another single step, and so on.

Your task is to determine if the ant can go to the (n, n) cell of a world, given (i) the configuration of the world, and (ii) the initial position of the ant. You are to assume the ant's initial direction is north.

Входные данные

x

x

The configuration of an nn world can be codified as a natural number in binary notation by using n^2 bits. We adopt the following conventions: 0 = blue, 1 = red, and the binary representation of the configuration identifies the cells of the world from left to right and from bottom to top (considering the bits from the most significant bit to the least significant bit). For example, the binary number 0100 (4 in decimal notation) represents a 22 world with the following configuration:

x

Coherently, the binary number 011010100 (212 in decimal notation) represents a 33 world with the following configuration:

The problem input has several test cases. Each case consists of a single line containing a list of four natural numbers, n, c, x, y, separated by blanks, that should be interpreted as:

  • n (1n16): the size of the world;

  • c (0c < 2^{(n2)}): decimal representation of an n^2-bit binary number that describes an initial configuration of the world, as above explained;

  • (x, y): coordinates of the initial position of the ant in the world (1x, yn), where the position (n, n) corresponds to the least significant bit of c.

The end of the input is indicated by a line where n = c = x = y = 0.

Выходные данные

For each test case your solution should output:

  • "Yes" if the ant reaches the cell (n, n) from the initial position;

  • "Kaputt!" if the ant dies without reaching the cell (n, n) from the initial position.

For each test case, it's guaranteed that after a finite number of steps, the ant reaches the cell (n, n) or dies without reaching the cell (n, n).

Пример

Входные данные #1
2 8 1 1
2 4 1 1
2 15 1 1
0 0 0 0
Выходные данные #1
Yes
Kaputt!
Kaputt!