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

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?

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