Problem I/S. 11. (October 2016)
I/S. 11. Subscribers can reach the text of the problem after signing in. The text will be public from October 28, 2016.]
(10 pont)
Deadline expired on November 10, 2016.
Sorry, the solution is available only in Hungarian. Google translation
Mivel a mérési költségek nemcsökkenő sorozatot alkotnak, nincs értelme olyan golyót a mérlegre tenni, amiről tudjuk, hogy nem a speciális golyó. Viszont minden mérés után, ha \(\displaystyle K\) golyót mérünk meg, akkor vagy erről a \(\displaystyle K\) golyóról, vagy a maradék \(\displaystyle N-K\) golyóról biztosan tudni fogjuk, hogy nincs köztük a speciális golyó.
Vagyis a helyzet mindig leírható egy pozitív egész számmal: azon golyók számával, amelyekről még nem tudjuk, hogy speciálisak-e.
Ha egy golyónk van, akkor az biztosan a speciális golyó, vagyis végeztünk,
különben pedig ha \(\displaystyle G\) golyónk van, akkor megmérhetünk \(\displaystyle 1\), \(\displaystyle 2\), ... vagy \(\displaystyle G-1\) golyót. Ha \(\displaystyle K\) golyót mérünk meg, akkor a mérés eredményétől függően vagy \(\displaystyle K\), vagy \(\displaystyle G-K\) golyó marad. Vegyük észre, hogy amennyiben minden \(\displaystyle G\)-nél kisebb helyzetre ismerjük az optimális megoldást, akkor minden \(\displaystyle K\)-ra meg tudjuk mondani, hogy ha \(\displaystyle K\) golyót mérünk meg, akkor legrosszabb esetben mennyi ideig tart a keresés. Innen következik, hogy ha minden lehetséges \(\displaystyle K\)-ra kiszámítjuk ezt, és vesszük a legkisebb értéket, akkor megtaláljuk az optimális megoldást \(\displaystyle G\) golyóra.
Láthatjuk, hogy ez egy dinamikus programozási feladat, a futási idő \(\displaystyle O(N^2)\), a memóriahasználat \(\displaystyle O(N)\).
Megjegyzés: Észrevehetjük, hogy ha \(\displaystyle K\) golyót mérünk meg, azzal ugyanazt az eredményt érjük el, mintha a másik \(\displaystyle G-K\) golyót mértük volna meg, ezért mivel a mérési költségek nemcsökkenő sorozatot alkotnak, elég ha a minimum értéket csak \(\displaystyle K=1, \ldots , \lfloor \frac {G} {2} \rfloor\)-re nézzük meg, mivel a minimum biztosan ezek között lesz, de ez nem javít a futási idő komplexitásán, és a maximális pontszám megszerzéséhez nem szükséges.
Statistics:
20 students sent a solution. 10 points: Bálint Martin, Borbényi Márton, Csenger Géza, Földes András Ottó, Gáspár Attila, Gergely Patrik, Horváth Botond István, Janzer Orsolya Lili, Kiss Gergely, Kovács 246 Benedek, Molnár Bálint, Nagy Nándor, Szakály Marcell, Vári-Kakas Andor. 7 points: 2 students. 6 points: 1 student. 4 points: 1 student. 3 points: 1 student. 1 point: 1 student.
Problems in Information Technology of KöMaL, October 2016