Форум » Динамическое программирование » №2561 (возможная ошибка) » Ответить
№2561 (возможная ошибка)
beep: Здравствуйте! По условию можно передвигаться в любую сторону по горизонтали или вертикали. Единственное ограничение - на каждом следующем шаге число должно быть больше предыдущего. В условии не оговорено можно ли перемещаться больше, чем на одну клетку, причем в следующей задаче №2560 это оговорено, что наводит на мысль, что можно перескакивать в любую клетку строки или столбца данной позиции. Начальная позиция тоже не задана. В ответе дан результат 446, у меня получился результат 1373. Вот мой маршрут (массив кортежей с координатами (x, y), где отсчет идет с 0 для строк и столбцов): [(1, 12), (1, 9), (11, 9), (4, 9), (2, 9), (2, 3), (2, 1), (1, 1), (5, 1), (5, 7), (2, 7), (2, 12), (2, 13), (8, 13), (8, 3), (3, 3), (7, 3), (7, 2), (7, 14), (1, 14), (0, 14), (0, 6), (0, 11), (0, 1)] Или в числах: 4 + 7 + 9 + 18 + 21 + 24 + 25 + 32 + 36 + 44 + 52 + 58 + 72 + 73 + 78 + 81 + 82 + 83 + 88 + 93 + 96 + 98 + 99 + 100 Для наглядности залил скрин - https://i.imgur.com/akQa017.jpg Либо я не понял из условий какие-то дополнительные ограничения на передвижение, либо у меня получилось найти путь с большей суммой. Писал на почту, указанную на сайте, а также через форму сайта, ответа не последовало.
Ответов - 9
cabanov.alexey: Либо я не понял из условий какие-то дополнительные ограничения на передвижение Ровно на одну клетку по горизонтали и вертикали. Всё, конечно, куда проще чем вам показалось.
beep: cabanov.alexey пишет: Ровно на одну клетку по горизонтали и вертикали. С таким ограничением ответ сходится, но из условия: Перемещаться между числами можно по горизонтали и вертикали (в любом направлении). Рассматриваются последовательности чисел, такие что каждое следующее число больше предыдущего. Такое ограничение не следует. Стоит поправить условие задачи. cabanov.alexey пишет: Всё, конечно, куда проще чем вам показалось. Да, намного проще. Без ограничения в одну клетку задача куда интереснее. Спасибо! UPD: только сейчас заметил, что Вы - автор задачи. Спасибо за задачу, когда ее увидел и решал без ограничений в одну клетку, немного оживился посреди однотипных задач.
cabanov.alexey: Хорошо, давайте дополним условие №2561 так (А. Кабанов) Дана таблица вещественных чисел размера NxN (1 < N ≤ 20). Перемещаться между числами можно на одну клетку по горизонтали и вертикали (в любом направлении). Рассматриваются последовательности чисел, такие что каждое следующее число больше предыдущего. Найдите последовательность с наибольшей суммой. В качестве ответа запишите наибольшую сумму.
beep: cabanov.alexey пишет: Хорошо, давайте дополним условие №2561 так Я только за, так же сформулировано в №2560. Главное, чтобы на сайте Константин внес эти изменения. Если у Вас есть возможность с ним связаться, было бы здорово. Мне он так и не ответил, к сожалению.
Поляков: Спасибо, я поправил на сайте и в файле.
beep: Поляков, Вам спасибо за Ваши труды. А Вы не планируете выпускать материалы по олимпиадному программированию?
Поляков: beep пишет: А Вы не планируете выпускать материалы по олимпиадному программированию? Нет, это совсем не моя сфера деятельности. Есть прекрасные авторы - Е.В. Андреева, С.М. Окулов, М. Густокашин.
beep: Поляков, а не могли бы посоветовать конкретные книги на уровне введения, где будет объясняться, как рассчитать ограничения по памяти и тп? Посмотрел этих трех авторов, у них нет толком книг на данную тему. Либо какие-то небольшие лекции по 100 страниц, либо просто про основы программирования книги.
Поляков: beep пишет: как рассчитать ограничения по памяти и тп К сожалению, так сразу не могу назвать книг специально по этой теме.
полная версия страницы