| 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 !!!
|
|
|
