Polish version    English version  
  OI books


 News
 About Olympic
 History of OI
 OI books
Publications in English
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2003/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
Where to buy?
Order
PS and PDF files
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
X Olympiad in Informatics 2002/2003

Problem: Crystal
Author: Marcin Stefaniak

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

Write a program which controls the laboratory apparatus. Your program should:
  • 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

Your program should communicate with "the rest of the world" exclusively by means of calls to the functions and procedures of the module (krysztal.pas in Pascal, krysztal.h in C/C++; "krysztal" = "crystal" in Polish). It means that it is not permitted to open any files nor to use the standard input/output streams.
        (* 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);
("rozmiar" = "size", "zamroz" = "freeze", "niestabilna" = "unstable")

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 (xy), 1 <= xy <= n.

A function call zamroz(xy) (for 1 <= xy <= n) freezes the atom at the coordinates (xy), 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 (x1y1), (x2y2) is determined, your program should call the procedure niestabilna (x1y1x2y2). 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