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