2111D.md (3410B)
1 Source: https://codeforces.com/problemset/problem/2111/D 2 3 D. Creating a Schedule 4 5 time limit per test 6 7 2.5 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A new semester is about to begin, and it is necessary to create a schedule for the first day. There are a total of $n$ groups and $m$ classrooms in the faculty. It is also known that each group has exactly $6$ classes on the first day, and the $k$-th class of each group takes place at the same time. Each class must be held in a classroom, and at the same time, there cannot be classes for more than one group in the same classroom. 22 23 Each classroom has its own index (at least three digits), and all digits of this index, except for the last two, indicate the floor on which the classroom is located. For example, classroom $479$ is located on the $4$-th floor, while classroom $31415$ is on the $314$-th floor. Between floors, one can move by stairs; for any floor $x \gt 1$, one can either go down to floor $x - 1$ or go up to floor $x + 1$; from the first floor, one can only go up to the second; from the floor $10^7$ (which is the last one), it is possible to go only to the floor $9999999$. 24 25 The faculty's dean's office has decided to create the schedule in such a way that students move as much as possible between floors, meaning that the total number of movements between floors across all groups should be maximized. When the students move from one floor to another floor, they take the shortest path. 26 27 For example, if there are $n = 2$ groups and $m = 4$ classrooms $[479, 290, 478, 293]$, the schedule can be arranged as follows: 28 29 | | | | 30 | --- | --- | --- | 31 | Class No. | Group 1 | Group 2 | 32 | $1$ | $290$ | $293$ | 33 | $2$ | $478$ | $479$ | 34 | $3$ | $293$ | $290$ | 35 | $4$ | $479$ | $478$ | 36 | $5$ | $293$ | $290$ | 37 | $6$ | $479$ | $478$ | 38 39 In such a schedule, the groups will move between the $2$nd and $4$th floors each time, resulting in a total of $20$ movements between floors. 40 41 Help the dean's office create any suitable schedule! 42 43 Input 44 45 Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^{3}$) — the number of test cases. The description of the test cases follows. 46 47 The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le m \le 10^{5}$) — the number of groups and the number of available classrooms. 48 49 The second line of each test case contains $m$ integers $a_{i}$ ($100 \le a_{i} \lt 10^{9}$) — the indices of the available classrooms. 50 51 Additional constraints on the input: 52 53 * the numbers of all classrooms are pairwise distinct; 54 * the sum of $m$ across all test cases does not exceed $10^{5}$. 55 56 Output 57 58 For each test case, output $n$ lines, where the $i$-th line should contain $6$ integers — the indices of the classrooms where the classes for the $i$-th group will be held. 59 60 Each classroom must be occupied by at most one group during the $k$-th class. 61 62 Example 63 64 Input 65 66 ``` 67 3 68 69 2 4 70 71 479 290 478 293 72 73 1 1 74 75 31415 76 77 6 10 78 79 479 385 290 293 384 383 297 478 291 382 80 ``` 81 82 Output 83 84 ``` 85 290 478 293 479 293 479 86 293 479 290 478 290 478 87 31415 31415 31415 31415 31415 31415 88 479 290 479 290 479 290 89 290 479 290 479 290 479 90 293 478 293 478 293 478 91 297 385 297 385 297 385 92 478 293 478 293 478 293 93 291 384 291 384 291 384 94 ``` 95 96 Note 97 98 In the third test case, the maximum number of moves between classrooms is $50$.