{"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.\n\nThe 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$.\n\nThis 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.\n\nHelp Vasya — calculate the minimum amount of lab works Vasya has to redo.\n\n## Input\n\nThe first line contains a single integer $n$ — the number of Vasya's grades ($1 \\leq n \\leq 100$).\n\nThe second line contains $n$ integers from $2$ to $5$ — Vasya's grades for his lab works.\n\n## Output\n\nOutput 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$.\n\n[samples]\n\n## Note\n\nIn the first sample, it is enough to redo two lab works to make two $4$s into $5$s.\n\nIn the second sample, Vasya's average is already $4.75$ so he doesn't have to redo anything to get a $5$.\n\nIn 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$.","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$ 会被向下取整为 $4$。\n\n这对瓦夏来说并不乐观，因为他没想过这些实验作业会有什么影响，所以他可能得到低于 5 的成绩（甚至可能得到可怕的 2）。然而，教授允许他选择重做部分作业以提高平均分。瓦夏希望尽可能少地重做作业，以便获得课程的 5 分。当然，瓦夏选择重做的作业都会得到 5 分。\n\n请帮助瓦夏——计算他最少需要重做多少次实验作业。\n\n第一行包含一个整数 $n$ —— 瓦夏的成绩数量（$1 lt.eq n lt.eq 100$）。\n\n第二行包含 $n$ 个从 2 到 5 的整数 —— 瓦夏的实验作业成绩。\n\n请输出一个整数 —— 瓦夏最少需要重做的实验作业数量。可以证明，瓦夏总可以通过重做足够多的作业来获得 5 分。\n\n在第一个样例中，只需重做两次作业，将两个 4 变为 5 即可。\n\n在第二个样例中，瓦夏的平均分已经是 $4.75$，因此他无需重做任何作业即可获得 5 分。\n\n在第三个样例中，瓦夏需要重做一次作业，去掉一个 3，这样平均分恰好变为 $4.5$，最终成绩即为 5。\n\n## Input\n\n第一行包含一个整数 $n$ —— 瓦夏的成绩数量（$1 lt.eq n lt.eq 100$）。第二行包含 $n$ 个从 2 到 5 的整数 —— 瓦夏的实验作业成绩。\n\n## Output\n\n请输出一个整数 —— 瓦夏最少需要重做的实验作业数量。可以证明，瓦夏总可以通过重做足够多的作业来获得 5 分。\n\n[samples]\n\n## Note\n\n在第一个样例中，只需重做两次作业，将两个 $4$ 变为 $5$ 即可。在第二个样例中，瓦夏的平均分已经是 $4.75$，因此他无需重做任何作业即可获得 5 分。在第三个样例中，瓦夏需要重做一次作业，去掉一个 $3$，这样平均分恰好变为 $4.5$，最终成绩即为 5。","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 = \\frac{1}{n} \\sum_{i=1}^n g_i\n$$\n\nThe final grade is computed as:  \n$$\n\\text{final} = \\lfloor \\mu + 0.5 \\rfloor\n$$  \n(i.e., rounding to the nearest integer, with **half-up** rounding: $ 4.5 \\rightarrow 5 $, $ 4.4 \\rightarrow 4 $).\n\nVasya may replace any subset of his grades with $ 5 $.  \nLet $ k \\in \\mathbb{N}_0 $ be the number of grades replaced.\n\nObjective: Find the **minimum** $ k $ such that after replacing $ k $ of the grades with $ 5 $, the resulting mean $ \\mu' $ satisfies:  \n$$\n\\mu' \\geq 4.5\n$$\n\nLet $ S = \\sum_{i=1}^n g_i $ be the initial sum.\n\nAfter replacing $ k $ grades (each originally $ g_i \\leq 4 $) with $ 5 $, the new sum is:  \n$$\nS' = S + \\sum_{j=1}^k (5 - g_{i_j}) \\quad \\text{for some } g_{i_j} \\in \\{2,3,4\\}\n$$\n\nTo minimize $ k $, we should choose the $ k $ grades with the **largest possible improvement** (i.e., replace the smallest current grades first).\n\nDefine the **improvement potential** for each grade $ g_i $ as $ 5 - g_i \\in \\{0,1,2,3\\} $.  \nSort the grades in ascending order (i.e., prioritize replacing 2s, then 3s, then 4s).\n\nLet $ d_1 \\geq d_2 \\geq \\dots \\geq d_n $ be the sorted list of improvements $ 5 - g_i $ in descending order.\n\nFind the smallest $ k \\in \\{0, 1, \\dots, n\\} $ such that:  \n$$\n\\frac{S + \\sum_{i=1}^k d_i}{n} \\geq 4.5\n$$\n\nEquivalently:  \n$$\nS + \\sum_{i=1}^k d_i \\geq 4.5n\n$$\n\nOutput: the minimal such $ k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF991B","tags":["greedy","sortings"],"sample_group":[["3\n4 4 4","2"],["4\n5 4 5 5","0"],["4\n5 3 3 5","1"]],"created_at":"2026-03-03 11:00:39"}}