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

 

Problem S. 110. (October 2016)

S. 110. 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

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:

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.

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