A. Polycarp's Pockets

Codeforces

IDCF1003A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Polycarp has $n$ coins, the value of the $i$\-th coin is $a_i$. Polycarp wants to distribute all the coins between his pockets, but he cannot put two coins with the same value into the same pocket. For example, if Polycarp has got six coins represented as an array $a = [1, 2, 4, 3, 3, 2]$, he can distribute the coins into two pockets as follows: $[1, 2, 3], [2, 3, 4]$. Polycarp wants to distribute all the coins with the minimum number of used pockets. Help him to do that. ## Input The first line of the input contains one integer $n$ ($1 \le n \le 100$) — the number of coins. The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$) — values of coins. ## Output Print only one integer — the minimum number of pockets Polycarp needs to distribute all the coins so no two coins with the same value are put into the same pocket. [samples]

Polycarp 有 $n$ 枚硬币，第 $i$ 枚硬币的面值为 $a_i$。Polycarp 希望将所有硬币分配到他的口袋中，但他不能将两枚面值相同的硬币放入同一个口袋。例如，如果 Polycarp 有六枚硬币，表示为数组 $a = [ 1, 2, 4, 3, 3, 2 ]$，他可以将硬币分配到两个口袋中，如下所示：$[ 1, 2, 3 ], [ 2, 3, 4 ]$。 Polycarp 希望使用最少数量的口袋来分配所有硬币。请帮助他完成这一任务。输入的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100$) —— 硬币的数量。输入的第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 100$) —— 硬币的面值。请仅输出一个整数 —— Polycarp 分配所有硬币所需的最少口袋数量，使得没有两个面值相同的硬币被放入同一个口袋。 ## Input 输入的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100$) —— 硬币的数量。输入的第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 100$) —— 硬币的面值。 ## Output 请仅输出一个整数 —— Polycarp 分配所有硬币所需的最少口袋数量，使得没有两个面值相同的硬币被放入同一个口袋。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of coins. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers representing coin values. Let $ f: \mathbb{Z}^+ \to \mathbb{Z}^+ $ be the frequency function, where $ f(v) $ denotes the number of times value $ v $ appears in $ A $. **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ 1 \leq a_i \leq 100 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the minimum number of pockets required such that no pocket contains two coins of the same value. This is equivalent to the maximum frequency of any coin value: $$ \min \text{pockets} = \max_{v \in \text{values}(A)} f(v) $$

Samples

Input #1

6
1 2 4 3 3 2

Output #1

Input #2

1
100

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Polycarp's Pockets",
    "description": {
      "content": "Polycarp has $n$ coins, the value of the $i$\\-th coin is $a_i$. Polycarp wants to distribute all the coins between his pockets, but he cannot put two coins with the same value into the same pocket. F",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1003A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp has $n$ coins, the value of the $i$\\-th coin is $a_i$. Polycarp wants to distribute all the coins between his pockets, but he cannot put two coins with the same value into the same pocket.\n\nF...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 有 $n$ 枚硬币，第 $i$ 枚硬币的面值为 $a_i$。Polycarp 希望将所有硬币分配到他的口袋中，但他不能将两枚面值相同的硬币放入同一个口袋。\n\n例如，如果 Polycarp 有六枚硬币，表示为数组 $a = [ 1, 2, 4, 3, 3, 2 ]$，他可以将硬币分配到两个口袋中，如下所示：$[ 1, 2, 3 ], [ 2, 3, 4 ]$。\n\nPolycarp ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of coins.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing coin values.\n\nLet $ f: \\mathbb{Z}^+ \\to \\mathbb{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments