ACMCEG2C - Pick the candies

Pick the Candies

Many children went to a sweet shop. There were n candy varieties and each variety is kept in a separate bowl. The sweetness of each variety is written on the bowl. All the children wanted the candy with highest sweetness value. As there are only limited candies in each variety, the shop keeper makes a rule. According to the rule, the shopkeeper will show selectively chosen k varieties to every children. The children can pick any one of those varieties and move away. To make it easy for him, the shop keeper shows the

varieties 1,2,...,k to children1,

varieties 2,3,…,k+1 to children2,

varieties 3,4,…,k+2 to children3 and so on..

All the children are good at math. Find what variety each child will choose.

Input Specification:

The first line contains an integer t, the number of test cases. For each test case the input consists of two lines. The first line contains two integers n(number of candy varieties) and k. The next line contains n number of integers, the sweetness values of all the candy varieties.

Output Specification:

For each test case, print the candy varieties chosen by the children.

Input Constraints:

1<=t<=1000

1<=n<=10000

1<=k<=n

0<=Sweetness value<=10000

Sample Input:

5 3

1 2 3 4 5

4 2

7 1 6 8

9 5

7 14 3 0 2 2 2 2 2

Sample Output:

3 4 5

7 6 8

14 14 3 2 2

Hint: use deque

Submit solution!

Added by:	cegprakash
Date:	2012-03-30
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: BF GOSU

hide comments

2017-04-12 01:54:47
[removed non English comment]

Last edit: 2017-08-02 13:19:00

2017-03-08 20:04:48
AC in 1 go :-)

2017-02-27 11:13:09 cegprakash
omg Shakir

2017-02-12 21:14:13 S. M. Shakir Ahsan Romeo
Solved by segment tree :P

2016-09-11 09:39:12 Glenda Emanuella Sutanto
@sharif ullah :
for example the 2nd testcase
n = 4, k = 2, the sweetness values :
7 1 6 8
the 1st children will be shown : 7 1 by the teacher so he will choose 7
the 2nd children will be shown: 1 6 by the teacher so he will choose 6
the 3rd children will be shown: 6 8 by the teacher so he will choose 8

so the output :
7 6 8

:)

2015-05-25 11:45:51 sharif ullah
i cannot understand the problem statement .even the inputs

2014-07-19 06:39:52 dabuu
why i m getting WA in 3 test case ? Please Check

2012-12-17 10:56:16 lavish goel
Ok I got it sorry :):)

2012-12-17 10:53:24 lavish goel
How many children are there? :(:(