Polish version    English version  
  History of OI -> II OI 1994/1995 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/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
II OI 1994/1995
Stage III - results
Stage I - results
Problems
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
II Olympiad in Informatics 1994/1995

Task: SZA
Author: Wojciech Rytter
Board Covering

II stage contest  

We are given a board of n × n squares, where n is an odd integer meeting the inequality 3 <= n < 50, and a set of k = (n2 - 3) / 2 stones. Each stone has the shape of a rectangle covering exactly 2 squares of the board. The board squares are numbered consecutively by rows - the squares in the first row (from left to right) are numbered from 1 to n, the squares in the second row from n + 1 to 2n, and so on until we reach the bottom right corner square whose number is n2.

We cut any three squares out of the board, and next we want to cover it with the stones. We require that every square not removed should be covered with exactly one stone (covering also one adjacent square) and that cut out squares remain uncovered.

Is it always possible?

Task

Write a program that:
  • reads from the text file SZA.IN the dimension of the board n and numbers of three board squares that have been cut out,
  • examines whether such a board can be covered with stones.
    If not, the program writes the answer NIE ("no") in the file SZA.OUT.
    If so, it writes in the file SZA.OUT a sequence of k = (n2 - 3) / 2 pairs of integers indicating the positions of stones covering the given board.

If there are many ways to cover the board with stones, your program should write only one (arbitrary) of them.

Input

In the only line of the file SZA.IN there are written four numbers separated by single spaces. The first number is the dimension of the board n, and the three other are the numbers of the cut out squares. The last number is followed by the end of the line.

The data in the file SZA.IN are written correctly, and your program need not verify that.

Output

The file SZA.OUT should contain:
  • either one word NIE
  • or in each of k consecutive lines two numbers separated by a space, i.e. the numbers of two adjacent squares covered with one stone.

Examples

For the file SZA.IN:
7 17 25 40
a correct file SZA.OUT may contain:
18 19
20 21
8 9
10 11
12 13
14 7
6 5
4 3
1 2
15 22
16 23
29 36
30 37
24 31
32 39
43 44
38 45
46 47
48 49
41 42
33 34
35 28
26 27

For the file SZA.IN:

7 25 32 40
the file SZA.OUT should contain only one word:
NIE

Your program should look for the file SZA.IN in the current directory and create the file SZA.OUT also in the current directory. The source file containing the program written by you should be named SZA.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file SZA.EXE.




Print friendly version