Byteotian physicists are doing research on crystals of bitanium. Atoms in bitanium crystals form a grid-shaped square lattice having perpendicular axes. Each crystal have two perpendicular axes: horizontal and vertical one. Each atom in such a crystal spins in its position round one of the crystal axes (horizontally or vertically), in one or other direction. As we have two axes and two spin directions, each atom in a given moment can be in one of four states.

If two atoms spin round the same axis but in opposite directions, we say that they spin oppositely. An atom and an atom next to it on an axis or a diagonal may form a stable or unstable pair. If such atoms spin oppositely, we say that they form an unstable pair, otherwise we say that they form a stable pair.

By putting a square crystal of bitanium in a polarised bitomagnetic field, Byteotian physicist are able to obtain a situation where peripheral atoms of the crystal form stable pairs and do not change their states, moreover, peripheral atoms symmetric with respect to the centre of the crystal spin oppositely. The theory states that in every moment there has to be an unstable pair of atoms in such a crystal. Unfortunately, nobody knows where such a pair is located, for inside the crystal atoms continuously alter their states.

Recently a technique of "freezing" atoms in a crystal has been developed. A frozen atom does not alter its state. It is not possible to determine in what state an atom will be frozen, but after freezing its state can be seen. The putting of a crystal in a bitomagnetic field freezes the atoms on its periphery. Additionally, one can freeze some atoms inside the crystal, unfortunately not all of them. In a square crystal of dimensions n * n atoms, one can freeze in addition (apart from the periphery) at most 3n atoms.

Task

• get from the apparatus the information on states of the atoms on the crystal periphery,
• control the freezing of atoms and examine the states of frozen atoms,
• achieve a condition in which an unstable pair of atoms is frozen and output the coordinates of such a pair.

To enable you to test your program by yourself you will be provided with a simplified control module for the apparatus.

Description of Apparatus Interface

        (* Pascal *)
        function rozmiar: integer; 
        function zamroz (x, y : integer) : integer; 
        procedure niestabilna (x1, y1, x2, y2 : integer);

        /* C/C++ */
        int rozmiar(void);
        int zamroz (int x, int y);
        void niestabilna (int x1, int y1, int x2, int y2);

Your program should first start the apparatus by calling the function rozmiar which returns the size of the crystal n, 3 <= n <= 10000. The examined crystal has dimensions of n * n atoms. Atoms in the crystal are identified by integer coordinates (x, y), 1 <= x, y <= n.

A function call zamroz(x, y) (for 1 <= x, y <= n) freezes the atom at the coordinates (x, y), and the function returns the state of the atom being frozen. The states of atoms are represented by numbers -2, -1, 1 or 2. The absolute value of the number specifies the axis round which the atom spins, and its sign determines the direction of the atom's spin. (Notice that it does not matter which axis is represented by numbers 1 and -1 and which by 2 and -2, also it is not significant which spin direction is represented by negative and which by positive numbers.) Atoms on the crystal periphery are already frozen when the apparatus starts. Freezing of a frozen atom does not alter its state. The function zamroz may be called at most 3n times for the atoms in the interior of the crystal. For the atoms on the periphery of the crystal it may be called arbitrary many times.

After an unstable pair (x₁, y₁), (x₂, y₂) is determined, your program should call the procedure niestabilna (x₁, y₁, x₂, y₂). Calling this procedure ends the run of the program. If there are many unstable pairs of atoms your program should present one of them (arbitrary).

Example

An example of interaction with the program may look as follows:

        rozmiar() = 5
        zamroz (1, 1) = 1
        zamroz (1, 2) = 1
        zamroz (1, 3) = 1
        zamroz (1, 4) = 1
        zamroz (1, 5) = 2
        zamroz (2, 5) = 2
        zamroz (3, 5) = 2
        zamroz (4, 5) = 2
        zamroz (3, 3) = 2
        zamroz (2, 2) = 1
        zamroz (4, 2) = -1
        zamroz (3, 2) = -2
        niestabilna (3, 2, 3, 3)

Print friendly version