G. Large Bouquets

Codeforces

IDCF953G

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

A flower shop has got _n_ bouquets, and the _i_\-th bouquet consists of _a__i_ flowers. Vasya, the manager of the shop, decided to make large bouquets from these bouquets. Vasya thinks that a bouquet is large if it is made of **two or more** initial bouquets, and there is a constraint: the total number of flowers in a large bouquet should be **odd**. Each of the initial bouquets can be a part of at most one large bouquet. If an initial bouquet becomes a part of a large bouquet, all its flowers are included in the large bouquet. Determine the maximum possible number of large bouquets Vasya can make. ## Input The first line contains a single positive integer _n_ (1 ≤ _n_ ≤ 105) — the number of initial bouquets. The second line contains a sequence of integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) — the number of flowers in each of the initial bouquets. ## Output Print the maximum number of large bouquets Vasya can make. [samples] ## Note In the first example Vasya can make 2 large bouquets. For example, the first bouquet can contain the first and the fifth initial bouquets (the total number of flowers is then equal to 9), and the second bouquet can consist of the second and the third initial bouquets (the total number of flowers is then equal to 7). The fourth initial bouquet is unused in this scheme. In the second example it is not possible to form a single bouquet with odd number of flowers. In the third example Vasya can make one large bouquet. For example, he can make it using all three initial bouquets. The size of the large bouquet is then equal to 11 + 4 + 10 = 25.

一家花店有 #cf_span[n] 束花，第 #cf_span[i] 束花包含 #cf_span[ai] 朵花。花店经理 Vasya 决定用这些花束制作大型花束。 Vasya 认为，一个花束是大型的，当且仅当它由 *两个或更多* 初始花束组成，且有一个约束条件：大型花束中的花朵总数必须为 *奇数*。每个初始花束最多只能属于一个大型花束。如果一个初始花束被纳入一个大型花束，则其所有花朵都必须包含在该大型花束中。请确定 Vasya 最多能制作多少个大型花束。第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 初始花束的数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 106]) —— 每个初始花束中的花朵数量。请输出 Vasya 最多能制作的大型花束数量。在第一个例子中，Vasya 可以制作 #cf_span[2] 个大型花束。例如，第一个花束可以包含第一个和第五个初始花束（花朵总数为 #cf_span[9]），第二个花束可以由第二个和第三个初始花束组成（花朵总数为 #cf_span[7]）。第四个初始花束在该方案中未被使用。在第二个例子中，无法组成任何一个花朵总数为奇数的花束。在第三个例子中，Vasya 可以制作一个大型花束。例如，他可以使用全部三个初始花束，此时大型花束的大小为 #cf_span[11 + 4 + 10 = 25]。 ## Input 第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 初始花束的数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 106]) —— 每个初始花束中的花朵数量。 ## Output 请输出 Vasya 最多能制作的大型花束数量。 [samples] ## Note 在第一个例子中，Vasya 可以制作 #cf_span[2] 个大型花束。例如，第一个花束可以包含第一个和第五个初始花束（花朵总数为 #cf_span[9]），第二个花束可以由第二个和第三个初始花束组成（花朵总数为 #cf_span[7]）。第四个初始花束在该方案中未被使用。在第二个例子中，无法组成任何一个花朵总数为奇数的花束。在第三个例子中，Vasya 可以制作一个大型花束。例如，他可以使用全部三个初始花束，此时大型花束的大小为 #cf_span[11 + 4 + 10 = 25]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of initial bouquets. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of flowers in the $ i $-th bouquet. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq a_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $ **Objective** Partition a subset of $ A $ into disjoint groups (each of size $ \geq 2 $) such that the sum of flowers in each group is **odd**. Maximize the number of such groups.

Samples

Input #1

5
2 3 4 2 7

Output #1

Input #2

6
2 2 6 8 6 12

Output #2

Input #3

3
11 4 10

Output #3

API Response (JSON)

{
  "problem": {
    "name": "G. Large Bouquets",
    "description": {
      "content": "A flower shop has got _n_ bouquets, and the _i_\\-th bouquet consists of _a__i_ flowers. Vasya, the manager of the shop, decided to make large bouquets from these bouquets. Vasya thinks that a bouquet",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF953G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A flower shop has got _n_ bouquets, and the _i_\\-th bouquet consists of _a__i_ flowers. Vasya, the manager of the shop, decided to make large bouquets from these bouquets.\n\nVasya thinks that a bouquet...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "一家花店有 #cf_span[n] 束花，第 #cf_span[i] 束花包含 #cf_span[ai] 朵花。花店经理 Vasya 决定用这些花束制作大型花束。\n\nVasya 认为，一个花束是大型的，当且仅当它由 *两个或更多* 初始花束组成，且有一个约束条件：大型花束中的花朵总数必须为 *奇数*。每个初始花束最多只能属于一个大型花束。如果一个初始花束被纳入一个大型花束，则其所有花朵都必须包含在...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of initial bouquets.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the number of flowers in the $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments