codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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).