codeforces-scrape

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

1133B.md (2095B)


      1 Source: https://codeforces.com/problemset/problem/1133/B
      2 
      3 B. Preparation for International Women's Day
      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 International Women's Day is coming soon! Polycarp is preparing for the holiday.
     22 
     23 There are $n$ candy boxes in the shop for sale. The $i$-th box contains $d_i$ candies.
     24 
     25 Polycarp wants to prepare the maximum number of gifts for $k$ girls. Each gift will consist of exactly two boxes. The girls should be able to share each gift equally, so the total amount of candies in a gift (in a pair of boxes) should be divisible by $k$. In other words, two boxes $i$ and $j$ ($i \ne j$) can be combined as a gift if $d_i + d_j$ is divisible by $k$.
     26 
     27 How many boxes will Polycarp be able to give? Of course, each box can be a part of no more than one gift. Polycarp cannot use boxes "partially" or redistribute candies between them.
     28 
     29 Input
     30 
     31 The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le k \le 100$) — the number the boxes and the number the girls.
     32 
     33 The second line of the input contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$), where $d_i$ is the number of candies in the $i$-th box.
     34 
     35 Output
     36 
     37 Print one integer — the maximum number of the boxes Polycarp can give as gifts.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 7 2
     45 1 2 2 3 2 4 10
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 6
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 8 2
     58 1 2 2 3 2 4 6 10
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 8
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 7 3
     71 1 2 2 3 2 4 5
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 4
     78 ```
     79 
     80 Note
     81 
     82 In the first example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):
     83 
     84 * $(2, 3)$;
     85 * $(5, 6)$;
     86 * $(1, 4)$.
     87 
     88 So the answer is $6$.
     89 
     90 In the second example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):
     91 
     92 * $(6, 8)$;
     93 * $(2, 3)$;
     94 * $(1, 4)$;
     95 * $(5, 7)$.
     96 
     97 So the answer is $8$.
     98 
     99 In the third example Polycarp can give the following pairs of boxes (pairs are presented by indices of corresponding boxes):
    100 
    101 * $(1, 2)$;
    102 * $(6, 7)$.
    103 
    104 So the answer is $4$.