Problem I. 466. (November 2018)

I. 466. Subscribers can reach the text of the problem after signing in. The text will be public from November 28, 2018.]

(10 pont)

Deadline expired on December 10, 2018.

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

A feladatra 5 különböző nyelven érkezett megoldás. A legnépszerűbb a C# volt, 4 megoldó használta. Érkezett C, C++, VB és Java nyelvű megoldás is.

Meglepően kevés tökéletes megoldás született. Két algoritmussal lehetett nagyobb méretű tesztesetekre működő megoldást megadni. Ha csak a helyes törési sorrend kialakítását vesszük alapul, akkor az egyik elgondolás szerint rendezni kell az egyik, azon belül pedig a másik koordináta szerint. Időigénye a törési pontok számától és a rendezési algoritmustól függ. Egy másik módszer a táblán bejelöli a törési pontokat, majd megkeresi azokat. Ennek időigénye a legrosszabb esetben csokoládétábla méretével arányos.

Az egyik hibátlan megoldást beadó versenyző, Ürmössy Dorottya utóbbi elven dolgozott, leírása szerint:

1. Az adatokból egy N*M-es matrixot állítok elő, ahol minden elem 1 értékű, kivétel azokat a pontokat, ahol törés volt. Ezeken a pontokon a törés száma lesz az érték, negatív előjellel.

2. Az 1,1 pontból indulva a sorokon illetve oszlopokon végigpáztázva keresem a 0-nál kissebb elemeket. Ha ilyet találok, akkor annak értékét (pozitív előjellel) kiírom, illetve a tőle kisebb sor és oszlopszámú elemek értékeit összegzem, és közben 0-ra állítom. Az összegeket az első vagy második játékos által gyűjtött értékekhez adom, attól függően, hogy páros vagy páratlan sorszámú a találat.

3. A 2-es pontot addig ismétlem, amíg az összes töréspontot meg nem találom.

Megoldása: i466urmossy.cs

A program teszteléséhez 8 tesztesetet használtunk, 1-1 pontot érően. (Csak a teljesen hibátlan kimenetért járt pont.) Az alábbiakban: 1: a mintaként megadott, 2: egyetlen törést tartalmazó, 3: bármely törési sorrend jó, 4: 2xN méretű a csoki, 5: a teljes csokoládé elfogy, 6: közepes méretű, nagyságrendileg az oldalhosszal egyező töréssel, 7: maximális méretű tábla, mérethez képest kevés töréssel, 8: maximális méretű tábla, a feladatban megengedett maximális számú töréssel.

A tesztesetek: i466bemenet.zip

Statistics:

9 students sent a solution.
10 points:	Nagy 793 Márton, Ürmössy Dorottya.
9 points:	Papp Marcell Miklós, Zámborszky Balázs.
6 points:	2 students.
5 points:	1 student.
4 points:	1 student.
3 points:	1 student.

Problems in Information Technology of KöMaL, November 2018