Блог пользователя traynmslf

Doubt regarding this problem : http://codeforces.me/problemset/problem/194/A

Автор traynmslf, история, 10 лет назад, По-английски

Hi Everyone,

I'm a newbie here.I just started solving Div 2 A problems. I solved the following problem using a brute force approach. http://codeforces.me/problemset/problem/194/A

I was looking at the editorial here — http://codeforces.me/blog/entry/4673 I don't understand the logic behind "3n-k" being used.

Can anyone please help?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

If k > 3*n the sum is big enough such that we can only use exams with value > 3 which means that we won't resit any exam.

Otherwise, we'll consider all the exams as having value 3 and decrease their value by 1 from left to right by 1 until their sum is equal to k also adding 1 to a counter.

ex: n = 4, k = 8 -> 3 3 3 3 ( sum 12 ) we'll need to decrease all the values by 1 in order for their sum to be 8.

So the question because how many times do you need to decrease the sum ( 3n ) in order to make it equal to k which is by definition equal to their difference.

→ Ответить
  • »
    »
    10 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Hi There. Thanks for the response. I understand the case for k<=3*n. If k>3*n, isn't there a possibility of having to resit an exam. For eg., n =5,k= 18 .Here k>3*n. We could use 4 4 4 4 2. I understand that, here the ideal solution would be to use 4 4 4 3 3. What I am trying to understand is, why is it that there will always be a solution without the need for a '2' when k>3*n. Is there something that I am missing in the question or may be there is some trivial proof?

    → Ответить