Educational Codeforces Round 112 — Question A

Правка en12, от astitva19, 2021-08-01 14:26:12

I had some issues with understanding Ques A from Edu Round 112, but I found a different way of approaching the problem.

Consider x,y,z to be the Pizzas ordered of slices 6, 8 and 10 respectively.

Thus we require:

$$$6x+8y+10z \leq n$$$

=> $$$ 2 \times (3x+4y+5z) \leq n$$$

We see that any integer k>=3 can be represented by the expression 3x+4y+5z with non negative values of x,y,z (atleast one such triplet x,y,z will always exist) .

(This observation is key to the approach. The proof of this observation is given at the end of this article.)

Thus, any even integer>=6 can be represented by 2*(3x+4y+5z) = 6x+8y+10z . #OBSV1

Now, we know that in order to minimize the time, we would want the number of final slices that we order to be as close to n as possible. In other words, we would want the extra slices we order (that take extra time to make) to be as close to 0 as possible.

If n is even (and >=6) then we can write it in terms of 2*(3x+4y+5z) exactly (#OBSV1); the number of extra slices we order will be 0.

If n is odd (and >6), then we cannot write n as 2*(3x+4y+5z) exactly because this expression will always give an even number. However, we can write n+1 as 2*(3x+4y+5z) exactly, making the number of extra slices we have to order just 1.

The total time taken would be 15x + 20y + 25z = 5*(3x+4y+5z). Thus, if we know the optimal answer for 3x+4y+5z ,we can easily calculate the total time by multiplying this by 5.

Hence, we have an algorithm:

-> If n<6 then we would have to order atleast the 6 slices pizza. Thus the minimum time possible for this case would be 15 mins directly.

-> Else If n is even then divide n by 2 and find the optimal value of 3x+4y+5z, or else if n is odd then divide (n+1) by 2 and find the optimal value of 3x+4y+5z.

-> Multiply the optimal value of 3x+4y+5z by 5 to get the minimum time to get atleast n slices.


Proof that any integer k >= 3 can be written in the form of 3x+4y+5z where x>=0, y>=0 and z>=0 :

This proof is trivial for the cases of k=3, k=4, k=5.

Thus consider k>=6.

By the division theorem:

$$$ k = 3 (\lfloor \frac{k}{3} \rfloor) + k\%3 $$$

=> $$$ k = 3(\lfloor \frac{k}{3} \rfloor - 1) + 3 + k\%3 $$$

Now 3 + k%3 can be either 3 or 4 or 5.

In either case, we have represented k as a linear combination of 3 , 4 and 5 i.e. k = 3x+4y+5z.

It can also be seen that in our representation x,y,z will be non negative integers.

Hence proved.

Теги #codingcontest, # solution

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский astitva19 2021-08-01 14:29:05 0 (published)
en14 Английский astitva19 2021-08-01 14:28:52 2 Tiny change: '.\n\n---\n### Appe' -> '.\n\n---\n\n### Appe'
en13 Английский astitva19 2021-08-01 14:28:27 16 (saved to drafts)
en12 Английский astitva19 2021-08-01 14:26:12 0 (published)
en11 Английский astitva19 2021-08-01 14:25:23 18
en10 Английский astitva19 2021-08-01 14:24:19 2
en9 Английский astitva19 2021-08-01 14:12:27 83
en8 Английский astitva19 2021-08-01 14:08:39 30
en7 Английский astitva19 2021-08-01 14:06:00 8 Tiny change: 're:\n\n 6x+8y+10z >= n\n\n=> 2*(' -> 're:\n\n $6x+8y+10z /leq n$\n\n=> 2*('
en6 Английский astitva19 2021-08-01 13:59:23 0 Tiny change: 're:\n\n 6x+8y+10z >= n\n\n=> 2*(' -> 're:\n\n ($6x+8y+10z >= n$)\n\n=> 2*(' (saved to drafts)
en5 Английский astitva19 2021-08-01 12:55:10 0 (published)
en4 Английский astitva19 2021-08-01 12:53:28 129
en3 Английский astitva19 2021-08-01 12:50:00 9
en2 Английский astitva19 2021-08-01 12:47:59 6
en1 Английский astitva19 2021-08-01 12:47:04 2383 Initial revision (saved to drafts)