| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Problem link: https://mirror.codeforces.com/problemset/problem/2181/B
I'm specifically not able to make sense of this claim
In each pair of moves, at least the maximum is subtracted from the sum of all N numbers. Therefore, the total sum is multiplied by at most $$$1 − \frac{1}{N}$$$ in each step.
I've tried getting AI to explain it to me but it keeps getting confused as well :((
Auto comment: topic has been updated by project2400 (previous revision, new revision, compare).
Auto comment: topic has been updated by project2400 (previous revision, new revision, compare).
Let $$$S$$$ denote the sum of elements in play. The maximum element must be at least $$$\frac{S}{N}$$$. After one turn, the sum goes from $$$S$$$ to ($$$S$$$ minus max element), which is at most $$$S - \frac{S}{N}$$$; that is, S is multiplied by a factor of at most $$$1 - \frac{1}{N}$$$. So the maximum possible number of turns is $$$\log_{(1 - \frac{1}{N})^{-1}} S$$$, which after change of base, yields the subsequent arithmetic.