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!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

S. 110.

(10 points)

Deadline expired on 10 November 2016.


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

Az első 2 pont megszerezhető a klasszikus pénzváltás probléma megoldásával (dinamikus programozás, \(\displaystyle O(N\cdot K)\)).

Mintamegoldás (2 pont, c++)

A következő 3 pont megszerzéséhez a következő megfigyelésre van szükségünk:

Ha növekvő sorrendbe rendezzük a pénzérméket, akkor ha \(\displaystyle k\) pénzérme után a legkisebb (pontosan) nem kifizethető összeg \(\displaystyle m_k\), és minden ennél nagyobb összeg kifizethető, akkor

ha \(\displaystyle e[k+1] > m_k\), akkor \(\displaystyle m_{k+1} = m_k\) továbbra is a legkisebb nem kifizethető érték, és ezután minden \(\displaystyle l>k\)-ra \(\displaystyle e[l] > m_k\), vagyis \(\displaystyle m_k\) továbbra sem kifizethető, így \(\displaystyle m_l = m_k\), vagyis az összes érmével nem kifizethető legkisebb összeg \(\displaystyle m_n = m_k\).

különben \(\displaystyle e[k+1] \leq m_k\), és mivel minden \(\displaystyle m_k\)-nál kisebb \(\displaystyle o\) összeg kifizethető az első \(\displaystyle k\) érmével, \(\displaystyle o+e[k+1]\) kifizethető az első \(\displaystyle k+1\) érmével, így minden \(\displaystyle m_k+e[k+1]\)-nél kisebb összeg kifizethető lesz. De mivel az előző pontban leírtak alapján az összes eddigi érmével ugyanez volt a helyzet, \(\displaystyle e[1] + e[2] + \ldots + e[k] + e[k+1] = m_k-1 + e[k+1] = m_{k+1} - 1\), ahol \(\displaystyle m_{k+1} = m_k + e[k+1]\) (ezt teljes indukcióval bizonyíthatjuk). Viszont akkor \(\displaystyle m_{k+1}\) tényleg nem fizethető ki (mivel az összes eddigi érme összege kisebb, így egyszerűen nincs ennyi pénzünk).

A fenti feltételeket figyelembevéve kiszámíthatjuk \(\displaystyle m_n \)-t, és így minden \(\displaystyle m_n\)-nél nagyobb vagy egyenlő összegre NEM a válasz, minden \(\displaystyle m_n\)-nél kisebb összegre IGEN a válasz.

A mintamegoldás \(\displaystyle m_n - 1\)-et számolja ki.

Mintamegoldás (+3 pont, c++)

A teljes pontszámért az előző módszert kell általánosítanunk. Itt nem rendezhetjük az érméket. Ehelyett szintén ki fogjuk számolni \(\displaystyle m_k\)-t minden \(\displaystyle k\)-ra, viszont a fel nem használt érméket (amelyek túl nagyok voltak), ``félrarakjuk", amíg túl nagyok. Erre a célra egy olyan adatszerkezet kell, amibe beilleszthetünk elemeket, illetve kivehetjük a legkisebbet hatékonyan. Ilyen adatszerkezet a kupac és a bináris keresőfa (implementációk: heap, set, priorityqueue; viszont kupacot magunk is implementálhatunk). Mivel minden érmét maximum egyszer adunk az adatszerkezethez, illetve maximum egyszer törlünk, összesen \(\displaystyle 2\cdot N\) műveletet végzünk az adatszerkezeten, így kellően hatékony implementációt használva \(\displaystyle O(N\cdot log(N))\) futási idő, és \(\displaystyle O(N)\) memóriahasználat elérhető.

teljes megoldás (c++)


Statistics on problem S. 110.
15 students sent a solution.
10 points:Busa 423 Máté, Csenger Géza, Kiss Gergely, Németh 123 Balázs, Noszály Áron.
7 points:1 student.
6 points:2 students.
5 points:1 student.
3 points:1 student.
2 points:2 students.
1 point:3 students.


  • 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