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

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

HotLog


 
[Вернуться к задаче]   1
  1  Яшкин Тимур Сергеевич, 21 июля 2022 г. 8:31:14
     Сведите задачу к следующей: Надо минимальным кол-вом операций превратить число 1 в n: +1, *2, *3
  2  Максат Гуванчмырадов, 08 февраля 2022 г. 20:38:41
     С BFS все просто и ACCEPTED!
  3  Цупа Роман Павлович, 09 января 2022 г. 22:27:07
     Чистая динамика с первого трая)10000 - 14; 999 - 8; 5678 - 14; 1 - 0; 2 - 1; 3 - 1; 4 -2; 5 - 3; 6 - 2; 7 - 3; 8 - 3; 9 - 2;10 - 3; 11 - 4; 12 - 3; 13 - 4; 14 - 4; 15 -4;
  4  Гришков Васлий Александрович, 01 ноября 2021 г. 9:14:28
     кривые ограничения
  5  Зеленский Данил Олегович, 03 августа 2021 г. 17:43:54
     Пришлось помучить себя, рекурсией динамика стек переполняет, не люблю реализовывать итеративную=(
  6  Кузьмицкий Максим Сергеевич, 03 апреля 2021 г. 16:34:26
     Низамов Айнур Мулланурович, dp[1000001] зачем? я создавал dp[n]
  7  Неизвестный, 22 января 2021 г. 21:37:05
     а можно примеры тестов пожалуйста
  8  Измайлович Денис, 23 ноября 2020 г. 22:12:25
     А, уже на 3 тесте число на входе больше 100000 XD. Нечасто такое увидишь.
  9  Измайлович Денис, 23 ноября 2020 г. 19:52:59
     Добрый вечер, Админ. Еще никогда настолько чистые и прозрачные решения у меня не выдавали ошибок. ДП, O(n), RE-3 тест, однако у меня проходят абсолютно все тесты. В чем проблема, подскажите пожалуйста?
  10  Касымбеков Абдусаттар Манасбекулы, 13 октября 2020 г. 21:19:37
     прикольная задача, хотя я думал она будет сложнее.
  11  АЩщщ, 06 февраля 2020 г. 17:03:19
     Динамикой вверх решается за O(N) .
  12  МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 02 февраля 2020 г. 15:15:53
     recursive 0,062 AC
  13  Низамов Айнур Мулланурович, 14 января 2020 г. 22:47:03
     Прошу прощения, где я написал не n/3, надо i/3, i/2, i-1. Думаю разберетесь :)
  14  Низамов Айнур Мулланурович, 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-го элемента. Решайте задачи тем методом, каким является его тема!
  15  Петерс Егор Александрович, 25 декабря 2019 г. 9:44:17
     BFS - поиск в ширину)
  16  МИРЖАХОН КАЙИМОВ МИРТЕМИРОВИЧ, 19 декабря 2019 г. 11:37:23
     BFS что ???
  17  Бобоев Н, 23 октября 2019 г. 21:50:01
     Не надо заморачиваться ) BFS и всё ACCEPTED !!!
 1

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

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