NézetNyomtat

Építkezés (Megoldás)
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.BEEPITKEZ.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 106 1 2 5 8 3 6 4 7 9 10

Tesztadatok