National Olympiad in Informatics, China, 1999
Memory is an important resource of computers, and running processes require memory to be allocated for them.
The classic memory allocation process is as follows:
- The minimally addressable storage unit is the most basic unit for
memory. Each storage unit is identified using a certain integer
which is known as the address. Addresses begin at 0 and go up
consecutively. Storage units with consecutive addresses are
considered logically contiguous. We shall call the
contiguous storage units starting at address the memory block at of length . - While the computer is running, there may be several processes that
will need to take up memory. Each process will have a requested time
, the number of storage units and the running time . Within the running duration (the process starts at and terminates at ), the occupied storage units will not be accessible to any other process. - If at time
there is a process requesting storage units with a running time , then:- If at time
there exists an unused memory block of length , then the system will assign these storage units to the process. If there are multiple length blocks, then the system will assign the process the block with the smallest initial address. - If at time
there does not exist an unused memory block of length , then the process will be placed in a waiting queue. Regarding the process at the head of the waiting queue, if at any time there exists an unused memory block of its requested size , then the system will immediately remove the process from the waiting queue and allocate this block to it. Note that while allocating memory, the process at the head of the queue has the highest priority, and no other processes in the queue may be dealt with before this process.
- If at time
Given information about the processes, please write a program that simulates the memory allocation of the system.
Input Specification
The first line of input is an integer
Starting at the second line of input, each line will describe a single
process with three integers
The processes will be given in increasing order of
The last line of input is denoted by three zeros.
There are at most
Adjacent values on the same line of the input will be separated by one or more spaces.
Output Specification
The output should contain two lines.
The first line should contain the time at which all processes terminate.
The second line should contain the total number of processes that have been placed in the waiting queue.
Sample Input
10
1 3 10
2 4 3
3 4 4
4 1 4
5 3 4
0 0 0
Sample Output
12
2
Explanation
Time |
Memory Usage Status | Description | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
1 | Process A requests memory | ||||||||||
2 | Process B requests memory | ||||||||||
3 | Process C requests memory | ||||||||||
4 | Process D requests memory | ||||||||||
5 | Process B terminated with its memory freed up. Process C is removed from the queue and memory is allocated. Process E requests memory | ||||||||||
6 | |||||||||||
7 | |||||||||||
8 | Process D terminated with its memory freed up. Process E is removed from the queue and memory is allocated. | ||||||||||
9 | Process C terminated with its memory freed up. | ||||||||||
10 | |||||||||||
11 | Process A terminated with its memory freed up. | ||||||||||
12 | Process E terminated with its memory freed up. |
Problem translated to English by .
Comments