1195A.md (2824B)
1 Source: https://codeforces.com/problemset/problem/1195/A 2 3 A. Drinks Choosing 4 5 time limit per test 6 7 2 seconds 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 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? 22 23 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$. 24 25 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. 26 27 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. 28 29 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. 30 31 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? 32 33 Input 34 35 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. 36 37 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. 38 39 Output 40 41 Print exactly one integer — the maximum number of students that can get a favorite drink. 42 43 Examples 44 45 Input 46 47 ``` 48 5 3 49 1 50 3 51 1 52 1 53 2 54 ``` 55 56 Output 57 58 ``` 59 4 60 ``` 61 62 Input 63 64 ``` 65 10 3 66 2 67 1 68 3 69 2 70 3 71 3 72 1 73 3 74 1 75 2 76 ``` 77 78 Output 79 80 ``` 81 9 82 ``` 83 84 Note 85 86 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. 87 88 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).