1517B.md (2758B)
1 Source: https://codeforces.com/problemset/problem/1517/B 2 3 B. Morning Jogging 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The 2050 volunteers are organizing the "Run! Chase the Rising Sun" activity. Starting on Apr 25 at 7:30 am, runners will complete the 6km trail around the Yunqi town. 22 23 There are $n+1$ checkpoints on the trail. They are numbered by $0$, $1$, ..., $n$. A runner must start at checkpoint $0$ and finish at checkpoint $n$. No checkpoint is skippable — he must run from checkpoint $0$ to checkpoint $1$, then from checkpoint $1$ to checkpoint $2$ and so on. Look at the picture in notes section for clarification. 24 25 Between any two adjacent checkpoints, there are $m$ different paths to choose. For any $1\le i\le n$, to run from checkpoint $i-1$ to checkpoint $i$, a runner can choose exactly one from the $m$ possible paths. The length of the $j$-th path between checkpoint $i-1$ and $i$ is $b_{i,j}$ for any $1\le j\le m$ and $1\le i\le n$. 26 27 To test the trail, we have $m$ runners. Each runner must run from the checkpoint $0$ to the checkpoint $n$ once, visiting all the checkpoints. Every path between every pair of adjacent checkpoints needs to be ran by exactly one runner. If a runner chooses the path of length $l_i$ between checkpoint $i-1$ and $i$ ($1\le i\le n$), his tiredness is $$\min_{i=1}^n l_i,$$ i. e. the minimum length of the paths he takes. 28 29 Please arrange the paths of the $m$ runners to minimize the sum of tiredness of them. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). Description of the test cases follows. 34 35 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n,m \leq 100$). 36 37 The $i$-th of the next $n$ lines contains $m$ integers $b_{i,1}$, $b_{i,2}$, ..., $b_{i,m}$ ($1 \le b_{i,j} \le 10^9$). 38 39 It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10^4$. 40 41 Output 42 43 For each test case, output $n$ lines. The $j$-th number in the $i$-th line should contain the length of the path that runner $j$ chooses to run from checkpoint $i-1$ to checkpoint $i$. There should be exactly $m$ integers in the $i$-th line and these integers should form a permuatation of $b_{i, 1}$, ..., $b_{i, m}$ for all $1\le i\le n$. 44 45 If there are multiple answers, print any. 46 47 Example 48 49 Input 50 51 ``` 52 2 53 2 3 54 2 3 4 55 1 3 5 56 3 2 57 2 3 58 4 1 59 3 5 60 ``` 61 62 Output 63 64 ``` 65 2 3 4 66 5 3 1 67 2 3 68 4 1 69 3 5 70 ``` 71 72 Note 73 74 In the first case, the sum of tiredness is $\min(2,5) + \min(3,3) + \min(4,1) = 6$. 75 76  77 78 In the second case, the sum of tiredness is $\min(2,4,3) + \min(3,1,5) = 3$.