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

Problem S. 119. (October 2017)

S. 119. Subscribers can reach the text of the problem after signing in. The text will be public from October 28, 2017.]

(10 pont)

Deadline expired on November 10, 2017.


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

A feladatra érkezett megoldások jelentős részében a versenyzők feltételezték, hogy valamely egyszerű szabályosság alapján következtetni lehet arra, hogy a következő köpeny felvétele előtt érdemes-e levenni a köpenyt, vagy sem. Sajnos – eddig – nem találtunk általános "képlet" arra, hogy egy adott helyzetben mit érdemes tenni. Így igazából az összes eset módszeres végigpróbálása maradt. Természetesen lehetett egyszerűsíteni helyzeteket, pl. ha egy köpeny színe még egyszer nem fordul elő, akkor nyilván levehető, vagy ha az egymást követő manók színei "palindom" helyzetűek, vagyis pl. 12321, akkor nyilván érdemes az 1 és 2 köpenyt nem levenni.

Nézzük az összes eset vizsgálatát. Mivel 30 manón kellett áthaladni, ezért – az utolsó kivételével – 29 helyen lehetett levenni vagy fölvenni a legfelső köpenyt. Így \(\displaystyle 2^{29}\) lehetőség adódik. (Nyilván lehetséges, hogy egy manó után több köpenyt vesz le a herceg, de az egyenértékű azzal, hogy a fölvétel után leveszi.) Ezek alapján egy \(\displaystyle 2^{29} \approx 1024^3 \approx 10^9\). Egy GHz-es processzorral dolgozó gépeken egy backtrack-es megoldás nem fut le 1s alatt, mert a köpenyek cserélgetését adminisztrálni kell a programban. Így a jó megoldáshoz részfeladatokra kellett bontani a teljes feladatot.

Mintamegoldásként Gáspár Attila miskolci (S119.cpp ), és Busa Máté (s119bm.cpp) nagykanizsai versenyző munkáját közöljük.

Tesztfájlok és helyes kimenetek: teszt.zip


Statistics:

14 students sent a solution.
10 points:Busa 423 Máté, Gáspár Attila.
7 points:4 students.
6 points:1 student.
5 points:5 students.
4 points:1 student.
3 points:1 student.

Problems in Information Technology of KöMaL, October 2017