Az S. 54. feladat (2010. május)

S. 54. A grafilogika rejtvény egy téglalap alakú négyzetrácsos hálóból áll, amelynek az egyik vízszintes, és az egyik függőleges oldala mellett számok állnak, amelyek azt jelzik, hogy az adott sorban, vagy oszlopban mekkora méretű sötét blokkok követik egymást. Minden beszínezett blokkot tetszőleges számú (legalább egy) üres hely választ el egymástól. A játék célja, hogy eldöntsük minden négyzetrácsról, hogy be van-e színezve, vagy nem.

Forrás: http://hu.wikipedia.org/wiki/Grafilogika

Az alábbi példában a 8-as számjegy kitalálása a cél.

A bemenet szerkezete a következő: az első sorban két szám, a kép sorainak (s25) és oszlopainak (o25) száma található. A következő s sor mindegyike egy-egy sort ír le, amelyben a sor sötét blokkjainak hossza szerepel, az azt követő o sorban pedig az adott oszlop sötét blokkjainak hossza olvasható. A bemeneti fájl soraiban az adatokat pontosan egy szóköz választja el egymástól.

Készítsünk programot, amely a standard bemenetről beolvassa a rejtvény leírását, majd a standard kimenetre írja a képet s sorban és o oszlopban. A sötét elem helyére az ,,X'' karaktert, a többi helyre pedig a ,,.'' (pont) karaktert írjuk.

Beküldendő a program (s54.pas, s54.cpp, ...), egy teszteset (s54.be), amelyet a többi versenyző értékelésekor is használunk, valamint a dokumentáció (s54.txt, s54.pdf, ...).

Értékelés:

Maximum 6 pontot szerezhető az általunk adott teszteseteket időlimiten belül helyesen megoldó programmal. (Időlimit tesztesetenként 1 perc, a gép processzora Core2Duo, 2 GHz, 2 GB memóriával.)

A dokumentáció és a beküldött teszteset 2 pontot ér.

Még 2 pontot szerez az, akinek a programja időlimiten belül a legtöbb -- többi versenyző által beküldött -- tesztesetet megold. Egyezés esetén a megoldott tesztesetek időigényének összege rangsorol. A győztesen kívül 1 plusz pontot szerez, aki a fenti rangsorban a mezőny első felében végez.

(10 pont)

A beküldési határidő 2010. június 10-én LEJÁRT.

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

Statisztika:

3 dolgozat érkezett.
10 pontot kapott:	Éles András.
5 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2010. májusi informatika feladatai