Építkezés
(Megoldás)
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2002 > Döntő > 11-13. osztály
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2002 > Döntő > 11-13. osztály
Építkezés
A feladat szövege
Egy építkezés befejezéséhez N különböző munkát kell elvégezni. Minden munka pontosan egy nap alatt teljesíthető. A terv alapján tudjuk, hogy bizonyos munkákat előbb kell elvégezni, mint másokat. Pontosabban, a terv (A, B) párok halmazát tartalmazza, ahol az (A, B) pár azt jelenti, hogy az A munkát előbb kell elvégezni, mint a B munkát. Vannak olyan speciális munkák is, amelyekből egy nap csak egy végezhető el, ráadásul csak a megadott sorrendben (de nem feltétlenül egymást követő napokon).
Feladat:
Írj programot, (EPITKEZ.PAS, EPITKEZ.C vagy EPITKEZ.CPP), amely
- A. kiszámítja, hogy legkevesebb hány nap kell az összes munka elvégzéséhez;
- B. megadja a munkáknak egy olyan beosztását, amely szerint minden munka a lehető legkorábban végezhető el a követelmények teljesülése mellett.
Bemenet:
Az EPITKEZ.BE állomány első sora az N, K és T egész számokat tartalmazza. N az elvégzendő munkák száma (1<=N<=200), az egyes munkákat az 1, ..., N számokkal azonosítjuk. K (1<=K<=N) a speciális munkák száma. A T tervben megadott megelőzési párok száma (1<=T<=10000). A második sor pontosan K egész számot tartalmaz egy-egy szóközzel elválasztva, minden szám egy-egy speciális munka sorszáma. A további T sor mindegyikében két egész szám van: A, B (1<=A<=N, 1<=B<=N), ami azt jelenti, hogy az A munkát előbb kell elvégezni, mint a B-t.
Kimenet:
Az EPITKEZ.KI állomány első sorába egy egész számot kell írni: annak a lehető legrövidebb időnek a napokban mért hosszát, amely alatt az összes munkát el lehet végezni. Ezt követően az állományban pontosan M sornak kell lennie. Az állomány (i+1)-edik sora azon munkák sorszámát tartalmazza, egy-egy szóközzel elválasztva, amelyeket legkorábban az i-edik napon lehet és kell elvégezni. Ha nem lehet a tervben megadott feltételeket teljesíteni, akkor az első sorba 0-t kell írni.
Példa:
| EPITKEZ.BE | EPITKEZ.KI |
| 10 3 11 1 2 8 1 3 3 4 1 5 5 3 3 7 5 6 1 8 8 6 6 9 9 10 7 10 | 6 1 2 5 8 3 6 4 7 9 10 |