Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem S. 14. (January 2006)

S. 14. The construction of a certain machine in a factory is divided into several phases. The number of minutes needed to complete a phase is known, together with the information which phases are required to precede that phase. Phases that are independent of one another can be performed simultaneously.

Make a schedule how to construct the machine so that the construction time is minimized, in a form that the starting minute for each phase is given.

The input consists of some positive integers encoding the phases. The first line contains the number of phases. Each subsequent line contains the name of a phase (also a number), its length (a positive integer), then the number of those phases on which the actual phase depends, finally their names separated by a space.

The first line of the output should contain the total construction time, then in each line the name of a phase together with its starting time, separated by a space.

See the example.

The source code of the program (s14.pas, s14.cpp, ...) should be submitted.

(10 pont)

Deadline expired on February 15, 2006.


12 students sent a solution.
10 points:Csorba Sebestyén, Engedy Balázs, Grósz Dániel, Homolya Miklós, Kiss Dániel Miklós, Monszpart Áron, Nikházy László, Treszkai László, Ureczky Bálint.
8 points:2 students.
3 points:1 student.

Problems in Information Technology of KöMaL, January 2006