problem.txt (1663B)
1 A. Subset Selecting 2 time limit per test1 second 3 memory limit per test256 megabytes 4 Olivia Rodrigo - the cure 5 You are given an array a 6 of n 7 integers and a positive integer k 8 . 9 10 You want to split some of the elements of a 11 into groups S1,S2,…,Sm 12 (m≥0 13 ) such that: 14 15 each group contains at least k 16 elements; 17 each element of a 18 belongs to at most one group (an element may also belong to no group at all). 19 Find the maximum possible value of mex({max(S1),max(S2),…,max(Sm)}) 20 over all valid ways to form the groups, where mex(c) 21 denotes the smallest non-negative integer that does not appear in the collection c 22 . If m=0 23 , the collection is empty and mex({})=0 24 . 25 26 Input 27 Each test contains multiple test cases. The first line contains the number of test cases t 28 (1≤t≤500 29 ). The description of the test cases follows. 30 31 The first line of each test case contains two integers n 32 and k 33 (1≤k≤n≤100 34 ) — the length of the array a 35 and the minimum allowed size of each group. 36 37 The second line of each test case contains n 38 integers a1,a2,…,an 39 (0≤ai≤n 40 ) — the elements of the array a 41 . 42 43 Output 44 For each test case, output a single integer — the maximum possible value of mex({max(S1),max(S2),…,max(Sm)}) 45 over all valid ways to form the groups. 46 47 --- 48 49 - a of n int 50 - postiive k 51 - S_1, ... S_n 52 - groups such that 53 - each group has at least k elements 54 - each element belongs to at most one group 55 - find mex(max(S_1) + ... ) 56 - where mex is the smallest non-zero integer that doesn't appear in the collection c 57 58 --- 59 60 3 1 61 0 2 1 62 63 n = 3 64 k = 1 65 66 67 68 --- 69 70 4 2 71 1 2 3 4 72 73 5 2 74 0 1 0 1 0 75 76 5 4 77 0 0 1 0 0 78 79 5 1 80 4 0 0 0 2 81 82 6 2 83 0 0 2 1 0 0 84