A. Splitting in Teams

Codeforces

IDCF899A

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsgreedymath

English · Original

Chinese · Translation

Formal · Original

There were _n_ groups of students which came to write a training contest. A group is either one person who can write the contest with anyone else, or two people who want to write the contest in the same team. The coach decided to form teams of exactly three people for this training. Determine the maximum number of teams of three people he can form. It is possible that he can't use all groups to form teams. For groups of two, either both students should write the contest, or both should not. If two students from a group of two will write the contest, they should be in the same team. ## Input The first line contains single integer _n_ (2 ≤ _n_ ≤ 2·105) — the number of groups. The second line contains a sequence of integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 2), where _a__i_ is the number of people in group _i_. ## Output Print the maximum number of teams of three people the coach can form. [samples] ## Note In the first example the coach can form one team. For example, he can take students from the first, second and fourth groups. In the second example he can't make a single team. In the third example the coach can form three teams. For example, he can do this in the following way: * The first group (of two people) and the seventh group (of one person), * The second group (of two people) and the sixth group (of one person), * The third group (of two people) and the fourth group (of one person).

有 #cf_span[n] 组学生前来参加训练赛。每组要么是单个学生，可以与任何人组队；要么是两人组，希望在同一队中参赛。教练决定为此次训练赛组建恰好三人一队的队伍。请确定他最多能组成多少支三人队伍。可能无法使用所有组来组建队伍。对于两人组，要么两名学生都参赛，要么都不参赛；如果两人组中的两名学生参赛，他们必须在同一队中。第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 组的数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 2])，其中 #cf_span[ai] 表示第 #cf_span[i] 组的人数。请输出教练能组成的三人队伍的最大数量。在第一个示例中，教练可以组成一支队伍。例如，他可以从第一、第二和第四组中选取学生。在第二个示例中，他无法组成任何一支队伍。在第三个示例中，教练可以组成三支队伍。例如，他可以按以下方式操作： ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 组的数量。第二行包含一个整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 2])，其中 #cf_span[ai] 表示第 #cf_span[i] 组的人数。 ## Output 请输出教练能组成的三人队伍的最大数量。 [samples] ## Note 在第一个示例中，教练可以组成一支队伍。例如，他可以从第一、第二和第四组中选取学生。在第二个示例中，他无法组成任何一支队伍。在第三个示例中，教练可以组成三支队伍。例如，他可以按以下方式操作：第一组（两人）与第七组（一人），第二组（两人）与第六组（一人），第三组（两人）与第四组（一人）。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of groups. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence where $ a_i \in \{1, 2\} $ denotes the size of group $ i $. Let: - $ c_1 = |\{i \mid a_i = 1\}| $: number of singleton groups. - $ c_2 = |\{i \mid a_i = 2\}| $: number of two-person groups. **Constraints** $ 2 \leq n \leq 2 \cdot 10^5 $, $ c_1 + c_2 = n $, $ c_1, c_2 \in \mathbb{Z}_{\geq 0} $. **Objective** Maximize the number of teams of exactly three people, subject to: - Each team consists of exactly three students. - Each two-person group must be kept intact (both students in the same team) or not used at all. - Singleton groups can be freely assigned to any team. Let $ t $ be the number of teams formed. Let $ x \in \{0, 1, \dots, c_2\} $ be the number of two-person groups used (each contributing 2 students). Then the remaining $ 3t - 2x $ students must come from singleton groups, so: $ 3t - 2x \leq c_1 $ and $ 3t - 2x \geq 0 $. Thus, for fixed $ x $, the maximum number of teams is: $$ t = \left\lfloor \frac{c_1 + 2x}{3} \right\rfloor $$ with constraint $ 0 \leq x \leq c_2 $ and $ 2x \leq 3t \leq c_1 + 2x $. **Objective:** $$ \max_{x \in \{0, 1, \dots, c_2\}} \left\lfloor \frac{c_1 + 2x}{3} \right\rfloor $$

Samples

Input #1

4
1 1 2 1

Output #1

Input #2

2
2 2

Output #2

Input #3

7
2 2 2 1 1 1 1

Output #3

Input #4

3
1 1 1

Output #4

API Response (JSON)

{
  "problem": {
    "name": "A. Splitting in Teams",
    "description": {
      "content": "There were _n_ groups of students which came to write a training contest. A group is either one person who can write the contest with anyone else, or two people who want to write the contest in the sa",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF899A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There were _n_ groups of students which came to write a training contest. A group is either one person who can write the contest with anyone else, or two people who want to write the contest in the sa...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有 #cf_span[n] 组学生前来参加训练赛。每组要么是单个学生，可以与任何人组队；要么是两人组，希望在同一队中参赛。\n\n教练决定为此次训练赛组建恰好三人一队的队伍。请确定他最多能组成多少支三人队伍。可能无法使用所有组来组建队伍。对于两人组，要么两名学生都参赛，要么都不参赛；如果两人组中的两名学生参赛，他们必须在同一队中。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of groups.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence where $ a_i \\in \\{1, 2\\} $ denotes the size of group $ i $.  \n\nLet:  \n- $ c_1 = |...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments