HELPR2D2 - Help R2-D2!
In Episode III of Star Wars (whose alleged title is "How I became Vader"), R2-D2 (Artoo-Detoo) is again confronted to a tedious work. He is responsible for the loading of the republic transport starships in the fastest way. Imagine a huge space area where n starships are parked. Each starship has a capacity of K cubic femtoparsec. Containers Ci arrive one at a time with some volume vi (expressed in cubic femtoparsec). R2-D2 wants to minimize the number of starships used for a given sequence of containers.
Smart as he is, R2-D2 knows for sure that the problem is a hard one, even with the force being around. Here is the heuristics he selected to solve his problem. Start with all starships ready to load, and numbered S0,S1,etc. When a container Cj arrives, select the starship of minimal index i that can contain Cj and put it in Si. In some sense, this heuristic minimizes the move of the container arriving before its loading.
At the end of the n arrivals, R2-D2 counts the number s of starships used and he measures the total waste w of the sequence. For i=0..s-1, the waste in starship i is given by the unused volume.
Your task is to simulate the algorithm of R2-D2.
Input
The first line of the input contains a number T ≤ 10 that indicates the number of test cases to follow. Each test case begins with K on a line (K ≤ 1000), followed by the number of containers in the sequence, n, on the second line (1 ≤ n ≤ 1000000). There are two possible formats for the remaining lines. If it contains one integer, then this is the next vi. If it begins with the character b (for block), it is followed by 2 integers r and v. This means that the r next containers arriving have volume v.
Output
Your program must output the number s of starships used, followed by a blank, followed by the total waste w.
You can assume, that at most 100000 starships are needed, and R2-D2 has to change the starships in which the next container is loaded at most 100000 times.
Example
Input: 2 100 3 50 25 70 100 4 50 b 2 40 20 Output: 2 55 2 50
hide comments
onlyerror:
2022-07-02 20:08:07
solve cses hotel queries |
|
yaseenmollik:
2020-08-09 20:27:13
Segment Tree +Binary Search :D |
|
sawchawn:
2020-05-13 19:19:13
could you have written a longer problem statement! fed up |
|
tri_cep1:
2020-04-20 17:54:14
why tf time limit is 7 sec |
|
coolio_1:
2020-02-26 19:31:16
Was afraid of this problem when I read it initially. Ended up solving it in 1 go with Seg tree. Also, interesting i/p format :) |
|
thekidnamedme:
2018-09-27 21:14:35
Ok so something weird is happening, SPOJ always seems to replace one instance of a variable that happens to be in a scanf statement by a stray '×' character regardless of whether the code gives a wa or an ac. Really curious to know why this is happening :/ |
|
luka_dzimba911:
2018-08-09 11:46:46
334 lines , modified AVL tree , 3 days , ugliest code ever
|
|
anubhawiiitu:
2017-12-24 15:51:36
Not so good problem due to ample time(7s) |
|
sxie12:
2017-07-06 18:37:59
Use scanf and printf if you're using C++. |
|
Vineet Setia:
2016-06-05 21:59:40
how can we know if input is int or char ? |
Added by: | Adrian Kuegel |
Date: | 2004-07-14 |
Time limit: | 7s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | ACM Southwestern European Regional Contest, Paris 2003 |