In 1500A - Going Home, how can we construct a sequence of $$$n$$$ integers such that the answer is NO.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 20:23:38 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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