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

 

Problem I/S. 11. (October 2016)

I/S. 11. Subscribers can reach the complete after signing in. The text will be public from 28 October 2016.

(10 pont)

Deadline expired on 10 November 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.

main.cpp


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.

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