Дистанционная подготовка: Максимальное время работы превышено.
Максимальное время работы превышено.
от Никита Пушкин - Суббота 3 Май 2014, 18:49
915. Платная лестница
  Написал программу, но один тест не проходит, так как превышено максимальное время работы. Подскажите, как его уменьшить?
Re: Максимальное время работы превышено.
от Никита Пушкин - Суббота 3 Май 2014, 19:48
  Переделал задачу в соответствии с предлагаемым разбором, так теперь по времени не проходят уже 2 теста.
Re: Максимальное время работы превышено.
от Peter Cherepanov - Суббота 3 Май 2014, 20:58
  Ищите бесконечный цикл. Правильно написанная программа проходит за малые доли секунды.
Re: Максимальное время работы превышено.
от Никита Пушкин - Воскресенье 4 Май 2014, 00:30
  В каком смысле бесконечный цикл? Я просто сделал все так, как мне сказали в разборе, то есть тупо перебрать все варианты.
Re: Максимальное время работы превышено.
от Антон Карабанов - Воскресенье 4 Май 2014, 02:55
  Рекурсивное решение данной задачи возможно, но как показывает Ваш пример, требует много времени.

Чтобы вычислить rec[100] нужно вычислить rec[99] и rec[98].
Чтобы вычислить rec[99] нужно вычислить rec[98] (причем вычислить заново, пройдя всю цепочку до rec[2]) и rec[97].
Время впустую тратится на перевычисления уже ранее найденных значений.

А вот применив метод динамического программирования, мы спокойно будем обращаться к массиву и брать оттуда найденные на предыдущем шаге числа.

PS Это в тестах еще мало больших чисел, Ваша программа уходит в TimeLimit уже при n = 30.
Re: Максимальное время работы превышено.
от Никита Пушкин - Воскресенье 4 Май 2014, 16:28
  Хорошо, я понял, что нужно использовать метод динамического программирования. Но как это делать? Как в массив записывать вычисленные ранее значения? Что-то я немного не догоняю...
Re: Максимальное время работы превышено.
от Никита Пушкин - Воскресенье 4 Май 2014, 17:58
  Спасибо огромное за помощь, я наконец-то сдал задачу.