J. Parallelograms

Codeforces

IDCF10175J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

There are n sticks, the i-th of which has length ai. Alex wants to assemble from them as many parallelograms as possible simultaneously, with each stick used at most in one parallelogram. What maximal number of parallelograms is it possible to assemble? The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of sticks. The second line contains n integers ai (1 ≤ ai ≤ 200000) — the lengths of sticks. Output a single integer — the maximal number of parallelograms that is possible to assemble. ## Input The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of sticks.The second line contains n integers ai (1 ≤ ai ≤ 200000) — the lengths of sticks. ## Output Output a single integer — the maximal number of parallelograms that is possible to assemble. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of sticks. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers representing stick lengths. Let $ f: \mathbb{Z}^+ \to \mathbb{Z}^+ $ be the frequency function, where $ f(l) $ denotes the number of sticks of length $ l $. **Constraints** 1. $ 1 \le n \le 200000 $ 2. $ 1 \le a_i \le 200000 $ for all $ i \in \{1, \dots, n\} $ **Objective** Maximize the number of parallelograms, where each parallelogram requires two pairs of sticks of equal lengths (i.e., four sticks: two pairs of equal-length sides). Each stick may be used in at most one parallelogram. Let $ x $ be the number of parallelograms. Then: $$ x = \sum_{l=1}^{\max(A)} \left\lfloor \frac{f(l)}{2} \right\rfloor $$ Let $ m = \sum_{l=1}^{\max(A)} \left\lfloor \frac{f(l)}{2} \right\rfloor $. Then the maximum number of parallelograms is: $$ \left\lfloor \frac{m}{2} \right\rfloor $$

API Response (JSON)

{
  "problem": {
    "name": "J. Parallelograms",
    "description": {
      "content": "There are n sticks, the i-th of which has length ai. Alex wants to assemble from them as many parallelograms as possible simultaneously, with each stick used at most in one parallelogram. What maximal",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10175J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are n sticks, the i-th of which has length ai. Alex wants to assemble from them as many parallelograms as possible simultaneously, with each stick used at most in one parallelogram. What maximal...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of sticks.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing stick lengths.  \n\nLet $ f: \\mathbb{Z}^+ \\to \\ma...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments