Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution E - Bigger Picture

E. Bigger Picture

Score: 1

CPU: 3s
Memory: 1200MB

In our country, sometimes organizers organize competition keeping a “big picture” in mind. They don’t care about the fairness of a competition. They just see that “lots of people got aware.” And that’s a great achievement for them while a good participant’s morale may get hurt by the unfairness but that gives the least amount of headache to the organizers. So, let’s organize a competition ourselves with a bigger picture in mind. There are n rooms in the competition arena. We are given the number of participants in each room. If we are to choose the first, we will look for the room with the maximum number of participants, in the case of more than one such room, we choose the room with the minimum id among the ones with maximum number of participants. After choosing the room, we randomly remove one participant from that room. Then we proceed on in the similar fashion until we rank all the participants. For example, suppose there are 3 rooms with 2, 1 and 3 participants respectively:
Number of participantsSelected room (1 based)
2, 1, 33 (first came from 3rd room)
2, 1, 21 (second from 1st room)
1, 1, 23 (third from 3rd room)
1, 1, 11 (forth from 1st room)
0, 1, 12 (fifth from 2nd room)
0, 0, 13 (sixth from 3rd room)
0, 0, 0No participants are left

Given n and the number of participants in each of these n rooms. For the given K, find the room from where the K’th participant will be chosen from.

Input

First line of the input will be T (≤ 20), number of test cases. Hence T cases will follow.
First line of the test case will contain two numbers: n and m (1 ≤ n ≤ 100,000, 1 ≤ m ≤ 1000). Second line will contain n non-negative numbers, each not exceeding 1,000,000,000,000. The i’th of these numbers denote number of participants in the i’th room. Third line will contain m numbers, each denoting a K (1 ≤ K ≤ total number of participants). The K’s in a test case would be distinct.

Output

For each test case first print the case number, followed by m answers to the given queries. For details of the output format please check the sample input/output.

Sample

InputOutput
3 3 6 2 1 3 4 3 1 6 2 5 5 3 2 5 2 5 1 7 8 9 5 1 1 2 3 4 5 1 Case 1: 1 3 3 3 1 2 Case 2: 1 2 3 Case 3: 5
*Warning: Large I/O file, user faster input output functions.









Comments

Popular posts from this blog

Solution - Codeforces Problem 327B - Hungry Sequence

Solution - Timus Problem 1293. Eniya

Solution - Timus Problem 1409. Two Gangsters