| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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.net/problemset/problem/194/A
I was looking at the editorial here — http://codeforces.net/blog/entry/4673 I don't understand the logic behind "3n-k" being used.
Can anyone please help?
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.
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?
If k > 3*n we can set all the values to 3 and still have some of the sum left.
ex: n = 5, k = 18
First we set all of the values to 3: 3 3 3 3 3 ( sum = 3*n = 15 ) Then we increase them from left to right until we reach the sum k since all the values are already > 2 we'll never have to resit an exam.
That makes sense. Thanks :) . When you explained that, it became obvious :) .....
Np, good luck solving problems :)