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

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

HotLog


 
[Вернуться к задаче]   1
  1  АЩщщ, 06 февраля 2020 г. 17:03:19
     Динамикой вверх решается за O(N) .
  2  МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 02 февраля 2020 г. 15:15:53
     recursive 0,062 AC
  3  Низамов Айнур Мулланурович, 14 января 2020 г. 22:47:03
     Прошу прощения, где я написал не n/3, надо i/3, i/2, i-1. Думаю разберетесь :)
  4  Низамов Айнур Мулланурович, 14 января 2020 г. 22:45:38
     С теми, кто пишет BFS - они неправы. Решение обыкновенной динамикой в одномерном массиве - куда проще. Предлагаю дать вам идею. Создаем массив dp[1000001] (такие ограничения) и приравниваем каждый элемент массива от 1 до n-1 бесконечному числу (например, 10е6 + 1 достаточно). Задаем базу: за сколько действий мы можем получить число n - за 0, ничего не делая. Значит в массиве dp будем хранить - сколько минимально действий надо сделать, чтобы получить i-ую. Пишем цикл от n до 1. Пусть сначала i=n, тогда если n%3==0, то разделив n на 3 мы можем получить n/3. Проверяем, dp[i/3] > dp[i] + 1, то обновляем dp[i/3]. Так же делаем и для n/2, n-1. Ответ будет лежать в dp[1] - если начинать заполнять массив с 1-го элемента. Решайте задачи тем методом, каким является его тема!
  5  Петерс Егор Александрович, 25 декабря 2019 г. 9:44:17
     BFS - поиск в ширину)
  6  МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 19 декабря 2019 г. 11:37:23
     BFS что ???
  7  Бобоев Н, 23 октября 2019 г. 21:50:01
     Не надо заморачиваться ) BFS и всё ACCEPTED !!!
 1

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

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