In 1500A - Going Home, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 22:31:23 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
We can construct an increasing sequence such that each element is strictly greater than sum of previous numbers . But that will increase exponentially.
Well, that won't fulfill the constraint as $$$a_i <= 2.5*10^6$$$ needs to satisfy
largest $$$n$$$ value test case in problem with answer "NO" was $$$1572$$$ . $$$n$$$ in worst case could be $$$2*10^5$$$ . So at an average numbers are around $$$12.5$$$ distance apart (for worst case $$$n$$$) which increases difficulty of finding such sequence satisfying the constraint.
Not completely sure but I don't think we can, it is guaranteed to have an answer if n is greater than some limit (you can calculate that), because of the pigeon hole principle.
Yeah, I know. But, for N <= 1572, we can have NO. And we need to find a sequence having the answer No for those N
The sequence of alternate prime nos. (2, 5, 11, 17...) works! Edit: Changed 19 to 17
You're looking for a Golomb ruler. There are many ways of constructing such a ruler (apart from the one mentioned in the link I just gave), for instance:
n = 4. a = {1, 10, 100, 1000} Clearly works.
I mean, satisfying the problem constraints($$$a_i <= 2.5*10^6$$$)is needed