APPROVAL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are 5 judges in a reality show. You know the i-th judge will give you a score of A_i out of 10, but you can pay them 100 coins and make that a 10.
What’s the minimum number of coins you need to pay to ensure that your average score is at least 7 out of 10?

EXPLANATION:

Note that with 5 judges, an average of (at least) 7 out of 10 is equivalent to having the sum of scores be at least 35.

Each usage of 100 coins lets us set one judge score to 10, clearly it’s optimal to always set smaller scores to 10 before larger ones.

For convenience, let’s sort the scores, so that A_1 \leq A_2 \leq A_3 \leq A_4 \leq A_5.
Then,

  • If the sum of all A_i is already \geq 35, the answer is 0: no coins are needed.
  • Otherwise, set A_1 to 10 by spending 100 coins, and check if 10 + (A_2 + A_3 + A_4 + A_5) \geq 35 .
    If it is, 100 coins suffices; otherwise we need to bribe another judge.
  • The next bribe should be used to set A_2 to 10, and then run the check again.
  • If this still fails, set A_3 to 10, then A_4, and finally A_5 (though you’ll never actually reach A_5, since the first four being set to 10 already gives a sum of 40).

Or, in simpler terms: if k judges are bribed, it’s optimal to set A_1, A_2, \ldots, A_k to 10 (recall that A is sorted).
This results in a sum of 10\cdot k + (A_{k+1} + A_{k+2} + \ldots + A_5).
Try each k between 0 and 5, compute this quantity, and print the smallest k (multiplied by 100) for which it’s \geq 35.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    a = list(map(int, input().split()))
    a.sort()
    for i in range(6):
        if 10*i + sum(a[i:]) >= 35:
            print(100*i)
            break