|
|
|
|
|
|
|
| 41 Kuzmin Alexey Andreevich, 16 марта 2009 г. 10:40:55 |
Я так и не понял, как эту задачу сделать перебором, реализовал ленивую динамику, работает за 0.029сек
Элементарно, перебрав всевозможные лесенки.
|
|
|
| 42 Чудов Алексей Евгеньевич, 19 сентября 2008 г. 9:17:02 |
Люди - это была издавна одна из классических задача на ДП! Очень простая динамическая схема.
Почему написано что это перебор?
Дело в том, что ограничения таковы, что рекурсивный перебор здесь весьма допустим. Конечно, эту тему можно смело отнести и к динамике, ведь это решение разумнее. А вообще полезно решить ее двояко.
|
|
|
| 43 Шевяков Макс, 20 мая 2008 г. 11:27:18 |
а я придумал свою динамическую схему! да и она проще. По-моему, если ее сильно оптимизировать до (NlogN), то пройдет и на более больших тестах, только додумать надо: надо вычислять количество лесенок для каждого числа до данного N, например мы пересчитали 14 чисел, считаем 15-ое: перебираем "основания": 15, 14-1 (+значение первого числа),13-2(+[2]),.... 8-7(+[7]), 7-6-2 вот тут над додумать, но думаю - (+[6+2]-[1]-1)... короч, схема интересная, но додумать надо...(((
Вообще, сложность алгоритма O(N*N), и без длинной арифметики можно для N=700 примерно расчитать. А вы для N=10^6 желаете решить?
|
|
|
| 44 Лавров Петр Аркадьевич, 12 апреля 2008 г. 22:23:25 |
Ну, чей компьютер успеет перебрать (для 100) быстрее секунды, а чей нет, это еще поспорить можно. Посмотрите: я сдал, но у меня для N=100 секунд 5 считал (несколько раз пробовал). =)
Речь шла о компьютере на котором тестируются задачи данного сайта. Я подозреваю, что и на Pentium I данная задача прошла бы за 1 сек. полным перебором. Даже возможно, что и на 386м компе прошла бы... Что стоит по времени чистый перебор 444793 вариантов? Издавна известно, что миллион простых действий проходит за секунду и стоит полагать, что современные школьники не застали еще тех компьютеров (ДВК-3, ЕС, Корвет, БК, УКНЦ), на которых подобное за секунду нереально выполнить.
|
|
|
| 45 Гольдшмидт Шлёва Лазаревич, 06 апреля 2008 г. 14:10:42 |
Если перебирать все возможные варианты, то не пройдёт по времени. Здесь нужно использовать динамическое программирование, однозначно!
Да нет вовсе, данные ограничения позволяют рекурсивно перебрать всевозможные лесенки. Для N=100 их меньше миллиона, т.е. при любом раскаде за 1 сек. успеваем перебрать. Есть аналогичная задача на тимусе, вот там дейтсвительно только динамикой, там N может быть 500.
|
|
|
| 46 Царицинский Сергей Владимирович, 29 декабря 2007 г. 16:45:45 |
Посоветуйте, что почитать по переборным алгоритмам вроде этого? С Новым годом!
Для вас полезным материалом может стать любой, касающийся динамического программирования или рекурсивного перебора. А для этой задачи может оказаться полезной такая ссылка: http://olympiads.ru/mioo_inform/2/handout4.shtml
|
|
|
| 47 Царицинский Сергей Владимирович, 26 декабря 2007 г. 13:57:50 |
Выложите, пожалуйста, несколько ответов с большими значениями N (например, 70,80,90,100). Вручную сложно пересчитать и проверить работу программы. На небольших значениях вроде работает, а что происходит при большом количестве вариантов непонятно.
при N=70, 80, 90 соответственно получим 29927, 77312, 189586.
|
|
|
| 48 Кундалев Денис Николаевич, 03 октября 2007 г. 23:06:12 |
Что за ерунда мое решение должно довать правильный ответ!!! По времени не должно проходить конечно, но чего неверный ответ на первом тесте?
А что за ерунда у вас получается при N=1? По вашему из 1-го кубика невозможно построить не одной лесенки? Именно такой первый тест, а не тот, что в примере. Так что как всегда оказалась прав компьютер, а не программист.
|
|
|
| 49 Бобер Александр Дмитриевич, 13 марта 2007 г. 6:05:23 |
Математическая интерпретация задачи: найти количество разбиений числа n на сумму различных слагаемых, 1+3 и 3+1 одно и то же разбиение.
Совершенно верно. Но такая формулировка задачи более скучна.
|
|
|
| 50 Гольцов Артем Витальевич, 09 марта 2007 г. 13:31:34 |
Как можно сделать из 6 кубиков 4 лесенки
Легко: 1) 6; 2) 1+5; 3) 2+4; 4) 1+2+3
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
