Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Матус Даниил Дмитриевич, 22 июля 2020 г. 12:57:11
     4 Жуков Александр И, 05 февраля 2018 г. 23:44:43 3^15 * 15 = 215.233.605 - это в несколько раз меньше 10^9, а именно столько операций делает программа за одну секунду. Или я не прав? Если это так, то простой перебор должен решать задачу (но он не решает) вы не правы за 1с проходит только 10^8 а значит данный код пройдет более чем за 2с
  2  Зинов Вадим, 08 июля 2020 г. 19:55:37
     Сложная задача. Надо на 2 умножать уметь(
  3  Яндулов Богдан, 19 июля 2018 г. 18:29:44
     Решил техникой meet-in-the-middle с асимптотикой O(M*2^(M/2)). В худшем случае не более 500 000 операций.
     Вы решили за O(M*2^M). А можно чуть лучше за O(M*3^(M/2)).
  4  Жуков Александр И, 06 февраля 2018 г. 0:02:38
     Решает рекурсия - перебор с отбросом заведомо не подходящих
  5  Жуков Александр И, 05 февраля 2018 г. 23:44:43
     3^15 * 15 = 215.233.605 - это в несколько раз меньше 10^9, а именно столько операций делает программа за одну секунду. Или я не прав? Если это так, то простой перебор должен решать задачу (но он не решает)
  6  Беляев Сергей Николаевич, 07 декабря 2015 г. 18:36:47
     
     Добавлены новые тесты. Все решения перетестированы.
  7  Снытко Максим Александрович, 04 февраля 2012 г. 14:33:05
     Ууу... месяц не мог найти ошибки... а ошибка в том, что я min:=16 когда нужно min:=31;
  8  Пересадин Илья, 01 мая 2010 г. 16:08:53
     Я просто в шоке после решения этой задачи...... Столько нового узнал для себя....
     Это хорошо.
  9  Пересадин Илья Валерьевич, 08 февраля 2010 г. 18:56:03
     Подскажите,здесь сортировать надо? Если надо,то как???
     Ну можете и отсортировать, наверное лучше по убыванию.
  10  Шайхиев Айдар Аликович, 28 января 2010 г. 13:09:29
     а числа А1 ,А2 идут в порядке возрастания?
     вовсе не обязательно
  11  Прищенко Богдан Олегович, 02 октября 2009 г. 16:31:55
     Можно бы добавить пару "крайних" тестов, а то у меня прошла лобовая проверка в пределах лонгинта, если же дать, например, 15 числе около миллиарда, то будет преполнение лонгинта при обычном суммировании, и, например, учитывая особености компиляторов и кодинга, были бы и WА, и RE. Простой пример - если при переполнении идет "по новому кругу снизу" (после максинта идет 0-максинт), то можно сделать такой тест, в котором будет "несколько переполнений" и маленькое число, и получится, что денег недостаточно, хотя в реальности это не так. Ну и еще несколько похожих тестов.
  12  Демиденко Виталий, 23 февраля 2009 г. 15:03:43
     И прошло за 0.01 последний тест
  13  Демиденко Виталий, 23 февраля 2009 г. 15:02:07
     А моя сложность 2^M * M
  14  Грачев Владимир Алексеевич, 30 января 2009 г. 18:21:52
     Знаете,крайне странно.С типом лонгинт на числах программа работала чуть более 1 сек.Поставил интегер - и она прошла.Хотя в Дельфи по идее оба типа вмещают одни и те же числа.
     Да не странно, просто ваша программа прошла за время, чуть меньшее 1 сек, что допустимо. Более эффективная реализация алгоритма может привести к более стабильной сдаче. Т.е. эффективное решение этой задачи приводит к тому, что она сдается за 0.1 сек.
  15  Степанов Егор Владимирович, 14 января 2009 г. 8:08:35
     перебор подмножеств не прошел (((
     Это смотря насколько разумно перебирать.
  16  Нагин Сергей Юрьевич, 29 декабря 2008 г. 0:44:46
     тут сложность : 3^m
     да
  17  Кожаев Г.М., 28 июля 2008 г. 21:21:35
     Попарно разные - значит в массиве А могут быть одинаковые числа?
     Нет, попарно разные означает, что все разные. Пару одинаковых чисел вряд ли можно назвать попарно разной :)
  18  Лавров Петр Аркадьевич, 04 мая 2008 г. 15:17:18
     Может поставить m где-нибудь 30, и сложность увеличить - чтобы стимул был писать хорошо отлаженный код перебора с отсечением... ато совсем лень! =)
     Замечу, что тут не любой алгоритм перебора пройдет по времени. А если увеличить до 30, то пожалуй, вообще любой оптимальный может не пройти.
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru