KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem I. 190. (September 2008)

I. 190. We simulate the crystallization of a melted substance in a rectangle-shaped furnace. The box is divided into N×M squares, containing either 0 (melted state) or 1 (crystallized state). A square with melted substance crystallizes, if at least 3 squares out of its 8 neighbours have already crystallized. See the figure.

The state of each square is recomputed in every simulation step, and we change melted into crystallized state where necessary. (In the next simulation step in the example, the middle 0 will become 1, because it has at least 3 crystallized neighbours. Similarly, the fourth cell in the first row will be 1, but no more changes will take place in this step.)

The command line argument of your program is the name of the input file containing the initial pattern of crystals. The first row of the input file contains two positive integers, the number of rows (3\leN\le200) and columns (3\leM\le200) of the state matrix. Then each of the following N lines contains M values, either 0 or 1.

The output of your program (written on the standard output) should contain the number of steps in which complete crystallization occurs. (If this does not happen, the output should be ``Crystallization has stopped''.)

See the example (``Bemenet'' is input, and ``Kimenet'' is output).

The source code of your program (i190.pas, i190.cpp, ...) together with a short documentation (i190.txt, i190.pdf, ...) should be submitted, also containing a brief description of your solution and the name of the developer environment to use.

(10 pont)

Deadline expired on 15 October 2008.


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

Megoldás menete:

A megoldás során két tömböt (T1 és T2) használunk a szimulációstér aktuális és következő állapotának tárolásához (lásd mintamegoldás). Az Elokeszit eljárás a folyadékot ábrázoló 0-kal veszi körbe a cellák halmazát, így a kristály szomszédok megszámlálása nem igényel külön eljárást a mátrix szélén. A folyadék 0 és a kristály 1 ábrázolása a kristály szomszédok számának meghatározását egyszerű összegzésre vezeti vissza. Elég a Szomszedszamlalas() függvényt csak a folyadék, 0 tartalmú cellák esetén használnunk. A Szimulacio eljárást addig hajtjuk végre, amíg változás történik. Ha az 1-esek, azaz kristályok száma megegyezik a cellák számával, akkor a minden folyadék kikristályosodott, különben a kristályosodás előbb leállt.

Típushibák:

Sok beküldött program a standard bemenet és kimenet használata helyett fájlból olvasta és fájlba írta az eredményt. Nagy adatmennyiségekkel így nem lehet tesztelni a megoldásokat. Nem kellett megjeleníteni minden lépés után a szimulációsteret. Ez nagy méretnél nem is lehetséges karakteres felbontásnál. A be- és kimenettel több probléma volt. Több program szóközöket várt a bemeneti adatok között, illetve a futás végén billentyűleütésre várt. Amennyiben a feladat szövegében a be- és kimenetet pontosan definiáljuk, úgy a program a bemenetet mindig a specifikált formában fogja kapni, így azt nem kell ellenőrizni, illetve a kért kimeneten kívül semmi mást nem kell kiírni.

Siegler Gábor

Megoldás:

kristalyosodas.dpr


Statistics:

25 students sent a solution.
10 points:Dévényi Attila, Englert Péter, Erdős Gergely, Fár Attila Gergő, Földes Imre, Gaizer Bence, Hunyady Márton, Jákli Gábor, Kővágó Zoltán, Molnár Gábor, Nagy 111 Miklós, Póta Kristóf, Szabó 313 Gábor, Uray Marcell János.
9 points:Pap 999 Dávid.
8 points:3 students.
7 points:1 student.
5 points:2 students.
4 points:2 students.
3 points:1 student.
1 point:1 student.

Our web pages are supported by:   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