KöMaL - Középiskolai Matematikai és Fizikai Lapok
A lap

Rendelje meg a KöMaL-t!

VersenyVizsga portál


Matematika oktatási portál

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 s82.zip.

(10 points)

Deadline expired on 10 October 2013.

Google Translation (Sorry, the solution is published in Hungarian only.)

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

Statistics on problem S. 82.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley