| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 2048 MB | 3 | 2 | 2 | 66.667% |
The International Mathematics Olympiad (IMO) is a maths competition for high school students that is held every year. The 2025 edition of the IMO takes place at the same time as the EGOI. As you are reading this, both contest days of the IMO have ended and the grading is probably almost done as well. Unlike programming competitions like the EGOI, the grading is done by hand, which is a long and arduous process.
This year the IMO had $M$ problems (numbered from 0ドル$ to $M-1$), and each problem is worth a maximum of $K$ points. There were $N$ contestants taking part in the contest. The $i$th contestant received a score of $a_{i,j}$ on problem $j,ドル where $a_{i,j}$ is an integer between 0ドル$ and $K,ドル inclusive. The ranking of the contestants is determined by the total score of each contestant, with ties broken by the contestants' indices. More formally, contestant $x$ ranks higher than contestant $y$ if:
In order to release the final ranking, the organizers need to publish some of the values $a_{i,j}$. If a value is unpublished, it is only known that it is an integer between 0ドル$ and $K,ドル inclusive.
The organizers want to reveal as few of the values $a_{i,j}$ as possible. At the same time, they need to make sure that everyone knows the correct final ranking. In other words, they must reveal a set of values such that the only ranking consistent with it is the correct one.
Find the smallest $S$ such that it is possible to reveal $S$ of the values $a_{i,j}$ in a way that uniquely determines the full ranking of the contestants.
The first line contains three integers $N,ドル $M,ドル and $K$: the number of contestants, the number of problems, and the maximum score of the tasks, respectively.
Then follow $N$ lines, where the $i$th line contains $a_{i,j}$. That is, the first of these contains $a_{0,0}, a_{0,1}, \ldots, a_{0, M-1},ドル the second contains $a_{1,0}, a_{1,1}, \ldots, a_{1, M-1},ドル and so on.
Print one integer $S,ドル the minimum number of scores that can be revealed so that the final ranking is uniquely determined.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N = M = 2$ and $K = 1$ |
| 2 | 13 | $N = 2$ |
| 3 | 10 | $N \cdot M \leq 16$ |
| 4 | 18 | $K = 1$ |
| 5 | 21 | $N \leq 10,000円$ and $M,K \leq 10$ |
| 6 | 28 | No additional constraints |
4 6 7 7 7 0 2 7 0 7 3 0 7 2 1 7 0 0 7 0 0 7 7 7 7 7 1
20
2 1 1 1 0
1
2 2 7 7 4 7 0
2
2 2 1 0 1 1 0
2
In the first example, the 20ドル$ scores can be revealed in the following way:
Here, the third contestant is known to have a total score between 0ドル$ and 14ドル,ドル which is definitely lower than any other score. It can be shown that it is impossible to reveal fewer than 20ドル$ scores. For example, if we were to hide one of the zeroes of the third contestant, then this contestant could have a total score of up to 21ドル$. This is a problem because the second contestant has a total score of 20ドル,ドル but should be guaranteed to rank higher than the third contestant.
The first sample satisfies the constraints of test groups 5ドル$ and 6ドル$.
In the second example, we can either reveal only the first contestant's only score, or reveal only the second contestant's only score (but not both). If we reveal only the first contestant's score, then we know that the first contestant has a total score of 1ドル$. This means that even if the second contestant also has a score of 1ドル,ドル the first contestant will rank higher because their index is lower. Similarly, if we only reveal the score of the second contestant, we know that they have a score of zero, which means that the first contestant will rank higher regardless of their score.
The second sample satisfies the constraints of test groups 2ドル,ドル 3ドル,ドル 4ドル,ドル 5ドル,ドル and 6ドル$.
The third sample satisfies the constraints of test groups 2ドル,ドル 3ドル,ドル 5ドル,ドル and 6ドル$.
The fourth sample satisfies the constraints of all test groups.