A. Tetris

Codeforces

IDCF961A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

You are given a following process. There is a platform with $n$ columns. $1 \times 1$ squares are appearing one after another in some columns on this platform. If there are no squares in the column, a square will occupy the bottom row. Otherwise a square will appear at the top of the highest square of this column. When all of the $n$ columns have at least one square in them, the bottom row is being removed. You will receive $1$ point for this, and all the squares left will fall down one row. You task is to calculate the amount of points you will receive. ## Input The first line of input contain 2 integer numbers $n$ and $m$ ($1 \le n, m \le 1000$) — the length of the platform and the number of the squares. The next line contain $m$ integer numbers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n$) — column in which $i$\-th square will appear. ## Output Print one integer — the amount of points you will receive. [samples] ## Note In the sample case the answer will be equal to $2$ because after the appearing of $6$\-th square will be removed one row (counts of the squares on the platform will look like $[2~ 3~ 1]$, and after removing one row will be $[1~ 2~ 0]$). After the appearing of $9$\-th square counts will be $[2~ 3~ 1]$, and after removing one row it will look like $[1~ 2~ 0]$. So the answer will be equal to $2$.

你被给予以下过程。有一个包含 $n$ 列的平台。$1 \times 1$ 的方块会依次出现在平台的某些列上。如果某一列没有方块，则方块会占据最底行；否则，方块会出现在该列最高方块的顶部。当所有 $n$ 列都至少有一个方块时，最底行会被移除。你会因此获得 $1$ 分，剩余的所有方块会向下移动一行。你的任务是计算你将获得的总分数。输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1000$）——平台的长度和方块的数量。接下来的一行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$1 \leq c_i \leq n$）——表示第 $i$ 个方块出现的列。请输出一个整数——你将获得的分数。在样例中，答案为 $2$，因为在第 $6$ 个方块出现后，会移除一行（平台上的方块数量变为 $[ 2 \mid 3 \mid 1 ]$，移除一行后变为 $[ 1 \mid 2 \mid 0 ]$）。在第 $9$ 个方块出现后，方块数量变为 $[ 2 \mid 3 \mid 1 ]$，移除一行后变为 $[ 1 \mid 2 \mid 0 ]$。因此答案为 $2$。 ## Input 输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1000$）——平台的长度和方块的数量。接下来的一行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$1 \leq c_i \leq n$）——表示第 $i$ 个方块出现的列。 ## Output 请输出一个整数——你将获得的分数。 [samples] ## Note 在样例中，答案为 $2$，因为在第 $6$ 个方块出现后，会移除一行（平台上的方块数量变为 $[ 2 \mid 3 \mid 1 ]$，移除一行后变为 $[ 1 \mid 2 \mid 0 ]$）。在第 $9$ 个方块出现后，方块数量变为 $[ 2 \mid 3 \mid 1 ]$，移除一行后变为 $[ 1 \mid 2 \mid 0 ]$。因此答案为 $2$。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of columns and the number of squares, respectively. Let $ C = (c_1, c_2, \dots, c_m) $ be a sequence of column indices, where $ c_i \in \{1, 2, \dots, n\} $ indicates the column in which the $ i $-th square appears. Let $ h_j \in \mathbb{N} $ denote the height (number of squares) in column $ j \in \{1, 2, \dots, n\} $ after all squares have been placed. **Constraints** 1. $ 1 \leq n, m \leq 1000 $ 2. $ 1 \leq c_i \leq n $ for all $ i \in \{1, \dots, m\} $ **Process** Squares are placed sequentially: for each $ i \in \{1, \dots, m\} $, increment $ h_{c_i} \leftarrow h_{c_i} + 1 $. After each placement, if $ \min_{1 \leq j \leq n} h_j \geq 1 $, then: - Increment the score by 1, - Decrement each $ h_j \leftarrow h_j - 1 $ for all $ j \in \{1, \dots, n\} $. **Objective** Compute the total score (number of times the bottom row is removed) after processing all $ m $ squares.

Samples

Input #1

3 9
1 1 2 2 2 3 1 2 3

Output #1

API Response (JSON)

{
  "problem": {
    "name": "A. Tetris",
    "description": {
      "content": "You are given a following process. There is a platform with $n$ columns. $1 \\times 1$ squares are appearing one after another in some columns on this platform. If there are no squares in the column, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF961A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a following process.\n\nThere is a platform with $n$ columns. $1 \\times 1$ squares are appearing one after another in some columns on this platform. If there are no squares in the column, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给予以下过程。\n\n有一个包含 $n$ 列的平台。$1 \\times 1$ 的方块会依次出现在平台的某些列上。如果某一列没有方块，则方块会占据最底行；否则，方块会出现在该列最高方块的顶部。\n\n当所有 $n$ 列都至少有一个方块时，最底行会被移除。你会因此获得 $1$ 分，剩余的所有方块会向下移动一行。\n\n你的任务是计算你将获得的总分数。\n\n输入的第一行包含两个整数 $n$ 和 $m$（$1 \\l...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of columns and the number of squares, respectively.  \nLet $ C = (c_1, c_2, \\dots, c_m) $ be a sequence of column indices, where $ c_i ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments