Алгоритмы-числа

  • 11
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (232)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Роман Князев22 уровень, Санкт-Петербург
21 июня, 06:19
Читерство. Наверное не очень правильный путь, но сделал метод он отсчитал все значения до "Long.MAX_VALUE". Удаляем весь код, берем эти числа и делаем массив, далее уже просто проверяем число в массиве меньше входного, если да, то добавляем в массив)
Виталий Погодаев30 уровень, Владивосток
12 июня, 11:00
Два полных дня! Около 20 часов чистого времени! Это рекорд! Для тех, кто поймёт какой алгоритм даёт нужное быстродействие, и вроде бы вот всё уже работает, но зависает на входных данных свыше 10_000_000_000_000_000L, вероятно, вы, как и я, используете Math.pow(double, double) для возведения в степень! Этот метод тут не годится, так как он возвращает тоже double, и при числах более 16 знаков возникают ошибки округления при приведении к long! Ну и с 19-значными числами возможно придётся повозиться (мне пришлось). Остальное описано тут в комментах и в хелпе. П.С. на сегодня её решило 4519 чел.
Николай27 уровень
10 июня, 12:54
Задача сложная, но интересная. Из принципа решил сам, но опирался на алгоритм решения. В итоге решение не прошло из за того, что у меня 0 попадал в решение и максимальное количество знаков пришлось снизить с 19 до 17 иначе решение на несколько секунд дольше шло, чем нужно.
Евгений20 уровень, Днепр
6 июня, 20:28
Можно запилить bruteforce-алгоритм на майнинговой ферме и запрашивать у нее результат при надобности. Кстати, ASIC для такой задачи должен быть простой, как угол дома. :)
Даниил33 уровень
2 июня, 10:08
Постараюсь рассказать в кратце как это было у меня. Несколько месяцев назад потратил тупо весь день что бы понять задание, написать перебор в лоб и распаралелить. В итоге до Integer.MAX_VALUE считало помоему секунд 40-50. Так же для себя открыл (так как раньше этим вопросом не задавался) что результаты быстродействия работы лучше проверять тут на сайте чем на своём компе (что логично) так как лично у меня на компе было в 2 раза медленее. Потом решил к этой задаче вернуться снова. Спрашивал советов у людей тут на сайте и пытался изучать готовые решения, но ничего понять не мог. В итоге всё-таки с помощью советов написал своё решение реализовав вот этот алгоритм используя переборы цифр в числе перемудрёнными переборами ещё и вместе с рекурсией в одном маленьком участке кода. Но валидатор не принимал давая всякие непонятные советы. Потом подсказали проверить все ли значения у меня в итоге получаються при Long.MAX_VALUE. Оказалось, как я и предполагал, что этот предложеный выше алгоритм не перебирает числа с нулями вообще никак. Вот пример вывода моего алгоритма: 11 12 13 14 15 16 17 18 19 22 23 24 25 26 27 28 29 33 34 35 36 37 38 39 44 45 46 47 48 49 55 56 57 58 59 66 67 68 69 77 78 79 88 89 99 111 112 113 114 115 116 117 118 119 122 123 124 125 126 127 128 129 133 134 135 136 137 138 139 ... 688 689 699 777 778 779 788 789 799 888 889 899 999 1111 1112 1113 1114 1115 1116 1117 1118 1119 1122 1123 1124 1125 1126 1127 1128 1129 1133 1134 1135 1136 1137 1138 1139 ... 5899 5999 6666 6667 6668 6669 6677 6678 6679 6688 6689 6699 6777 6778 6779 6788 6789 и т.д. аж до 8999999999999999999L (надеюсь с колличесвтом девяток правильно написал). При таком переборе получаеться 6_906_889 значений. Оказываеться всего 50 чисел Армстронга от 1 до Long.MAX_VALUE у 6 из которых есть по 2 нуля, и у 2-х из них по 3 нуля (одним нулём там их не мало).
Даниил33 уровень
2 июня, 10:42
Короче если по делу, то просто я сделал ещё 3 разных метода (для чисел с 1-м нулём в конце, с 2-мя и с 3-мя соответственно). У каждый из этих методов перебирал 4_686_823 значений, 3_124_548 и 2_042_974 соответственно. Выглядил первый так, а другие по аналогии: 10 20 30 40 50 60 70 80 90 110 120 130 140 150 160 170 180 190 220 230 240 250 260 270 280 290 ... 770 780 790 880 890 990 1110 1120 1130 1140 1150 1160 1170 1180 1190 1220 1230 1240 1250 1260 1270 1280 1290 и в каждом из этих методов вызывал метод перебора без нулей после чего умножая результат на 10, 100, 1000 соответсвенно (ах да, числа от 1 до 9 я добавлял до перебора этих алгоритмов обязательно с учётом что если к примеру чисто N = 4, то результат будет 1, 2, 3). Для каждого метода написал отдельно тестовый код в main() что бы контролировать какую хрень я пишу, иначе ооочень легко где-то перепутать один знак и будешь долго не понимать что к чему (тем более своим замыленным глазом). Все эти методы и вспомогательные методы (расчёт суммы цифр и проверка на соответствие числу Армстронга) вызывал в методе getNumbers(long N). Так же расспаралелил всё это дело на (колличество доступных ядер - 1) используя ExecutorService, Callable, Future и даже разделяя большие диапазоны в 2, а то и в 3 раза на разные потоки (в моём случае в скорости прибавило). В общем обязательно проверить на любых входных данных (например 0, 4, 9, 10, 6234654, -1, -543 и т.п.). У меня приняло когда при невалидных значениях ( <= 0 ) возвращало массив размером 0 (так получилось только когда коллекцию нулевой длинны "скопировать" в массив). По времени выполнения на сайте было около 8 секунд, но что-то всё равно не принимал (писал что-то про "проверить нет ли ошибок в методе"). Потом после того как который раз всё проверив с выводом результатов, исправив реально пару ошибок, он не принимал я банально пробовал сдать передавая в параметры.
Александр Орлов22 уровень, Орёл
5 июня, 09:16
не понятна суть решения
Даниил33 уровень
5 июня, 10:10
Ну я прям всё решение старался и не раскрыть, а то может кто расстроится от того что прочитал уже готовую схему...
Владислав Пахомов26 уровень, Белгород
6 июля, 08:45
Можете подсказать алгоритм перебора пожалуйста?
Даниил33 уровень
6 июля, 09:14
Если честно, то я уже внятно не расскажу как я это сделал, память подводит. Могу скинуть ссылку на решение, но это лучше уже если вообще ничего не будет получаться после того как получиться реализовать самому алгоритм перебора. А вообще алгоритм состоит из того что видно из моего первого примера: - числа 1 - 9 можно сразу добавлять (если переданное число >= 9); - 10 в принципе можно не рассматривать если не знаешь как ег о красиво прикрутить (рассматривать прямо все числа тут не требуеться, по этому я и не делал проверку чисел у которых больше 3-х нулей есть); - перебираешь так 11, 12... 18, 19, дальше видишь остаток от деления на 10 == 9 значит пора увеличивать число что идёт на разряд выше, то есть на 20. Но в этот алгоритм и основывается на том что 21 к примеру мы уже рассмотрели, значит нужно начинать с 22. Вот и получаеться что накидываешь разряд тот что выше и младший разряд ставиться равным установленому старшему (итог - 22). Когда все цифры будут 9 (99 к примеру), то добавляеться ещё разряд (ещё одна цифра) и ставиться соответсвенно в 1. То есть 1хх. Ну а следующие младшие разряды ставятся по тому же принципу равными своему старшему разряду. То есть 111, и дальше всё заново идёт. Просто нужно проверять каждый разряд что бы он не был равным 9. Хотя как бы у нас не может быть числа 194 к примеру, будет только 199, значит проверяется только самый младший разряд и если он равен 9, то дальше идти по цифрам и проверять 9 там стоит или нет. Пример 1299: Самый младший 9, значит проверим старший. Его старший разряд тоже 9, значит проверим уже ЕГО старший разряд. ЕГО старший разряд - 2, значит накидуем к нему +1 и будет 1399 (или 1300, смотря как накидывать), и тогда уже все разряды что младше данного ставим в то же значение, то есть 1333.
Владислав Пахомов26 уровень, Белгород
6 июля, 11:49
Огромное спасибо, прямо надежду подарил))
Даниил33 уровень
6 июля, 17:52
У меня у самого надежда появилась только когда мне начали подсказывать) У самого ума не хватало...
Александр Орлов22 уровень, Орёл
20 мая, 10:28
Читал вот эту статью https://acmp.ru/article.asp?id_text=198, понял, что не нужно в лоб перебирать все числа от 0 до Long.MAX_VALUE. Не могу понять, как реализовать исключение повторной проверки. Пример из ссылки выше: 135, 153, 315, 531, 513. Создаём массив чисел из цифр 1, 3 и 5. Находим степенную сумму первого числа, и сравниваем её с каждым элементом этого же массива. Вот положим программа отработала число 152 и переходит к 153. По идее его не нужно уже проверять, так как 153 было проверенно в рамках массива числа 135. Если создать ещё один массив и туда складывать все проверенные числа, а потом проверять входит ли число, с которым программа работает в настоящий момент в этот массив проверенных числе, то как мне кажется я вернусь к тупому перебору от 0 до Long.MAX_VALUE
Даниил33 уровень
22 мая, 19:01
Сам сижу над этой проблемой... Уже 3-й подход делаю к этому заданию. Сделал уже абсолютно всю логику программы, осталось только реализовать тот самый метод который будет возвращать следующее число для перебора принимая у себя в параметрах предыдущее. Пока в качестве затычки сделал банальное ++ что бы проверить как остальной код работает. Мне подсказки дали "по какой схеме примерно должен происходить перебор" которые уточняют как исключить повтор к примеру числа 32 если ранее уже было число 23, но пока я так и не родил( P.S. Тестирование на скорость выполнения лучше делать тут на сайте в окне с кодом. У меня на ноуте в разы хуже результаты тестирования.
Mark35 уровень, Санкт-Петербург
15 мая, 00:00
Два дня как то жестко на такую задачу. Ну вечер - да, получилось 3.5 сек. Секунду примерно занимает генерация и 2.5 - проверка на соответствие числам Армстронга. Распараллеливание проверки с ThreadPoolExecutor ничего не дало кроме дополнительного времени. Видимо создавать новые объекты Runnable затратнее, чем все в одном потоке выполнять.
Dmitry Potamoshnev30 уровень, Москва
3 июля, 14:39
не всем мы такие гении
MrKermit20 уровень, Москва
11 мая, 12:22
Пробил днище) Вы решили задачу лучше, чем 2% учеников. Решил через ArmstrongNumbersMultiSetLongOpt Отличная задача для математической олимпиады.
Александр22 уровень, Минск
4 мая, 23:34
лютый, лютый хардкор!!! несколько раз хотел плюнуть и использовать готовый массив, но упрямству хвала. короч, ниже уже писали, но всеже: 1 матрица степеней 2 рекурсия, ну или типо того что получилось сочинить самому (может и не очень красиво, но свое) 3 сначала все расчеты в солюшене в статике, а только потом тело метода, иначе никак. я так понял что валидатор запускает сразу несколько вариантов, поэтому даже если Long.MAX как его Value удалось впихнуть в 9-8-7 секунд, то если валя их запустит несколько то всеравно время не хватит 4 ну и нуля нет, и меньше N ( т.е. 1,2,3,4... подходит, а 0,1,2,3,4... нет) (решил без нитей, 8 секунд)
Александр22 уровень
18 мая, 11:36
кинь плз в личку свой код
Justinian35 уровень, Киев
2 мая, 03:43
"Это не наши" (c) Хороша задачка. Чуток запутал меня валидатор, я не проходил по времени, но все-равно тыцал на кнопку, чтобы посмотреть что там пишет, сначала писало ("превышено время") ну это понятно, первоначальный мой алгоритм около 1000 лет должен был работать. А потом начало писать "Проверьте что программа работает на всех входных данных и нету исключений", благо интуиция в очередной раз не подвела, хотя чуток и потратил время на поиск экспшенов и какое такое значение может быть больше Long.MAX и меньше Long.MIN чтобы смутить алгоритм. А оказалось.....что просто не проходило по времени. Как только я влез в 10 секунд, все приняло на ура. Ну и ладно, слава Богу ) Когда-то вернусь и перепишу, рекурсия аж просится сюда, у людей по полсекунды считает, а я со своими массивами еле в 9 секунд влез.
Anonymous #37410529 уровень, Амстердам
2 мая, 13:19
У меня как раз без рекурсии не получилось. Честно пытался из спортивного интереса - никак. С рекурсией 1.7 секунды и код компактный.
Justinian35 уровень, Киев
2 мая, 14:22
Перебирать рекурсией или нет думаю не столь важно, сколько как именно, с помощью каких конструкций происходит сам перебор и обработка. Решение в лоб при неоптимизированном алгоритме поиска и с использованием массивов, некоторых методов стринг , лишнего парсинга и тд, это около 20 секунд. Просто нужно дебажить найденные последовательности, тут все упирается в алгоритм поиска, есои там закралась ошибка, то время на порядки будет возрастать. Единственным плюсом решения в лоб, массивы или без них(но без рекурсии), это читаемость и простота реализации. На это решение навести других легче. Но это классические задачки процедурного стиля, читаемость здесь не нужна, если кто знает алгоритм, он его узнает. Кто не знает этого алгоритма, тому мало что поможет )
Intoxikot22 уровень, Челябинск
3 июля, 03:14
Код дадите глянуть? Я уже все кнопки на клавиатуре стер и перепробовал мыслимые и немыслимые варианты в различных сочетаниях. Но как воплотить рекурсию в этой задаче мне сложно представить. Шел третий день