Programozás‎ > ‎Feladatok‎ > ‎

Gépek

Egy vállalkozó a következő N napra megrendeléseket fogad. Minden munkát egy nap alatt tud elvégezni. M megrendelés érkezett, minden megrendelésben szerepel, hogy az igényelt munkát milyen határidőig kell elvégezni. A vállalkozónak ki kell számítani, hogy legkevesebb
hány gépre van szükség, hogy minden igényelt munkát határidőre el tudjon végezni. 

Feladat

Írjunk programot, ami kiszámítja, hogy legkevesebb hány gép kell ahhoz, hogy minden megrendelt munkát határidőre el tudjon végezni a vállalkozó! A program adja is meg, hogy ez egyes megrendelést melyik napon, melyik gépen végezze el a vállalkozó!

Bemenet

A gepek.be szöveges állomány első sora két egész számot tartalmaz, a munkanapok N számát (1 <= N <= 10 000), és a megrendelések M számát (1 <= M <= 100 000). A második sor pontosan M egész számot tartalmaz egy-egy szóközzel elválasztva. Az i-edik szám az i-edik megrendelés határideje. Minden h határidőre teljesül, hogy 1 <= h <= N. 

Kimenet

A gepek.ki szöveges állományba M+1 sort kell írni! Az első sor a minimálisan szükséges gépek G számát tartalmazza! A további M sor tartalmazza az igényelt munkák beosztását az igények sorszáma szerinti sorrendben! Minden sor két számot tartalmazzon, egy szóközzel
elválasztva, az első szám annak a napnak a sorszáma legyen, amelyik napon a munkát elvégzik, a második szám pedig annak a gépnek a sorszáma legyen, amelyiken a munkát elvégzik! Több megoldás esetén bármelyik megadható. 

Példa

Bemenet  Kimenet
10 8
3 2 3 2 4 5 6 2
2
2 2
1 1
3 1
2 1
3 2
4 1
4 2
1 2


Tesztadatok

Címkék

A feladat forrása: NTOITV 2013-2014, 2. forduló, 11-13. évfolyam
Algoritmusok: