KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

I/S. 11.

(10 points)

Deadline expired on 10 November 2016.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem I/S. 11.
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

  • Támogatóink:   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