Programozás‎ > ‎Feladatok‎ > ‎

Beruházás

Egy nagyszabású beruházás terve N különböző munka elvégzését írja elő. Minden munkát pontosan egy nap alatt lehet elvégezni, azonban minden munkára elő van írva az a határidő, ameddig el kell végezni. A beruházó a munkák elvégzésére alvállalkozókat szerződtet. Minden alvállalkozó bármely munkát el tudja végezni, de egy nap csak egy munkát tud végezni. 

Feladat

Készíts programot, amely megadja, hogy legkevesebb hány alvállalkozót kell szerződtetni, hogy minden munkát határidőre elvégezzék! A munkák egy ütemezését is meg kell adni.

Bemenet

A standard bemenet első sorában az elvégzendő munkák száma van (2 ≤ N ≤ 10 000). A további N sor mindegyike egy pozitív egész számot tartalmaz egy munka határidejét (1 ≤ Hi ≤ 300).

Kimenet

A standard kimenet első sorába a legkevesebb alvállalkozók K számát kell írni, amennyivel minden munka elvégezhető határidőre! A következő N sor a munkák egy lehetséges beosztását tartalmazza! Az első szám a sorban egy munka (1 és N közötti) sorszáma, a második a munkát elvégző vállalkozó (1 és K közötti) sorszáma, a harmadik pedig annak a napnak a sorszáma legyen, amikor a munkát elvégzi a vállalkozó! Több megoldás esetén bármelyik megadható.

Példa

Bemenet  Kimenet
7
1
2
1
3
2
2
3
3
1 1 1
2 1 2
3 2 1
4 3 2
5 2 2
6 3 1
7 1 3


Tesztadatok

Csatolmányként

Címkék

A feladat forrása: Nemes Tihamér verseny, 2015-2016 2. forduló
Algoritmusok: 

megoldás