codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1846C.md (3921B)


      1 Source: https://codeforces.com/problemset/problem/1846/C
      2 
      3 C. Rudolf and the Another Competition
      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 Rudolf has registered for a programming competition that will follow the rules of ICPC. The rules imply that for each solved problem, a participant gets $1$ point, and also incurs a penalty equal to the number of minutes passed from the beginning of the competition to the moment of solving the problem. In the final table, the participant with the most points is ranked higher, and in case of a tie in points, the participant with the lower penalty is ranked higher.
     22 
     23 In total, $n$ participants have registered for the competition. Rudolf is a participant with index $1$. It is known that $m$ problems will be proposed. And the competition will last $h$ minutes.
     24 
     25 A powerful artificial intelligence has predicted the values $t_{i, j}$, which represent the number of minutes it will take for the $i$-th participant to solve the $j$-th problem.
     26 
     27 Rudolf realized that the order of solving problems will affect the final result. For example, if $h = 120$, and the times to solve problems are [$20, 15, 110$], then if Rudolf solves the problems in the order:
     28 
     29 * ${3, 1, 2}$, then he will only solve the third problem and get $1$ point and $110$ penalty.
     30 * ${1, 2, 3}$, then he will solve the first problem after $20$ minutes from the start, the second one after $20+15=35$ minutes, and he will not have time to solve the third one. Thus, he will get $2$ points and $20+35=55$ penalty.
     31 * ${2, 1, 3}$, then he will solve the second problem after $15$ minutes from the start, the first one after $15+20=35$ minutes, and he will not have time to solve the third one. Thus, he will get $2$ points and $15+35=50$ penalty.
     32 
     33 Rudolf became interested in what place he will take in the competition if each participant solves problems in the optimal order based on the predictions of the artificial intelligence. It will be assumed that in case of a tie in points and penalty, Rudolf will take the best place.
     34 
     35 Input
     36 
     37 The first line contains an integer $t$ ($1 \le t \le 10^3$) — the number of test cases.
     38 
     39 Then follow the descriptions of the test cases.
     40 
     41 The first line of each test case contains three integers $n, m, h$ ($1 \le n \cdot m \le 2 \cdot 10^5, 1 \le h \le 10^6$) — the number of participants, the number of problems, and the duration of the competition, respectively.
     42 
     43 Then there are $n$ lines, each containing $m$ integers $t_{i, j}$ ($1 \le t_{i, j} \le 10^6$) — the number of minutes it will take for the $i$-th participant to solve the $j$-th problem.
     44 
     45 The sum of $n \cdot m$ over all test cases does not exceed $2 \cdot 10^5$.
     46 
     47 Output
     48 
     49 For each test case, output an integer — Rudolf's place in the final table if all participants solve problems in the optimal order.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 5
     57 
     58 3 3 120
     59 
     60 20 15 110
     61 
     62 90 90 100
     63 
     64 40 40 40
     65 
     66 2 1 120
     67 
     68 30
     69 
     70 30
     71 
     72 1 3 120
     73 
     74 10 20 30
     75 
     76 3 2 27
     77 
     78 8 9
     79 
     80 10 7
     81 
     82 10 8
     83 
     84 3 3 15
     85 
     86 7 2 6
     87 
     88 7 5 4
     89 
     90 1 9 8
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 2
     97 1
     98 1
     99 2
    100 1
    101 ```
    102 
    103 Note
    104 
    105 In the first example, Rudolf will get $2$ points and $50$ penalty minutes. The second participant will solve only one problem and get $1$ point and $90$ penalty minutes. And the third participant will solve all $3$ problems and get $3$ points and $240$ penalty minutes. Thus, Rudolf will take the second place.
    106 
    107 In the second example, both participants will get $1$ point and $30$ penalty minutes. In case of a tie in points, Rudolf gets the better position, so he will take the first place.
    108 
    109 In the third example, Rudolf is the only participant, so he will take the first place.
    110 
    111 In the fourth example, all participants can solve two problems with penalty of $25 = 8 + (8 + 9)$, $24 = 7 + (7 + 10)$ and $26 = 8 + (8 + 10)$, respectively, thanks to the penalty, the second participant gets the first place, and Rudolf gets the second.