Cada año, desde hace dos, la empresa Tuenti plantea un reto algorítmico en su página web con el objetivo de “cazar talentos”. En esta página web pueden verse las veinte preguntas de este año: https://contest.tuenti.net/.

La siguiente es una de las preguntas del reto del año pasado.

You are trying to solve a very complex problem. In order to simplify it, you have divided it into many sub tasks. Most of these sub-tasks can be run in parallel, but some are dependent on the previous resolution of other tasks. There is no limit on the number of tasks that can be run in parallel. Each task has an associated computation time.

You are be given a subset of these tasks. For each of them you need to specify what is the minimal computation time for resolving the task (you must consider task dependencies).

The relations between the tasks are represented in the file contained in this archive: in.zip. This file is in the following format:

#Number of tasks
n

#Task duration <- task x has an associated computation time of tx
x,tx

#Task dependencies <- the resolution of task x depends of previously
#                     solving tasks y,z,w
x,y,z,w

It is imposible for two different tasks to be dependent on the resolution of one common task:

#Task dependencies <- this is not valid
x,y
z,y

The expected output is the following format: taskId taskComputationTime

x tx
y ty
z tz

From the standard input you will receive a set of tasks for which to compute the total time in the following format:

x,y,z

Sample input file

#Number of tasks
6

#Task duration
0,2
1,3
2,4
3,9
4,7
5,9

#Task dependencies
0,4
3,0,1,2
4,5

Sample standard input for tasks to compute time

3,1,4

Sample output

3 27
1 3
4 16

Como veréis, si lo pensáis un poco, la solución no es difícil en este caso. Pero se pueden plantear problemas de planificación de tareas cuya solución es algo más complicada. Alguno de ellos veremos en la asignatura…