## Intuition The problem is about optimizing the order of solving problems in a programming competition to maximize the score and minimize the penalty. Each participant should solve problems in increasing order of the time it takes to solve them. This strategy maximizes the number of problems solved within the given time limit and minimizes the penalty incurred. ## Approach 1. **Input Parsing:** Start by reading the number of test cases. For each test case, read the number of participants, the number of problems, and the total competition time. 2. **Sorting Problems:** For each participant, sort the times required to solve each problem in ascending order. This allows the participant to solve as many problems as possible within the given time limit, while also minimizing the penalty. 3. **Calculate Scores and Penalties:** - For each participant, iterate over the sorted problem times. - Keep a running sum of the time taken to solve problems. - If the cumulative time exceeds the competition time, stop solving further problems. - Count the number of problems solved and calculate the total penalty (sum of times when each problem is solved). 4. **Determine Rudolf's Rank:** - Compare Rudolf's score and penalty with other participants. - Rank participants first by score (number of problems solved) and then by penalty (lower is better). - In case of ties, Rudolf takes the better position. 5. **Output the Results:** For each test case, output Rudolf's rank. ## Complexity - **Time Complexity:** \(O(t \times n \times m \log m)\), where \(t\) is the number of test cases, \(n\) is the number of participants, and \(m\) is the number of problems. Sorting each participant's problems takes \(O(m \log m)\). - **Space Complexity:** \(O(n \times m)\) for storing the problem times for each participant. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n, m, h; cin >> n >> m >> h; vector> results; // To store (score, penalty) for each participant for (int i = 0; i < n; ++i) { vector times(m); for (int j = 0; j < m; ++j) { cin >> times[j]; } sort(times.begin(), times.end()); int score = 0, penalty = 0, currentTime = 0; for (int time : times) { if (currentTime + time <= h) { currentTime += time; penalty += currentTime; score++; } else { break; } } results.emplace_back(score, penalty); } // Determine Rudolf's rank auto rudolfResult = results[0]; int rudolfRank = 1; for (int i = 1; i < n; ++i) { if (results[i].first > rudolfResult.first || (results[i].first == rudolfResult.first && results[i].second < rudolfResult.second)) { rudolfRank++; } } cout << rudolfRank << '\n'; } return 0; } ``` This solution efficiently calculates the optimal order of solving problems for each participant and determines Rudolf's rank based on his performance relative to others.

Rudolf and the Another Competition

Problem Details