Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 82. (September 2013)

S. 82. We would like to place N castles on an N×N chessboard (N\le 1\;000\;000) so that no castle can attack any other castle: two castles attack each other precisely if they are positioned in the same file or rank. To complicate things a bit, some further restrictions are imposed: the ith castle can be placed only in the rectangle spanned by the coordinates (ai,bi) (as upper left) and (ci,di) (as lower right).

Your task is to decide whether this construction can be realized or not. If not, you should display ``NOT''. If yes, you should give a solution: rank and file numbers of each castle should be displayed in a separate line. Castles should be displayed in the same order as the given rectangles: the first line of the output should contain coordinates of the first castle, and so on.

Your program should read the value of N from the first line of the standard input, then the values of the ai, bi, ci, di integers separated by a space from the second line. The output of your program should be given in the first line of the standard output: either a ``NOT'' message, or the castle coordinates should be displayed. In the example, ``Példa bemenet'' is the sample input, while ``Példa kimenet'' is the corresponding output.

Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. The maximal 9 points for your program can only be obtained if it can solve an arbitrary valid input within 1 second of running time. You can test your program by downloading some sample input-output files from our website. Partial points can be obtained according to the following:

- your program gives a solution for N\le12,

- every rectangle is of size 1×2 or 1×3,

- every rectangle is of size 1×2 or 2×2.

The source code (s82.pas, s82.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s82.txt, s82.pdf, ...) - also describing which developer environment to use for compiling - should be submitted in a compressed file

(10 pont)

Deadline expired on October 10, 2013.

Sorry, the solution is available only in Hungarian. Google translation

Mintamegoldásként és hozzá dokumentációként Fonyó Viktória megoldását tesszük közzé:


13 students sent a solution.
10 points:Fonyó Viktória, Jákli Aida Karolina, Somogyvári Kristóf, Weisz Ambrus.
7 points:1 student.
6 points:1 student.
5 points:1 student.
4 points:1 student.
3 points:2 students.
2 points:1 student.
1 point:2 students.

Problems in Information Technology of KöMaL, September 2013