MEMDIS - Memory Distribution

no tags 

EMS memory (called memory for short) is some important resource of a computer. When a program is running, the computer must distribute the memory for it.

The classical memory distribution process is like the following:

  • The basic unit of the memory is called a cell, each cell is assigned to a fixed integer number called its address. The address starts from number 0. If two cells' address numbers are two consecutive integer numbers, the two cells are called (logically) consecutive. We name the s consecutive cells starting from address i a piece whose length is s and first address is i.
  • Many programs need memory during their running. For each program, we need an application time X, a number of cells needed M and a running time P to describe it. While the program is running (during its start running time T to T + P, including the left end and excluding the right end), the M cells cannot be used by other programs.
  • Suppose a program apply M cells at time X and its running time is P, then
    • (A) If there is a piece in the memory at time X, each cell of which is not being used, and whose length is M, the computer will distribute these M cells to this program. If there are more pieces, the computer will choose the one whose first address is minimum.
    • (B) If such piece does not exist at time X, the program will be put into a queue. If after some time, there exist a piece whose length is M and the corresponding program is at the head of the queue, the computer will pop this program and distribute memory for it like (A) immediately. During the process of memory distribution, the programs which are not at the head of the queue cannot start to run before the one at the head of the queue.

Input

Ten test cases (given one after another, you have to process all!) For each test case:

The first line is a number N, which shows the number of memory cells. Their addresses are 0..n-1. Fewer than 10000 lines follow, each contains 3 integers X, M (M ≤ N), P describing the programs. A line containing three zeroes denotes the end of a test case. The programs have been sorted by their application time X.

All numbers in the input and output file will be less than 109.

Output

For each test case output two lines. The first line contains a single integer, which shows the time when all the programs have been run and stops normally. The second line contains a single integer, which is the number of programs which have been put into the queue.

Example

Input:
10
1 3 10
2 4 3
3 4 4
4 1 4
5 3 4
0 0 0
[and 9 test cases more]

Output:
12
2
[and 9 test cases more]

hide comments
Brian Bi: 2024-12-01 03:07:44

From my write-up:

Based on the sample data, if a program finishes running at time T, then a
program that has been queued up takes priority over a new program whose X
value is T. Also, when multiple programs finish running at the same time T,
no program can be removed from the queue and scheduled at time T until all
programs finishing at time T have freed their memory.

Simes: 2024-11-10 10:05:10

@Brian Bi. Now that you've got AC, what's the answer to your question?

Brian Bi: 2024-10-24 06:02:58

What's supposed to happen if, at the exact time when memory becomes available to the program at the head of the queue, that's also the value of X for one of the programs in the input? Which one gets priority?


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 1999,Day 2; translated by Blue Mary