Az S. 168. feladat (2023. február)

S. 168. Egy leegyszerűsített felvételi eljárásban minden felvételiző legfeljebb 6 egyetemi szakra adhatja le a jelentkezését. Mindenki a saját listáján szereplő sorrend szerint szeretne bekerülni az adott képzésekre. Ha az első helyről elutasítják, akkor a második helyre kerül, ha a másodiktól is elutasítják, akkor a harmadikra stb. Ha egyik szakra sem veszik fel, akkor nem mehet egyetemre. Mivel a képzések pontszámítási rendszere eltérhet, ezért a felvételiző pontját minden szakra külön meg kell adni.

A felvételi a ponthatárok meghúzásával történik. Minden egyetem minden szakra megad egy ponthatárt. Ha egy felvételiző a ponthatárnál nagyobb vagy egyenlő pontszámot ért el, és a listájában előbb lévő szakokra nem vették fel, akkor az adott szakra veszik fel. Ha valakit több helyre is felvennének a pontjai alapján, akkor is csak a listájában legelöl lévő szakra iratkozhat be.

A ponthatárokat úgy kell meghúzni, hogy azok mindenhol a lehető legalacsonyabbak legyenek, de az egyetem ne lépje át az egyes szakokra kiszabott kvótát, azaz ne vegyen fel adott számú hallgatónál többet. Fontos szabály, hogy az azonos pontszámú hallgatókat csak együtt lehet felvenni, illetve elutasítani.

Adott az összes felvételiző preferencialistája a kiszámított felvételi pontokkal együtt és a szakok kvótái. Adjuk meg, melyik a legalacsonyabb ponthatár, amivel még valamelyik szakra be lehet kerülni, valamint adjuk meg, hogy hány felvételizőt nem vettek fel sehova.

A bemenet első sorában a felvételizők száma, \(\displaystyle F\) és az egyetemi szakok \(\displaystyle E\) száma szerepel. A következő \(\displaystyle F\) sor mindegyikében egy-egy felvételiző preferenciasorrendje, azaz legfeljebb 6 számpár szerepel. Minden számpár első tagja a szak sorszáma, a második tagja pedig a felvételiző pontszáma arra a szakra. A következő sorban a szakok \(\displaystyle E\) száma szerepel. Az alatta lévő sorban \(\displaystyle E\) szám szerepel. Az \(\displaystyle i\)-edik szám az \(\displaystyle i\)-edik szak kvótája, amit a felvettek száma nem léphet át.

A kimenet első sorába a legalacsonyabb ponthatárt kell írni. A kimenet második sorába azon felvételizők száma kerüljön, akik nem jutottak be sehova.

Példa:

Magyarázat: az első szakra az első két felvételiző jut be. A harmadik lemarad az első szakról, így kiejti a negyedik felvételizőt a második szakról.

Korlátok: \(\displaystyle 1\le F \le 10\,000\), \(\displaystyle 1\le E \le 1000\). Az egyetemek 1-től \(\displaystyle E\)-ig sorszámozottak. A pontszám 0 és 500 közötti egész szám. Időkorlát: 1 mp.

Értékelés: a pontok 40%-a kapható, ha a program helyes kimenetet ad az \(\displaystyle F, E\le 100\) bemenetekre.

Beküldendő egy s168.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2023. március 16-án LEJÁRT.

Statisztika:

1 dolgozat érkezett.
10 pontot kapott:	Zádor-Nagy Zsombor.

A KöMaL 2023. februári informatika feladatai