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

Problem I. 244. (September 2010)

I. 244. We compress geometric figures consisting only of few colours. For each row, only the difference between the actual row and its predecessor is stored in the compressed file. There is no entry for a row in the compressed file, if that row is identical to the previous one.

You can download the file zaszloX.be from our web page (zaszlo5.be). The first line of the file contains the number of rows N (1\leN\le100) and columns M (1\leM\le100) of the image. The following lines describe the compressed image, in an increasing order in each line and in each column. The first number refers to the corresponding row of the uncompressed image, while the second and third numbers are the starting and ending positions between which the uppercase letter in the fourth position is repeated.

In the example, zaszlo5.be is the encoded image, and ``Az eredeti kép (a dán zászló)'' is the original image, being the Danish flag.

Your program i244 should solve the following tasks by using the data in the file zaszloX.be given as the first command line argument to your program. The number of the actual task (e.g. ``Task #3'') should always be displayed.

[1.] Read the content of the input file and store it in an appropriate data structure.

[2.] Create and display the uncompressed image. A space character should appear between the letters.

[3.] Display the number of different colours (letters) appearing on the image.

[4.] You should save the image as zaszloX.ki (specified by the second command line argument), but by using a different compression method. The original image of N rows should be compressed into N rows: each row of the compressed image should contain uppercase letters describing a colour and the number of repetitions of that colour, each separated by a space. The second example shows again the Danish flag compressed by this method.

[5.] Your program should ask for a character position of the image, then display its colour and the size of the largest connected block of letters of the same colour that character is part of.

[6.] Display the original image in double size: each letter of the original image should correspond to a 2×2 block of identical letters of the magnified image.

The source code and project files of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (i244.txt, i244.pdf, ...) in a compressed folder i244.zip. (Idea is taken from an OKTV 2009 Informatics Competition problem.)

(10 pont)

Deadline expired on October 11, 2010.


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

Megoldásokról

Összesen 15 megoldás érkezett a feladatra. Tartalmi és formai szempontból összesen három megoldás volt 100%-os. Néhány tipikusan előforduló hiányosság:

A be- és kimeneti állományok nevét a parancssor argumentumaként kellett volna megadni. Ezt többen nem így oldották meg. A megoldásokat több teszt bemeneti állománnyal próbáljuk ki. A javítást, a vizsgálatot nehezíti, ha minden futtatáskor be kell írni 1-2 állománynevet.

A program rövid dokumentációja is teljesen hiányzott néhány versenyzőnél, pedig a feladat külön felhívta erre a figyelmet. Fontosnak gondoljuk, hogy a megoldások elvét, algoritmusát megértsük, illetve a programok fordítási környezetét is illik megadni.

Az 5. részfeladat megoldása több versenyzőnél hiányzott. Ez nem véletlen, hiszen ehhez kellett a legtöbb ötlet. Megoldást jelenthet, ha a zárt görbék kifestéséhez hasonló rekurzív eljárást készítünk az azonos értékű tömbelemek számának meghatározásához.

Mintamegoldás zaszlo.dpr

Teszteléshez be- és kimeneti állományok: i244beki.zip


Statistics:

15 students sent a solution.
10 points:Hoffmann Áron, Nagy 111 Miklós, Szabó 928 Attila.
9 points:Barta 111 János, Gema Barnabás, Nagy 319 Vendel, Papp Gergely.
8 points:1 student.
7 points:3 students.
6 points:1 student.
5 points:2 students.
4 points:1 student.

Problems in Information Technology of KöMaL, September 2010