A12678. Drinks Choosing
编程题
普及/提高-
知识点
题目描述
Old timers of Summer Informatics School can remember previous camps in which each student was given a drink of his choice on the vechorka (late-evening meal). Or may be the story was more complicated?
There are $n$ students living in a building, and for each of them the favorite drink $a_i$ is known. So you know $n$ integers $a_1, a_2, \dots, a_n$ , where $a_i$ ( $1 \le a_i \le k$ ) is the type of the favorite drink of the $i$ -th student. The drink types are numbered from $1$ to $k$ .
There are infinite number of drink sets. Each set consists of exactly two portions of the same drink. In other words, there are $k$ types of drink sets, the $j$ -th type contains two portions of the drink $j$ . The available number of sets of each of the $k$ types is infinite.
You know that students will receive the minimum possible number of sets to give all students exactly one drink. Obviously, the number of sets will be exactly $\lceil \frac{n}{2} \rceil$ , where $\lceil x \rceil$ is $x$ rounded up.
After students receive the sets, they will distribute their portions by their choice: each student will get exactly one portion. Note, that if $n$ is odd then one portion will remain unused and the students' teacher will drink it.
What is the maximum number of students that can get their favorite drink if $\lceil \frac{n}{2} \rceil$ sets will be chosen optimally and students will distribute portions between themselves optimally?
There are $n$ students living in a building, and for each of them the favorite drink $a_i$ is known. So you know $n$ integers $a_1, a_2, \dots, a_n$ , where $a_i$ ( $1 \le a_i \le k$ ) is the type of the favorite drink of the $i$ -th student. The drink types are numbered from $1$ to $k$ .
There are infinite number of drink sets. Each set consists of exactly two portions of the same drink. In other words, there are $k$ types of drink sets, the $j$ -th type contains two portions of the drink $j$ . The available number of sets of each of the $k$ types is infinite.
You know that students will receive the minimum possible number of sets to give all students exactly one drink. Obviously, the number of sets will be exactly $\lceil \frac{n}{2} \rceil$ , where $\lceil x \rceil$ is $x$ rounded up.
After students receive the sets, they will distribute their portions by their choice: each student will get exactly one portion. Note, that if $n$ is odd then one portion will remain unused and the students' teacher will drink it.
What is the maximum number of students that can get their favorite drink if $\lceil \frac{n}{2} \rceil$ sets will be chosen optimally and students will distribute portions between themselves optimally?
输入格式
The first line of the input contains two integers $n$ and $k$ ( $1 \le n, k \le 1\,000$ ) — the number of students in the building and the number of different drinks.
The next $n$ lines contain student's favorite drinks. The $i$ -th line contains a single integer from $1$ to $k$ — the type of the favorite drink of the $i$ -th student.
The next $n$ lines contain student's favorite drinks. The $i$ -th line contains a single integer from $1$ to $k$ — the type of the favorite drink of the $i$ -th student.
输出格式
Print exactly one integer — the maximum number of students that can get a favorite drink.
输入输出样例
输入 #1
5 3 1 3 1 1 2
输出 #1
4
输入 #2
10 3 2 1 3 2 3 3 1 3 1 2
输出 #2
9
说明/提示
In the first example, students could choose three sets with drinks $1$ , $1$ and $2$ (so they will have two sets with two drinks of the type $1$ each and one set with two drinks of the type $2$ , so portions will be $1, 1, 1, 1, 2, 2$ ). This way all students except the second one will get their favorite drinks.
Another possible answer is sets with drinks $1$ , $2$ and $3$ . In this case the portions will be $1, 1, 2, 2, 3, 3$ . Then all the students except one will gain their favorite drinks. The only student that will not gain the favorite drink will be a student with $a_i = 1$ (i.e. the first, the third or the fourth).
Another possible answer is sets with drinks $1$ , $2$ and $3$ . In this case the portions will be $1, 1, 2, 2, 3, 3$ . Then all the students except one will gain their favorite drinks. The only student that will not gain the favorite drink will be a student with $a_i = 1$ (i.e. the first, the third or the fourth).