PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
This problem can be solved by using DFS (Depth First Search). The number of states is much smaller than rN, and it works with **O(r * N *** the number of states) time, where r = 4 is derived from the values of the minimal X 10 and the required magical powers 666.
Some basic observations are here. Let ki be the minimal non-negative integer k such that Mi / 3k ≤ 666. We can consider that Ciel uses the help of the Evilbook for the i-th chef only before defeating the i-th chef. If Ciel already has enough magical power, Ciel must use at least max(0, ki - 1) helps before defeating the i-th chef, because Ciel may get at least 666 magical power after using ki - 1 helps if ki > 0. And Ciel must not use more than ki + r - 1 helps before defeating the i-th chef, because 666 / 3r-1 - (r-1) * X ≤ 0, so if used, Ciel’s magical power will be decreased. Therefore, when Ciel has no more than 666 magical power, each chef has only r states, undefeated, defeated with ki helps, defeated with ki + 1 helps, …, defeated with ki + r - 1 helps. So the total number of states is at most rN.
If the number of states is just 4N (at most 410 = 1048576), it seems a bit large. Indeed, we can check the number of states is much smaller. For example, if Mi ≤ 666/3, then the i-th chef has at most 3 states, because Ciel uses at most 2 helps for i-th chef. So, let Mi > 666/3, then at most 2 chef can have the state “defeated with ki helps”, because otherwise Ciel has at least 666 magical power. Therefore, we can prove that the number of states is at most 3N + N * 3N-1 + N * (N-1) / 2 * 3N-2 (at most 310 + 10 * 39 + 10 * 9 / 2 * 38 = 551124). Of course, the true number of states is smaller than it.
O(r * N * the number of states) time solutions can be accepted in the problem. If we would like to get more fast solutions, some prunings work fine. For example, let MaxEffiency be the maximal value of Mi / Ci over all undefeated chefs. Then we can use the lower bound of the answer, NowEffort + (666 - NowMagicalPower) / MaxEffiency. See the setter’s solution for details.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.