Problem S. 54. (May 2010)

S. 54. Nonograms, also known as Paint by Numbers or Griddlers are picture logic puzzles in which cells in a grid have to be colored or left blank according to numbers given at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers measure how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of ``4 8 3'' would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups.

Source: http://en.wikipedia.org/wiki/Nonogram

In the example one should reveal a hidden digit ``8''. (``Feladat'' is the original puzzle, ``Megoldás'' is the solution, while ``Bemenet'' is the corresponding input.)

The structure of the input is the following: the first line contains 2 numbers, the number of rows (s25) and columns (o25) of the image. Then each of the following s lines describes one row of the image by specifying the length of consecutive black blocks of that row. Similarly, each of the next o lines describes the length of consecutive black blocks of the actual column. In the input file there is exactly one space between each piece of data.

Your program should read the description of the puzzle from the standard input, then write the solution image in s rows and o columns to the standard output. A black square is represented by an ,, X'' character and ,,.'' (dot) should be written otherwise.

Your program (s54.pas, s54.cpp, ...) together with a test case (s54.be) and a documentation (s54.txt, s54.pdf, ...) should be submitted. Your test case will also be used to test your other competitors as well.

Evaluation of solutions:

At most 6 points can be awarded if your program correctly solves the test cases created by the proposers of this problem. (The time limit for each test case is 1 minute on a Core2Duo processor at 2 GHz with 2 GB of memory.)

The documentation and your test case are worth of 2 points.

Finally, 2 more points are awarded if your program solves within the time limit the most test cases submitted by other contestants. If there is a draw, then solutions are ranked according to the total time needed to solve the test cases. Besides the winner, competitors ranked among the first half of all will be awarded 1 extra point.

(10 pont)

Deadline expired on June 10, 2010.

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

A feladat nem számított egyszerűnek, az mégis meglepő, hogy csak 2 beküldő próbálkozott. Éles András hatékony algoritmusa az általunk adott tesztesetekre ( s54teszt.zip ) rendkívül gyorsan megoldást adott.

Az ő megoldását és dokumentációját is közöljük: s54.cpp s54dok.txt

Statistics:

3 students sent a solution.
10 points:	Éles András.
5 points:	1 student.
2 points:	1 student.

Problems in Information Technology of KöMaL, May 2010