50082. Two Machines

I'm a slow walker, but I never walk backwards.

Write a program to compute the completion time of a series of tasks going through two machines.

Task Description

We are given a sequence of tasks, which will go through two machines A and B sequentially. A task must first go through machine A, then through machine B. One machine can only process one task at a time, but two machines can process different tasks in parallel. Each task has an arrival time, the time it takes on machine A, and the time it takes on machine B. A task can start only when it arrives, and we must process the task in the time order they arrive. The tasks arriving at the same time are processed according to the order they appear in the input.

figurefigure

Arrival Time Time takes on machine A Time takes on machine B Completion Time
Task 1 0 8 5 13
Task 2 15 10 5 30
Task 3 20 2 10 40

We use an example to illustrate the task execution. Assume that there are three tasks. As the figure and table shown above. Task 1 arrived at time 0, task 2 arrived at time 15, and task 3 arrived at time 20. The time task 1, task 2 and task 3 need on machine A are 8, 10 and 2, respectively. The time task 1, task 2 and task 3 need on machine B are 5, 5 and 10, respectively.

To compute the completion time of these three tasks, the program should do the following:

  • Task 1 is ready to start at time 0. Since machine A and B are both available at time 0, the completion time of task 1 is (8 + 5) = 13.
  • Task 2 arrived at time 15, so it is ready to start at time 15. Since both machine A and B are available, its completion time is (15 + 10 + 5) = 30.
  • Task 3 arrived at time 20. It cannot start at machine A at time 20 because A was processing task 2. Task 3 needs to wait until task 2 finishes on machine A and machine A becomes available, which happened at time 25. Hence, task 3 was ready to start at time 25 on machine A. After task 3 completed on machine A, it cannot start on machine B immediately. it has to wait for machine B to finish task 2, which happened at time 30. Therefore, the completion time of task 3 is (30+10) = 40.

Write a program to simulate the task execution and print the completion time of all tasks. It is guaranteed that there is at least one task.

Subtask

  • 20 points: All tasks arrive at time 0 and the time it takes on machine B is all 0 for all tasks.
  • 40 points: All tasks arrive at time 0.
  • 40 points: Tasks may arrive at different time. The arrival time in the input is in non-decreasing order.

Note

Do not use array for this problem. You can solve this problem with very little memory. We will make sure that you will not have enough memory, and see the "memory limit exceeded" error, if you use array.

Input Format

The input contains information of tasks. Each line has the arrival time, time on machine A, and time on machine B of each task. The number of tasks is at least one.

Output Format

Print the completion time for each task in a line.

Hint

You need to use two variables to keep track of the ready time of machine A and B. That is, you need to remember when the machine can process the next task, after processing the current task. Note that both machines A and B are ready to process tasks at time 0 initially. Now after given a task, how do you update the ready time for A and B after they process the task?

Sample Input 1

0 2 0
0 4 0
0 6 0
0 8 0
0 4 0

Sample Output 1

2
6
12
20
24

Sample Input 2

0 2 1
0 3 2
0 7 1
0 8 3
0 1 10

Sample Output 2

3
7
13
23
33

Sample Input 3

1 2 1
3 3 2
5 7 1
7 8 3
9 1 10

Sample Output 3

4
8
14
24
34

Discussion