No.1692 Expectations
eSeF
first_vil
ygussanyProblem Statement
There is a game with $N$ participants. They are called Person 1, Person 2, ..., Person $N$.
Now, there is 1 copy of each integer between $1$ and $M$, inclusive. $N$ of these are chosen and given to the $N$ people, $1$ to each person.
SF-kun, who is watching this game, wants to guess which integer each person has. So he has made $N$ guesses. The $i$-th guess is as follows.
- The integer that Person $i$ has is $A_i$.
Find the maximum and minimum possible number of correct guesses among SF-kun's guesses. Here, a correct guess means an integer $i$ such that the integer Person $i$ actually has is $A_i$.
Input
$N\ \ M$ $A_1\ \cdots \ A_N$【Constraints】
- $1\le N\le M\le 2\times 10^5$
- $1\le A_i\le M$
- All input values are integers.
Output
Print the maximum $\max$ and the minimum $\min$ of the number of correct guesses among SF-kun's guesses on one line, separated by a space, as follows.$\max\ \ \min$
Sample
Sample 1
Input
3 5 1 2 1
Output
2 0
For example, if the integers the three people have are (Person 1, Person 2, Person 3)$=(4,2,1)$, two guesses are correct. On the other hand, if all the guesses were correct, there would be two copies of $1$, which is impossible. Therefore, the maximum number of correct guesses is $2$.
All the guesses can be wrong, for example when the integers they have are $(2,3,5)$. Thus, the minimum is $0$.
Sample 2
Input
8 8 7 1 2 5 8 3 4 6
Output
8 0
It is possible for all the guesses to be correct, and it is also possible for all of them to be wrong.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。