K stacks and Plates
All submissions for this problem are available.
Chingam likes to collect plates because they remind him of food. But Jimma hates plates, because they make a lot of noise when they break. Chingam has a collection of N plates hidden behind Jimma's bed, so that she cannot find them. The plates are arranged in K stacks, such that each stack has at least one plate. The stacks are indexed from 0 to K-1. Where 0 is index of the leftmost stack and K-1 is the index of the rightmost stack.
Every plate has a weight w and a capacity c. These values might be different for different plates. A plate breaks when the sum of weights of the plates kept above it exceeds its capacity.
Whenever Chingam finds a new plate, he adds it to one of the K stacks. The plate is always added to the top. After he does this, some of the plates in that stack break. As Jimma is always sleeping and plotting world domination, if too many plates break at the same time, she will wake up and scratch Chingam. So Chingam will always choose the stack which minimize the number of plates that break and hope that the noise is not too loud. If there are multiple ways to do that, then he will place the plate in the leftmost such stack. Chingam is not very good at counting and he cannot always find the best stack on his own. Please help him!
You are given the initial arrangement of N plates in the stacks and Q queries. Query i describes a plate with capacity C[i] and weight W[i]. You have to tell Chingam the index of the best stack for this plate and the number of plates which break after this plate is added to that stack.
Chingam will then add the plate to that stack.
The plates should be added in the order they appear in the queries.
A plate can break only once and its weight does not change after it breaks.
It is guaranteed that there are no broken plates in the initial arrangement; i.e. for every plate, the sum of plates on top of it will not exceed its capacity.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains the integer K and is followed by K lines.
- The ith such line describes the ith stack. The first integer on that line is n[i] the number of plates in that stack and is followed by 2*n[i] space separated integers. The 2*jth and 2*j+1th integers on that line give the capacity and the weight repectively, of the jth plate from the bottom.
- The next line contains an integer Q, the number of queries and is followed by Q lines
- Each of these lines contain two space separated integers, the capacity and the weight of the plate in that query.
- For each test case, output Q lines, one for each query. Each line should contain two integers - the first integer should be the index of the best plate for that query and the second integer should be the number of plates which break in that query.
- 1 ≤ T ≤ 3
- 1 ≤ K ≤ 5*104
- 1 ≤ Q ≤ 105
- The total number of plates (Q+N) in each test case will not exceed 105.
- All the weights and capacities are positive integers and do not exceed 109
Input: 1 3 2 5 10 3 3 2 7 15 2 1 1 2 8 2 3 4 9 5 Output: 1 1 2 1
Example case 1. There are 3 stacks and 2 queries. The first query has a plate of capacity 3 and weight 4. Placing that plate in the stack numbered 0 will break both the plates in that stack. Placing it in one of the other two stacks breaks only one plate. Chingam should place it in the leftmost stack, hence the output is 1 1.
Now stack 1 has three plates and one of them is broken. Placing the next plate in either stack 0 or 1 will break two plates, while placing it in stack 2 will break only one. Hence the output is 2 1
|Time Limit:||6 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions