IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. IMPORTANTE: Por favor, no enviéis soluciones, pistas, o cualquier otra cosa que pueda echar a perder la resolución del problema hasta que hayan pasado por lo menos 60 horas desde el envío de este mensaje. Gracias. WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser Mail. Danke. VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i voobshe lyubye podskazki v techenie po krajnej mere 60 chasov ot daty etogo soobshenija. Spasibo. Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60 Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4 Xie4Lou4 Da2An4 De5 Jian4Yi4. Xie4Xie4. ---------------------------------------------------------------- You will write a program to perform scheduling. As we all know, tasks sometimes take longer than expected. Sometimes when this happens, the final deadline of the project is affected; sometimes it isn't. For example, consider the four tasks A, B, C, and D. B and C depend on A, which means that they cannot be started until A is finished. D depends on B and C, and cannot be started until both B and C are finished: .-> B . A :-> D `-> C ' Suppose we expect the four tasks to take the following times: A: 1 day B: 2 days C: 3 days D: 1 day Then we don't expect the project to be finished for at least 5 days: one day to complete A and start C; 3 days to complete C and start D, and another day to finish D. Any delay in any of the three tasks A, C, or D will cause the completion date to slip. We say that A, C, and D are on the "critical path". But B is not on the critical path, because B can go on while C is going on, and can take up to one day longer than expected without delaying the start of D. You will write a program which will calculate critical paths. The input to the program will be a file in the following format: A 1 B 2 A C 3 A D 1 B C FINAL 0 D Each line represents one task. The first field in each line is the name of the task. The second field is the expected duration. If there are any other fields, they are the names of other tasks which must be finished before this task can start. The program will find all the tasks on the critical path to the task named FINAL and will print them out, one per line. It may happen that the input specifies tasks that cannot possibly be completed. For example: A 1 B B 1 A FINAL 0 A B Here A can't start until B is finished, but B can't start until A is finished. In such cases, the program should diagnose an error. [ ADMINISTRATIVE NOTE: Last week's expert quiz turned out to be more subtle than it first appeared. The report and sample solution will be along when it is ready. Thanks for your patience. -MJD ]