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

  • 11
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (218)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
понедельник, 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
Даниил29 уровень
позавчера, 19:01
Сам сижу над этой проблемой... Уже 3-й подход делаю к этому заданию. Сделал уже абсолютно всю логику программы, осталось только реализовать тот самый метод который будет возвращать следующее число для перебора принимая у себя в параметрах предыдущее. Пока в качестве затычки сделал банальное ++ что бы проверить как остальной код работает. Мне подсказки дали "по какой схеме примерно должен происходить перебор" которые уточняют как исключить повтор к примеру числа 32 если ранее уже было число 23, но пока я так и не родил( P.S. Тестирование на скорость выполнения лучше делать тут на сайте в окне с кодом. У меня на ноуте в разы хуже результаты тестирования.
Mark35 уровень, Санкт-Петербург
15 мая, 00:00
Два дня как то жестко на такую задачу. Ну вечер - да, получилось 3.5 сек. Секунду примерно занимает генерация и 2.5 - проверка на соответствие числам Армстронга. Распараллеливание проверки с ThreadPoolExecutor ничего не дало кроме дополнительного времени. Видимо создавать новые объекты Runnable затратнее, чем все в одном потоке выполнять.
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 секунд)
Александр20 уровень
суббота, 11:36
кинь плз в личку свой код
Justinian29 уровень, Киев
2 мая, 03:43
"Это не наши" (c) Хороша задачка. Чуток запутал меня валидатор, я не проходил по времени, но все-равно тыцал на кнопку, чтобы посмотреть что там пишет, сначала писало ("превышено время") ну это понятно, первоначальный мой алгоритм около 1000 лет должен был работать. А потом начало писать "Проверьте что программа работает на всех входных данных и нету исключений", благо интуиция в очередной раз не подвела, хотя чуток и потратил время на поиск экспшенов и какое такое значение может быть больше Long.MAX и меньше Long.MIN чтобы смутить алгоритм. А оказалось.....что просто не проходило по времени. Как только я влез в 10 секунд, все приняло на ура. Ну и ладно, слава Богу ) Когда-то вернусь и перепишу, рекурсия аж просится сюда, у людей по полсекунды считает, а я со своими массивами еле в 9 секунд влез.
Anonymous #37410529 уровень, Амстердам
2 мая, 13:19
У меня как раз без рекурсии не получилось. Честно пытался из спортивного интереса - никак. С рекурсией 1.7 секунды и код компактный.
Justinian29 уровень, Киев
2 мая, 14:22
Перебирать рекурсией или нет думаю не столь важно, сколько как именно, с помощью каких конструкций происходит сам перебор и обработка. Решение в лоб при неоптимизированном алгоритме поиска и с использованием массивов, некоторых методов стринг , лишнего парсинга и тд, это около 20 секунд. Просто нужно дебажить найденные последовательности, тут все упирается в алгоритм поиска, есои там закралась ошибка, то время на порядки будет возрастать. Единственным плюсом решения в лоб, массивы или без них(но без рекурсии), это читаемость и простота реализации. На это решение навести других легче. Но это классические задачки процедурного стиля, читаемость здесь не нужна, если кто знает алгоритм, он его узнает. Кто не знает этого алгоритма, тому мало что поможет )
Андрей Старжинский22 уровень, Киев
26 апреля, 14:37
Где в условии говориться хоть слово о диапазоне до N-го числа? Ограничение по времени и памяти есть, а вот о самом диапазоне вообще ничего не сказано. Сиди и гадай называется... Может до 1М за 10 секунд - это нормально. Оказывается, что нет.
Konstantin24 уровень, Одесса
27 апреля, 18:14
"среди натуральных чисел меньше N (long)"
Konstantin24 уровень, Одесса
22 апреля, 13:45
У меня возник нескромный вопрос - какое отношение данная задача имеет к теме уровня - Сериализация? Более того, курс обучает языку программирования Java, но никоим образом не намекает на наличие в них курса алгоритмов. При попытке найти в нэте применение данных чисел не нашёл ничего, т.е. задача носит чисто академический характер аля "вынос мозга". Ну и в конце концов задача была решена в течении часа, но из-за ограничений накладываемых условиями задачи на время выполнения и размер используемой памяти выполнить задание оказывается задачей нетривиальной. Всё больше возникает вопрос - курс о чём? О Java? Или обо всём что пришло в голову разработчикам курса? Хоть бы прикрутили сериализацию к примеру ради приличия.
Tom Riddle23 уровень, Москва
18 апреля, 11:52
Честно не осилил. Написал не оптимизированный вариант, дал ему отработать. Потом сделал статичный массив с ответами и скормил его Вале. Можно конечно убить пару дней на оптимизацию алгоритма, но ИМХО такое делать не прочитав сначала хорошую теорию по алгоритмам - просто расточительство времени.
Николай22 уровень
14 апреля, 11:20
Можно использовать кэш )) Сначала сгенерируем все значения числа Армстронга простым перебором, потом положим их тупо в массив в коде. И работать будем чисто с известным массивом. Правда это читерство. И как оказалось судя по комментариям - это лучший вариант для большинства.
Александр23 уровень, Казань
11 апреля, 15:12
Много дней потравил и всё же сдал. Самая хардовая задача пока что для меня. Совет: Натуральные числа это от 1 до N - N не включается по заданию.
System.out.println(Arrays.toString(getNumbers(100)));
System.out.println(Arrays.toString(getNumbers(1000)));
[1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
git