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

  • 11
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (177)
  • популярные
  • новые
  • старые
Для того, что бы оставить комментарий вы должны авторизоваться
Alex P22 уровень
вчера, 09:33
Let's think... In order to optimize calculations, we can reduce exponentials operations and results covered by some combinatory combinations. like ab~ba, abc~acb~bac~cab~bca~cba etc... We can store optimized results in XYZ matrix: x{0-9} - numbers in the decimal system. y{1-18} - for results of exponentiations for 18 bases (number of symbols in Long.MAX_V). z - for combinatory data. (We also can share matrix operations to threads) The good question is the nature of the combinatory type algorithm. Would it be good enough... It's a complex task...
Victoria Sedletskaya22 уровень, Одесса
четверг, 19:36
уже "Всего эту задачу решили 4137 учеников." одна из проверок потратилась на то, что числа в массиве были не строго меньше заданного числа, а <= Время работы алгоритма для максимального лонг у меня получалось от 8 до 12 секунд, не смотря на это валидатор принял (фух) мне кажется, за такие задачи надо больше материи давать :-) хотя, опыт бесценен
Pavel Soros22 уровень
8 ноября, 17:42
Сохраните в массив все возможные числа Армстронга в диапазоне Long.MAX_VALUE (их всего 50). Затем сравнивайте эти числа с переданным значением. Всё что меньше кладите в возвращаемый методом getNumber() массив. Это не очень честно. Но кто сказал что так нельзя. Валидатор принимает.
JamesBean22 уровень, Новосибирск
8 ноября, 16:03
Супер задача. Кучу времени потратил на нее, испробовал несколько вариантов. Но оказалось, что больше всего времени боролся с собственной глупостью - не чистил static переменную :-( - валидатор ругался, не принимал.
Bogdan Yushkov22 уровень, Екатеринбург
8 ноября, 16:08
Подскажи пожалуйста, как ты это сделал?)
JamesBean22 уровень, Новосибирск
8 ноября, 16:21
Написал коммент в вашем вопросе на обсуждение
Bogdan Yushkov22 уровень, Екатеринбург
8 ноября, 16:23
Спасибо)
JamesBean22 уровень, Новосибирск
8 ноября, 16:26
Удачи, надеюсь поможет. Сам я потратил 4 дня :-)
pca17323 уровень
19 сентября, 17:09
Здравствуйте! Не понятно для какого N должно быть < 10 c. ?
Максим27 уровень
22 сентября, 21:00
Для Long.MAX_VALUE
Ilya Sakharov41 уровень, Москва
17 сентября, 14:38
Какая жесть. Сделал. Читал все каменты, гуглил и т.п. Потратил 2 дня. Сделал два своих варианта. Первый вообще тормозной, второй быстро работает до Integer.MAX_VALUE, о Long только мечтать.. В итоге часть подглядел, часть от себя. Итог (для Long.MAX_VALUE): Time: 2178ms Total memory: 30Mb Кол-во чисел: 50 Потратил 3 попытки на борьбу с валидатором :(
urydmi22 уровень, Новосибирск
23 сентября, 14:46
чего хвастаешься, лучше бы советы давал
PSE36 уровень
26 октября, 09:45
ну ну!!!
Nataliya28 уровень, Киев
2 сентября, 20:49
Столько времени над этой задачей сижу... 18 секунд получается только. Меньше как-то никак. Мне уже ночью снилосн сегодня что малую мою мне нужно уложить в цикле 1000 раз )))) наверное хватит, пора идти дальше, а то уже сериализацию начала забывать.)
Andry Max35 уровень, Минск
13 августа, 01:28
сделал, запустил - работает, был рад, что с первого захода без проблем получилось, но условие про время и память игнорировал, в итоге как я и думал по этому пункту не прошёл. не знаю что менять, пришёл за подсказками)
4 августа, 10:14
Задача для меня показалась очень трудной. Решил с десятого раза И конечно все это было весьма познавательно. Когда решил понял что сложного в общем ничего.
Моряк Папай40 уровень
8 августа, 13:55
Вродь есть в условии: getNumbers должен возвращать все такие числа в порядке возрастания.
9 августа, 19:49
Значит сам виноват. Упустил :-) Благодарю поправил.
Павел31 уровень, Санкт-Петербург
30 июля, 20:45
Это были очень интересно проведённые сутки. В итоге я сдал. Очень помог юнит-тест, выложенный ниже. Нашёл с его помощью маленький недочёт. Сколько я всего перепробовал. Каждый шаг сокращал время выполнения на секунды, а иногда в десятки раз. Сперва я делал в лоб перебором в цикле и возведением в степень.Потом я добавил нити. Нашёл различные быстрые алгоритмы для второстепенных вычислений. Догадался сделал матрицу. Затем я решил проверить, сколько будет работать пустой цикл for i от 1 до Long.MAX_VALUE и понял, что всё, что я делал до этого - полная фигня. Нашёл я и ArmstrongNumbersMultiSetLongOpt, и статью про выкидывание чисел с другим расположением цифр. Но первое было как-то заумно сделано с адскими рекурсиями. А второе сразу не понял, как реализовать. В итоге, воспользовавшись идеями из этих двух источников, я стал копать дальше. Сделал генерацию чисел с возрастающим порядком цифр. Пытался перемешивать их различными алгоритмами. Эти решения всё равно были очень медленными, Integer.MAX_VALUE считался 120 сек. О long можно было только мечтать. Наконец, меня осенило, что ничего мешать не надо: если одни и те же цифры встречаются в числах одинаковое количество раз, то из одного числа можно составить другое. В итоге получилось 5 сек. для long. После оптимизаций я смог добиться 2,4 сек. Класс с гитхаба считает за 1, но я доволен своим результатом.
Павел31 уровень, Санкт-Петербург
30 июля, 20:52
Статические переменные использовать можно. Нити использовать можно. Поиск чисел у меня вообще во внешнем классе. Самое главное - результаты должны обнуляться перед каждый запуском getNumbers. Иначе валидатор не примет.