algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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