PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You are given N standard six-sided dice and a value S.
You must do the following:
- Choose one face from each die, such that the sum of values of chosen faces equals S.
Then, overwrite each of the chosen faces with 0. - Then, once again choose one face from each die.
Your score is the sum of chosen values now.
Find the maximum possible score.
EXPLANATION:
The largest value present on each die is 6.
So, it’s in our best interest to not overwrite any 6 if we can help it.
When is this possible?
Well, assuming that we can only choose values in [1, 5], the lowest possible sum we can obtain is N, while the highest is 5N.
It’s not hard to see that any value in [N, 5N] can also be obtained as a sum: a simple construction is as follows:
- Start with x_1 = x_2 = \ldots = x_N = 1.
- Then, repeatedly increase x_1 by 1 till it reaches 5.
- After that, repeatedly increase x_2 by 1 till it reaches 5.
\vdots - Finally, repeatedly increase x_N by 1 till it reaches 5.
We started with a sum of N and ended with a sum of 5N.
Since each step increased the sum by exactly 1, this also means we went through every single value in [N, 5N], as desired.
This tells us that if S \le 5N, we can avoid touching 6 on any of the dice; so the answer in these cases will just be 6N.
What about the cases where S \gt 5N though?
To reach such a large sum S, observe that we need to choose the value 6 on at least (S - 5N) of the dice.
This is because, if we choose the value 6 on x of the dice, the maximum possible sum from the remaining dice is 5\cdot (N-x), and so we need 6\cdot x + 5\cdot (N-x) \ge S which reduces to x \ge S - 5N.
On the other hand, as long as we choose the value 6 from exactly S - 5N of the dice, the remaining dice can always achieve the remaining summation just using values in [1, 5]; so their 6's do not need to be touched.
In every die where we overwrote 6 the maximum value that can be chosen is 5, while in the remaining dice it’s 6.
So, when S \gt 5N, the answer equals 5\cdot (S - 5N) + 6 \cdot (N - (S - 5N)).
By expanding things out, this can be further reduced to just (11N - S), or the more intuitive
6N - (S - 5N) where for each extra value the sum goes beyond 5N, we must subtract 1 from the upper bound of 6N.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, s = map(int, input().split())
if s <= 5*n: print(6*n)
else: print(6*n - (s - 5*n))