Here i am with my second editorial on CHEFUNI . It will also be kind of guideline how to approach when you cant disprove yourself but get WA. One advantage I had was that the testcase generation and verifying was pretty simple. Anyways letβs proceed.

**SOLVING SUBTASK 1:** Solution of subtask 1 is pretty simple. Just do a dp with the recursion

**F(x,y,z)=min(F(x-1,y,z)+a,F(x,y-1,z)+a,F(x,y,z-1)+a,F(x-1,y-1,z)+b,F(x-1,y,z-1)+b,F(x,y-1,z-1)+b,F(x-1,y-1,z-1)+c)**

**Complexity=O(n^3)**

**SOLVING FOR 100 POINTS:**

As the constraints suggest its clearly O(1) per query or rather OΒ© where c can be upto 1000. Now as one can guess its clearly greedy. So lets approach slowly towards the correct solution just like i did. Sort such that **x<y<z**. First of all one can easily think why only one of 5 possibilities are there:

- Take all βaβ type steps: Cost=(x+y+z)*a
- Take combination of βaβ and βbβ type steps: Two possibilities: 1)when
**z>(x+y)**we can take only**(x+y)**βbβ type steps rest we need to take βaβ type steps. 2)else we can take**(x+y+z)/2**βbβ type steps and**(x+y+z)%2**βaβ type steps. - Take combination of βaβ and βcβ type steps: We can take atmax x βcβ type steps and rest βaβ type.
- Take combination of βaβ and βbβ and βcβ type steps. Now this is where things get tricky. First we all would think of taking greedily as many βcβ type steps as possible, followed by greedy choosing of βbβ type steps and rest βaβ type steps. But this gives WA. You can use your bruteforce solution generating random testcases to see that there are cases where actually this greedy assignment doesnot work. A little brainstorming gives you the reason. What if **a is greater than b and c ** by such an amount that this greedy assignment cost increases because of choosing so many βaβ type steps. The count being ** (z-y) **. (Proof is left for readers). Now our main aim will be to reduce βaβ type steps. But HOW?? By compensating a few βcβ type steps and changing them into βbβ and βaβ type steps such that overall count of βaβ type steps gets reduced. Now greedy choosing of βcβ ,βbβ, and βaβ type steps, we had to take x βcβ type steps (y-x) βbβ type steps and (z-y) βaβ type steps. Now suppose we do not take the (z-y) βaβ type steps. The point where we stand we have to move more (z-y) steps along z direction. Let us take away
**k**βcβ type steps from this position i.e. we move diagonally in reverse direction by k steps. From the point we are at we need to take more k steps along x direction, k steps along y direction and k+(z-y) steps along z direction. So considering this pt. as the origin our destination is at (k,k,k+z-y). Now we take the remaining steps to be of βbβ and βaβ types. Now we discussed a point before that taking βbβ and βaβ type steps had 2 conditions- z>(x+y) and z<=(x+y) where in the latter we needed only (x+y+z)%2 steps of βaβ type. So for minimizing βaβ type steps we must satisfy**z<=x+y**. Or, k+z-y<=2*k which implies**k>=(z-y)**. So if we take away more than (z-y) βcβ type steps we might find an optimal ans. Now here i used a bit complexity analysis. Seeing atmax O(1000) per query is permissable i ran a loop from (z-y) to (z-y+1000) seeing when i get the optimal ans. Here is the code to that. Then later i verified at (z-k) only it gives minimum. Here . IDK THE PROOF FOR UPPERBOUND. If anyone has proved this kindly share please - The last case is from the relation 3b=2c i.e. we can compensate 2 βcβ type steps by taking 3 βbβ type steps. So we will be left with (2c)%3 βcβ type steps which can be 0,1 or 2. 0 case being greedy choosing of βaβ and βbβ type steps. So we need to handle the case of 1 βcβ and rest βbβ and βaβ and case of 2 βcβ and rest βbβ and βaβ seperately.

Finally min of all above cases gives the ans.

**COMPLEXITY: O(1) per query **

If anyone has better solution please share