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

  • 11
  • Недоступна
Ура, задачи на алгоритмы! Их очень любят резиденты планеты Линейный Хаос. И вы должны любить, по крайней мере, до того момента, как пройдёте пару-тройку собеседований. Итак, у вас есть число из некоторого количества чисел. Нужно найти все числа меньше N, которые удовлетворили бы некоторому критерию (о нём узнаете в самой задаче!).
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (317)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Koval22 уровень, Брест
вчера, 12:52
на Integer.MAX_VALUE 500 миллисек и этого все равно мало(
Санек20 уровень, Одесса
позавчера, 08:00
9300000000000000000 в этот момент понимаешь, что самое время отстрелить себе ногу, выкинуть свой код и пойти другим путем (уже с одной ногой)
Kubik_1323 уровень, Москва
четверг, 21:08
отмучался ) я - 5080
steff20 уровень, Воронеж
четверг, 11:51
А давайте все дружно запустим проверку в одно время и валидатор глюканет 😀
Сабир24 уровень
11 февраля, 07:55
5056! Через боль и страдания! Сдал полностью в объектном виде. Весь диапазон от 0 до Integer.MAX_VALUE проверяется за 0.8с. Быстрей не смог. Весь диапазон до Long.MAX_VALUE проверяется за 2 часа 37 минут. Совести не хватило что бы подсунуть готовый массив, но и что бы отложить задачу тоже не хватило совести. В итоге 8 дней с ней работал. 3 последние неудачные попытки были из-за того, что валидатор хотел что бы я полученный массив предварительно ещё проверил на строгое соответствие "< N". Добавил в одну строчку через потоки
vasiliy24 уровень, Москва
3 февраля, 19:14
Спасибо большое всем за комментарии ранее. Задача заставляет сильно "причесывать" свой код, искать как отбросить лишние вычисления как можно раньше. Сначала кажется нерешаемой, когда при первом решении в лоб "вешает" машину. Также валидатор начинает принимать решение, когда еще программа работает больше 10 сек ( у меня по крайней мере) Разницы в рекурсивном и нерекурсивном алгоритме не заметил, разница несколько миллисек - у рекурсивного дольше. Многопоточность не использовал, возможно будет быстрее для 9 цифр генерирует за 75 миллисек. Из того, что помогло координально ускорить программу (в моем случае) 1. Составление статической матрицы перемножения [][] в начале программы - ускоряется вычисление степенной суммы потом 2. Составление своего списка цифр не перебором, а сразу генерировать (от сгенерированной ранее цифры) по принципу любая цифра в числе д.б меньше предыдущей Исключение сделал для нуля. Пример 888 -> 889 -> 890 -> 899 -> 900 -> 990 -> 999 -> 1000 -> 1100 -> 1110 -> 1111 -> 1112 и т.д. 3. Отсеивание полученных чисел по нескольким условиям (чтобы не генерировать потом лишнее) - делал переводом числа long в массив ing[] а) длина числа должна быть равна длине числа в степенной сумме - т.е. длинна обоих массивов должна совпадать б) количество одинаковых цифр должно быть одинаково в обеих числах - т.е. совпадать общее количество нулей, едениц, двоек и т.д. в) проверяем, чтобы число Long (степенная сумма числа) не ушла в минус 4. Далее перебираем цифры, комбинируя их из числа а) если в сгенерированном массиве на первом месте [0] пропускаем - получается чуть быстрее. б) если используем сортировку в комбинаторике - использовать методы "быстрой сортировки" Также почитать теорию про перестановки - помогли вот эти ссылки (тут были) https://acmp.ru/article.asp?id_text=198 https://ru.wikipedia.org/wiki/Алгоритм_Нарайаны http://algolist.manual.ru/maths/combinat/permutations.php http://shujkova.ru/sites/default/files/lec6.pdf
Сабир24 уровень
7 февраля, 13:12
Прошу объяснить пункт 2 на своем же примере (Пример 888 -> 889 -> 890 -> 899 -> 900 -> 990 -> 999 -> 1000 -> 1100 -> 1110 -> 1111 -> 1112 и т.д.) более подробно. У меня исходя из этой статьи получился вот такой список: 880 -> 888 -> 889 -> 890 -> 899 -> 900 -> 909 -> 990 -> 999 -> 1000 -> 1009 -> 1090 -> 1099 -> 1100 -> 1101 -> 1102 -> 1103 -> 1104 -> 1105 -> 1106 -> 1107 -> 1108 -> 1109 -> 1110 -> 1111 -> 1112 -> 1113 -> 1114 -> 1115 -> 1116 -> 1117 -> 1118 -> 1119 -> 1120 -> 1122 -> 1123 -> 1124 -> 1125 -> 1126 -> 1127 -> 1128 -> 1129 -> 1130 -> 1133 Специально взял на том же интервале что и в твоем примере, но у меня значительно больше числе получается для дальнейших проверок. Тот же переход от 1000 до 1100 мне не совсем понятен.
vasiliy24 уровень, Москва
8 февраля, 10:38
условно принимал в сравнение 0 за 10 - поэтому и получается такой ряд, также прибавление делал после наибольшего разряда - т.е после 1000 идет 1100, после 2000 -> 2200 > 2220 и т.д - нули всегда сзади, т.к. они условно больше любой цифры в числе. Пример: в данном числе 1009 - получается что последние цифры не соответствуют условию (10) > 9 и после 1000 должно быть 1100, тогда условие совпадает - цифры идут по возрастанию (0 приниматся за (10).
Сабир24 уровень
8 февраля, 17:43
А идея с "нули всегда сзади" просто отличная! Жаль переписывать уже лень. 7ая версия решения уже написана и до значения 999999999999L решает за 7.4с. Я сделал класс единичного разряда отдельной цифры в числе. И у этого разряда есть внутренние правила инкриментирования, и при увеличении текущего разряда до максимального (это 10) он у меня сбрасывается до текущего разрешенного, и при этом дает команду разряду слева либо создаться со значением 1 либо инкриментироваться соблюдая все те же правила... А на счет нулей я схитрил - каждый разряд при создании (а у меня каждый разряд числа это отдельный полноценный объект) получает некоторые свойства: первые три разряда числа получают разрешение быть нулями, а остальные разряды при создании объекта не получают это право😏 Короче подошел к решению самым объектным способом - алгоритмизации почти нет😂
vasiliy24 уровень, Москва
10 февраля, 04:28
Алгоритм достаточно простой - без создания объектов 1. запоминаем послед цифру в числе (number % 10) 2. инкрементируем число - (если послед цифра не 0 или 9 - дальнейшие вычисления..) 3. ЕСЛИ последняя цифра 0 или 9 - проверяем в отдельном маленьком методе соответствует полученное число правилу, что все цифры идут по возрастанию, нули последние (1234,1220, 12340 и т.п) - ДА - число получили, дальнейшие вычисления... - НЕТ - "проапрейдиваем" число до нужного в отдельном маленьком методе -например получилось число 10000001, после возвращаем 11000000; или из 1010 получаем 1100 и т.п. Проход и поиск для цифр с 9 знаками получается за 16 миллисек всего ( это без дальнейших вычислений) - для ускорения и незабивания памяти лучше сразу их делать (смотреть основной пост)
Oleg23 уровень, Санкт-Петербург
23 января, 11:05
https://acmp.ru/article.asp?id_text=198 если не знаете с чего начать, то возможно это поможет
Александр24 уровень, Воронеж
15 января, 20:44
Я должжен на вход дать любое число меньше Long.Max, а программа должна определитьб все числа от 0 до поданого мною числа, которые соответствуют условию сумма произведений цифр равна числу? Что то я не пойму условие как должна она рабоать ребят поясните плз
Haumi35 уровень, Санкт-Петербург
16 января, 15:01
в примере число 370. значит метод должен вернуть все числа от 0 < N < 370 которые удовлетворяют условию. Если вы введете Long.Max значит в интервале от 0 < N < Long.Max
Сиявуш35 уровень, Худжанд
15 января, 10:25
Решил копипастом но ничего не понял что вообще тут происходит ( жаль((( Там много коди все такое... ужас короче... из за этой задачи у меня пропала настроение. Ну надеюсь для меня не будет проблема на будущем!
Айдар22 уровень, Казань
5 февраля, 20:06
Отличный метод для программирования )))))))) таким методом весь курс можно за один день пройти )))
Сиявуш35 уровень, Худжанд
6 февраля, 05:04
Мой золотой метод не для всех задача))))))))))) только для избранных задач)))))))))))
Дмитрий22 уровень, Токио
15 января, 08:10
Решил все таки. Читал комменты, ужасно хотелось читернуть и ввести матрицу. Спасибо всем, кто своими комментами вдохновлял на полноценное решение. Коммент Даниила помог сильно (ниже). Конечно же сначала попробовал решить задачу в лоб, обычным перебором, и повесил машину))). Мое решение 7887мс. Какие моменты вынес из задачи: - 2 недели над одной задачей, в новогодние праздники это то еще удовольствие. - Метод getNumbers может вызываться в методе main неограниченное количество раз, и каждый раз он должен возвращать корректное значение. - Рекурсия... я наверное не очень умный, потому что как не боролся с ней, победить не смог. Сделал через массивы. Просто не смог в голове представить правильный алгоритм. - Через массивы сделать алгоритм, генерирующий число для проверки получилось. В голове представил крутилку, как шифр на замке чемодана)) Дальше было дело техники, как из отдельных цифр составить число для проверки. - Забыл про нули. В итоге нули просто добавлял в отдельном цикле. Посмотрел, что максимально может быть 3 нуля в числе. Когда проверочное число достигло 17 знаков, количество прибавляемых нулей стал убирать. - Узнал, что лонг может внезапно стать отрицательным (над этим бился дня 3). Как победить лонг так и не понял, пришлось на числах от 18 знаков вводить BigInteger. Кстати, я сначала переделал все методы, убрал long и поставил BigInteger, но по времени вылез за 20с. Тогда я на числах, длиной знаков до 17 сделал обычные вычисления, через long, а свыше через большие числа.