Problem S. 110. (October 2016)
S. 110. 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
Az első 2 pont megszerezhető a klasszikus pénzváltás probléma megoldásával (dinamikus programozás, \(\displaystyle O(N\cdot K)\)).
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.
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ő.
Statistics:
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