B. Getting an A

Codeforces

IDCF991B

Time1000ms

Memory256MB

Difficulty—

greedysortings

English · Original

Chinese · Translation

Formal · Original

Translator's note: in Russia's most widespread grading system, there are four grades: 5, 4, 3, 2, the higher the better, roughly corresponding to A, B, C and F respectively in American grading system. The term is coming to an end and students start thinking about their grades. Today, a professor told his students that the grades for his course would be given out automatically — he would calculate the simple average (arithmetic mean) of all grades given out for lab works this term and round to the nearest integer. The rounding would be done in favour of the student — $4.5$ would be rounded up to $5$ (as in example 3), but $4.4$ would be rounded down to $4$. This does not bode well for Vasya who didn't think those lab works would influence anything, so he may receive a grade worse than $5$ (maybe even the dreaded $2$). However, the professor allowed him to redo some of his works of Vasya's choosing to increase his average grade. Vasya wants to redo as as few lab works as possible in order to get $5$ for the course. Of course, Vasya will get $5$ for the lab works he chooses to redo. Help Vasya — calculate the minimum amount of lab works Vasya has to redo. ## Input The first line contains a single integer $n$ — the number of Vasya's grades ($1 \leq n \leq 100$). The second line contains $n$ integers from $2$ to $5$ — Vasya's grades for his lab works. ## Output Output a single integer — the minimum amount of lab works that Vasya has to redo. It can be shown that Vasya can always redo enough lab works to get a $5$. [samples] ## Note In the first sample, it is enough to redo two lab works to make two $4$s into $5$s. In the second sample, Vasya's average is already $4.75$ so he doesn't have to redo anything to get a $5$. In the second sample Vasya has to redo one lab work to get rid of one of the $3$s, that will make the average exactly $4.5$ so the final grade would be $5$.

译者注：在俄罗斯最普遍的评分系统中，有四种成绩：5、4、3、2，分数越高越好，大致分别对应美国评分系统中的 A、B、C 和 F。学期即将结束，学生们开始关注自己的成绩。今天，一位教授告诉学生，他的课程成绩将自动计算——他会计算本学期所有实验作业成绩的简单平均值（算术平均数），然后四舍五入到最接近的整数。四舍五入时会偏向学生：$4.5$ 会被向上取整为 $5$（如示例 3），但 $4.4$ 会被向下取整为 $4$。这对瓦夏来说并不乐观，因为他没想过这些实验作业会有什么影响，所以他可能得到低于 5 的成绩（甚至可能得到可怕的 2）。然而，教授允许他选择重做部分作业以提高平均分。瓦夏希望尽可能少地重做作业，以便获得课程的 5 分。当然，瓦夏选择重做的作业都会得到 5 分。请帮助瓦夏——计算他最少需要重做多少次实验作业。第一行包含一个整数 $n$ —— 瓦夏的成绩数量（$1 lt.eq n lt.eq 100$）。第二行包含 $n$ 个从 2 到 5 的整数 —— 瓦夏的实验作业成绩。请输出一个整数 —— 瓦夏最少需要重做的实验作业数量。可以证明，瓦夏总可以通过重做足够多的作业来获得 5 分。在第一个样例中，只需重做两次作业，将两个 4 变为 5 即可。在第二个样例中，瓦夏的平均分已经是 $4.75$，因此他无需重做任何作业即可获得 5 分。在第三个样例中，瓦夏需要重做一次作业，去掉一个 3，这样平均分恰好变为 $4.5$，最终成绩即为 5。 ## Input 第一行包含一个整数 $n$ —— 瓦夏的成绩数量（$1 lt.eq n lt.eq 100$）。第二行包含 $n$ 个从 2 到 5 的整数 —— 瓦夏的实验作业成绩。 ## Output 请输出一个整数 —— 瓦夏最少需要重做的实验作业数量。可以证明，瓦夏总可以通过重做足够多的作业来获得 5 分。 [samples] ## Note 在第一个样例中，只需重做两次作业，将两个 $4$ 变为 $5$ 即可。在第二个样例中，瓦夏的平均分已经是 $4.75$，因此他无需重做任何作业即可获得 5 分。在第三个样例中，瓦夏需要重做一次作业，去掉一个 $3$，这样平均分恰好变为 $4.5$，最终成绩即为 5。

Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 100 $, be the number of lab work grades. Let $ g_1, g_2, \dots, g_n \in \{2, 3, 4, 5\} $ be Vasya’s current grades. Define the arithmetic mean: $$ \mu = \frac{1}{n} \sum_{i=1}^n g_i $$ The final grade is computed as: $$ \text{final} = \lfloor \mu + 0.5 \rfloor $$ (i.e., rounding to the nearest integer, with **half-up** rounding: $ 4.5 \rightarrow 5 $, $ 4.4 \rightarrow 4 $). Vasya may replace any subset of his grades with $ 5 $. Let $ k \in \mathbb{N}_0 $ be the number of grades replaced. Objective: Find the **minimum** $ k $ such that after replacing $ k $ of the grades with $ 5 $, the resulting mean $ \mu' $ satisfies: $$ \mu' \geq 4.5 $$ Let $ S = \sum_{i=1}^n g_i $ be the initial sum. After replacing $ k $ grades (each originally $ g_i \leq 4 $) with $ 5 $, the new sum is: $$ S' = S + \sum_{j=1}^k (5 - g_{i_j}) \quad \text{for some } g_{i_j} \in \{2,3,4\} $$ To minimize $ k $, we should choose the $ k $ grades with the **largest possible improvement** (i.e., replace the smallest current grades first). Define the **improvement potential** for each grade $ g_i $ as $ 5 - g_i \in \{0,1,2,3\} $. Sort the grades in ascending order (i.e., prioritize replacing 2s, then 3s, then 4s). Let $ d_1 \geq d_2 \geq \dots \geq d_n $ be the sorted list of improvements $ 5 - g_i $ in descending order. Find the smallest $ k \in \{0, 1, \dots, n\} $ such that: $$ \frac{S + \sum_{i=1}^k d_i}{n} \geq 4.5 $$ Equivalently: $$ S + \sum_{i=1}^k d_i \geq 4.5n $$ Output: the minimal such $ k $.

Samples

Input #1

3
4 4 4

Output #1

Input #2

4
5 4 5 5

Output #2

Input #3

4
5 3 3 5

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Getting an A",
    "description": {
      "content": "Translator's note: in Russia's most widespread grading system, there are four grades: 5, 4, 3, 2, the higher the better, roughly corresponding to A, B, C and F respectively in American grading system.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF991B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Translator's note: in Russia's most widespread grading system, there are four grades: 5, 4, 3, 2, the higher the better, roughly corresponding to A, B, C and F respectively in American grading system....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "译者注：在俄罗斯最普遍的评分系统中，有四种成绩：5、4、3、2，分数越高越好，大致分别对应美国评分系统中的 A、B、C 和 F。\n\n学期即将结束，学生们开始关注自己的成绩。今天，一位教授告诉学生，他的课程成绩将自动计算——他会计算本学期所有实验作业成绩的简单平均值（算术平均数），然后四舍五入到最接近的整数。四舍五入时会偏向学生：$4.5$ 会被向上取整为 $5$（如示例 3），但 $4.4$ 会被...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 100 $, be the number of lab work grades.\n\nLet $ g_1, g_2, \\dots, g_n \\in \\{2, 3, 4, 5\\} $ be Vasya’s current grades.\n\nDefine the arithmetic mean:  \n$$\n\\mu = \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments