ИНТЕРЕСНЫЕ ЧИСЛА. Назовём натуральное число X (X > 9) "интересным", если цифры в его десятичной записи ненулевые, попарно взаимно простые и их попарные суммы — простые числа. Например, число 114 является интересным, а числа 115, 124 — нет.
Найдите N-ое (1 <= N <= 2018) интересное число. Пример: 3 -> 14
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:06:45
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
18:06:45
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 23:28:16 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
Напишем простой перебор, который покажет все интересные числа до $$$10^7$$$. Заметим, что все интересные числа либо двузначные, либо удовлетворяют регулярному выражению
1*[1246]1*. Скорее всего, это можно строго доказать, но мне лень(Руками выкинем все двузначные. Из общего вида интересных чисел следует, что количество интересных чисел длины $$$n$$$ Равно $$$3 \cdot n + 1$$$. Из этой информации вы можете получить длину числа. В вашем случае сработает простой линейный перебор, однако для больших ограничений можно было бы использовать бинпоиск, или даже придумать явную формулу.
Затем осталось понять, какое именно у вас число, если известна его длина. Вы можете его явно перебрать, однако опять же, при больших ограничениях работал бы бинпоиск или явная формула.
Асимптотика решения: $$$O(n)$$$ если все просто перебирать, $$$O(\log{n})$$$, если придумать бинпоиск и $$$O(1)$$$, если придумать формулу.
Строгое доказательство такое. Пусть есть интересное число, в котором больше одной не единичной цифры. Заметим, что если выкидывать цифры из числа, то это на интересность никак не влияет — она не может исчезнуть, только появиться. Будем выкидывать единицы либо пока они есть, либо пока число не станет трехзначным. Если кончились единицы, то будем выкидывать что угодно, пока число не останется трехзначным. Итого мы получили трехзначное интересное число, в котором хотя бы две не единичные цифры, а наш перебор показал, что таких чисел нет, противоречие.
Аналогичное рассуждение работает, если предположить, что в числе оказалась цифра не из множества $$$[1246]$$$.
Спасибо большое за вашу помощь.
Я то могу, но какой в этом смысл? Для меня обучающей ценности эта задача не несет — я уже легко умею реализовывать подобное. Если я дам вам свой код, то вы, скорее всего, просто его сдадите в систему, возможно предварительно прочитав, но ничего не запомнив из этого полотна кода.
Гораздо лучше будет, если вы сами его напишете. Во-первых, я не потрачу свое бесценное время на простую задачу, а во-вторых, вы научитесь ее решать. Поверьте, так будет эффективней.
Если хотите, могу скинуть код моего перебора. Вот он:
Огромное спасибо! Можете объяснить
vector p = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1};
$$$p[i] = 0$$$, если число $$$i$$$ составное; $$$p[i] = 1$$$, если $$$i$$$ простое.
UPD. Ошибся, разумеется $$$0$$$ и $$$1$$$ не являются составными числами.
Формально говоря, не так. $$$p[i] = 1$$$, если $$$i$$$ простое, и $$$p[i] = 0$$$ если $$$i$$$ не простое.
Вообще мне нужна была таблица простых чисел до $$$20$$$, но было очень лень реализовывать Эратосфена, поэтому я ее руками вбил.
Можно ссылку на задачу?
https://olymp.krsu.edu.kg/ContestProblemset.aspx?contest=151 Задача Е.Кызыктуу сандар = Интересные числа. Если открыть задачу с формата (pdf).На первом листе киргизский вариант , а на следующем листе имеется русский вариант.