Этим летом решил позаниматься изучением алгоритмов. Язык программирования — C++. Недавно я узнал, что у компании «Яндекс» есть бесплатный веб-сервис «CodeRun» (работает с 2024 года), на котором можно порешать задачи. (В принципе, это не единственный подобный веб-сервис в интернете, но я захотел начать с этого.)

Тексты задач доступны в каталоге этого веб-сервиса по адресу https://coderun.yandex.ru/catalog. Всего там на данный момент 751 задача. Эти задачи имеют разную сложность: легкая (201 задача), средняя (267), сложная (190) и неопределенная сложность (93). Я решил сначала прорешать 10 легких задач, чтобы понять, какой уровень мне будет удобен.

Для чтения текстов задач регистрация не требуется. Но на веб-сервисе есть возможность отправить решение на автоматическую проверку с получением автоматического ответа. А для этого уже регистрация нужна. Кроме этого для зарегистрированных пользователей ведется статистика. Поэтому я решил, что регистрация мне необходима. Для входа на веб-сервис нужен «Яндекс ID» (единый аккаунт для всех сервисов компании «Яндекс»), он у меня заведен уже давно.

Насколько я понял, решать задачи на этом веб-сервисе можно на любом из 14 языков программирования: C++, C#, Java, JavaScript, Паскаль, Python и так далее (при отправке решения на проверку есть соответствующий переключатель для указания языка программирования). Я пробовал только на C++.

Сложность задач рассчитывается (тут подробнее) динамически, то есть может меняться со временем. Сложность задач зависит от того, как пользователи решают задачи. Кроме этого, все задачи распределяются в группы по трем указанным сложностям в следующем соотношении: 30 % легких, 40 % средних, 30 % сложных.

Таким образом, не следует надеяться, что задачи, состоящие в группе легких, действительно окажутся для вас легкими. Как видно из сказанного выше, «легкость» — это понятие относительное.

В этом посте я решил описать моё решение одной из задач с этого веб-сервиса. Она называется «Вывести маршрут максимальной стоимости» и на данный момент включена в группу легких.

Формулировка задачи

Я постарался сформулировать покороче, чтобы можно было охватить одним взглядом. Получилось следующее:

В левом верхнем углу прямоугольной таблицы размером N × M (размеры являются натуральными числами, не превосходящими 100) находится черепашка. В ячейках таблицы записаны целые числа. Черепашка перемещается только вправо или вниз, заканчивая свой маршрут в правом нижнем углу таблицы. Требуется подсчитать и вывести сумму чисел, через которые проползет черепашка, включая первую и последнюю ячейку маршрута; сумма должна быть максимально возможной в данной таблице. Также требуется вывести пошаговый маршрут черепашки с помощью символов D (вниз) и R (вправо), разделенных пробелом.

Пример ввода и вывода данных при работе программы:

5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9
74
D D R R R R D D

Последние две строки в этом примере — это вывод результата работы программы (максимально возможная в этой таблице сумма чисел на пути черепашки и пошаговый путь черепашки, дающий эту сумму).

Первая строка в этом примере — это размеры таблицы. В данном случае имеется в виду таблица из пяти рядов и пяти столбцов. После ввода размеров таблицы вводятся числа в ячейках таблицы. Красным цветом я пометил найденный программой путь в данной таблице.

Готовые решения в разделе «Разборы»

Прежде всего следует упомянуть, что на рассматриваемом веб-сервисе вы можете решить задачу и опубликовать своё решение и разбор этого решения прямо на этом же веб-сервисе. То есть вместо поиска решения любой человек (требуется регистрация на веб-сервисе) может зайти в раздел «Разборы», доступный на странице описания задачи, взять там готовое решение и выдать его за своё. Например, для рассматриваемой задачи на данный момент доступно 50 разборов.

Лично я считаю сам поиск решения и детальный его разбор самой главной частью обучения и самообучения. Поэтому я пока еще ни разу не заглядывал ни в один из подобных разборов для этой задачи или для других. Это для меня что-то вроде спойлера в любимом сериале, не хочу портить себе кайф от поиска решения.

Инструменты для поиска решения

Для поиска решения любой задачи я использую поисковые системы «Яндекс» и «Google». В последнее время очень полезны в поиске стали ответы встроенных в эти поисковые системы нейросетей.

В «Яндексе» это «Алиса AI», в Google это «AI Mode». Эти нейросети довольно хороши, очень помогают, но довольно часто выдают устаревшую информацию, ответы с ошибками и тому подобное. Их ответы приходится проверять. С одной стороны это недостаток, с другой стороны учит критично относиться к любым утверждениям, независимо от их источника.

На веб-сервисе «CodeRun» есть встроенная нейросеть «Кодерун AI», помеченная меткой «β» или меткой «new». Там написано, что эта нейросеть работает на технологиях веб-сервиса «SourceCraft» (сервис для разработки, тестирования и сборки проектов от «Яндекса», запущен в 2025 году). Я этой нейросетью пока не пользовался, не было необходимости. Для ее использования требуется регистрация на веб-сервисе «CodeRun», а кроме того там сказано, что вы ограничены 20 запросами.

Узнаю привычно дуболомный маркетинг от «Яндекса». На фоне бесплатных нейросетей, встроенных в поисковые системы, это выглядит глупо.

Поиск решения

Математик сразу увидит в подобной задаче граф. А теория графов — это довольно проработанный раздел математики, в котором придумано множество алгоритмов для решения различных задач.

Также небольшой подсказкой можно считать то, что рассматриваемая задача помечена ее авторами меткой «dynamic programming 2D». Приписка «2D», вероятно, сделана потому, что речь идет о решении задачи с использованием двумерной структуры данных.

Термин «динамическое программирование» я услышал впервые только несколько лет назад. И он меня слегка раздражает, так как всё, что под ним подразумевают, я использовал десятки лет, меня этому обучали, но никогда мне никто не говорил, что это называется «динамическим программированием». В моей картине мира это новый термин для того, что и так уже давно существует и не требует никаких новых названий для себя.

Решение

Возможно, у этой задачи есть несколько решений. Я своё придумал не сам, а, как обычно, написал по подсказкам умных людей из интернета. Код, как обычно, писал сам.

Предлагается сначала создать вспомогательную таблицу такого же размера, как исходная. В каждой ячейке вспомогательной таблицы хранится не исходное число, а уже рассчитанная сумма чисел на маршруте максимальной стоимости именно до этой ячейки.

Эту вспомогательную таблицу будем заполнять по мере ввода пользователем чисел исходной таблицы. Это возможно, так как расчет для каждой ячейки строится на расчетах для предыдущих ячеек. Весь процесс с расчетами для разных ячеек начинается с левого верхнего угла таблицы и последовательно продолжается для ячеек ряд за рядом, точно в том порядке, в котором пользователь программы вводит исходные данные. Именно подобные расчеты и называют «динамическим программированием» (окончательный результат строится на результатах предыдущих шагов, те результаты строятся на результатах еще более ранних шагов и так далее).

При этом для дальнейшей работы программы после создания описанной выше вспомогательной таблицы исходная таблица больше не понадобится. Поэтому даже нет смысла изначально выделять под нее память и что-то в ней сохранять при заданных условиях задачи.

Давайте посмотрим, как это будет происходить для данных, показанных в примере ввода и вывода данных выше. Пользователь программы вводит числа первого ряда таблицы. В каждую ячейку этого ряда черепашка может попасть, лишь двигаясь вправо. Вот первый ряд вспомогательной таблицы, который мы получим, исходя из этих соображений:

9 18 27 36 45

Далее пользователь программы начинает вводить числа второго ряда исходной таблицы. Для ячейки, которая лежит под начальной, ясно, что в нее можно попасть только, если черепашка поползет вниз (то же самое можно сказать про все ячейки первого слева столбца таблицы). Получаем следующее:

9  18 27 36 45
12

В любую другую ячейку второго ряда таблицы, кроме первой ячейки, можно прийти двумя путями (это можно сказать и про все остальные ячейки таблицы, не состоящие в верхнем ряду таблицы и не состоящие в первом слева столбце таблицы): слева или сверху. Мы можем посчитать стоимость каждого из этих двух путей, сравнить эти два пути, и сохранить в ячейке стоимость максимального из них. Это получится, если заполнять ячейки последовательно слева направо. Получаем следующее:

9  18 27 36 45
12 18 27 36 45

Объединив вышеизложенные рассуждения и продолжив последовательно, ряд за рядом, заполнять вспомогательную таблицу, получим:

9  18 27 36 45
12 18 27 36 45
21 30 39 48 57
27 36 45 54 65
36 45 54 63 74

Сумма чисел на маршруте максимальной стоимости для этих данных во вспомогательной таблице, очевидно, находится в целевой ячейке (ячейка в правом нижнем углу таблицы). Для этих данных это число 74. То есть мы уже имеем один из двух требуемых результатов для вывода.

Не сразу понятно, но получить этот результат мы можем, пройдя все ячейки таблицы, без исключений. Где-то сэкономить (пропустить одну или несколько ячеек) не получится.

Кроме того, мы не можем сразу, при построении этой вспомогательной таблицы, как-то записывать и пошаговый маршрут максимальной стоимости. Этот маршрут я восстанавливаю в обратном порядке, начиная с последней ячейки маршрута (правая нижняя ячейка вспомогательной таблицы).

При этом использую уже знакомые рассуждения. Например, в конечную ячейку можно попасть только сверху или слева (как и в большинство других ячеек этой таблицы, кроме ячеек самого верхнего ряда и первого столбца слева). Но теперь, опираясь на числа в ячейках вспомогательной таблицы, мы можем точно понять, что маршрут максимальной стоимости пришел в конечную ячейку сверху.

Конечно, тут возможен случай, когда в какую-то ячейку можно прийти двумя маршрутами (слева и сверху) одинаковой стоимости. В этом случае по условиям задачи разрешается использовать любой из этих маршрутов (результат-то одинаковый).

Пошаговый маршрут максимальной стоимости я записываю в вектор. Элементы полученного вектора вывожу в качестве результата в обратном порядке (мы восстанавливаем нужный пошаговый маршрут от конца к началу, поэтому при выводе требуется инвертировать, но я не хочу тратить время на изменение самого вектора, поэтому просто вывожу элементы вектора в обратном порядке).

Код программы на языке C++

#include <iostream>
#include <vector> // для std::vector

int main()
{
    // получить размеры таблицы,
    // по условиям задачи каждый размер — в диапазоне (0..100]
    int N{};
    int M{};
    std::cin >> N;
    std::cin >> M;

    // таблицу исходных чисел хранить не буду,
    // составить таблицу длин путей максимальной стоимости до каждой ячейки
    std::vector<std::vector<int>> paths(N, std::vector<int>(M, 0));
    for (int r{}; r < N; r++)
    {
        for (int c{}; c < M; c++)
        {
            // получить очередное число в ячейке исходной таблицы
            int number{};
            std::cin >> number;

            // использовать исходное число для вычисления пути к ячейке
            if (r == 0 && c == 0) // левый верхний угол
            {
                paths[r][c] = number;
            }
            else if (r == 0)      // верхняя строка
            {
                paths[r][c] = paths[r][c - 1] + number;
            }
            else if (c == 0)      // левая колонка
            {
                paths[r][c] = paths[r - 1][c] + number;
            }
            else                  // все остальные случаи
            {
                int fromAbove{ paths[r - 1][c] + number };
                int fromLeft{ paths[r][c - 1] + number };
                if (fromAbove > fromLeft)
                {
                    paths[r][c] = fromAbove;
                }
                else
                {
                    paths[r][c] = fromLeft;
                }
            }
        }
    }

    // вывести самую большую сумму чисел на пути черепашки
    std::cout << paths[N - 1][M - 1] << '\n';

    // восстановить путь черепашки
    std::vector<char> path;
    for (int r{ N - 1 }, c{ M - 1 }; r > 0 || c > 0;)
    {
        if (r == 0)      // верхняя строка
        {
            path.push_back('R');
            c--;
        }
        else if (c == 0) // левая колонка
        {
            path.push_back('D');
            r--;
        }
        else             // все остальные случаи
        {
            int above{ paths[r - 1][c] };
            int left{ paths[r][c - 1] };
            if (above > left)
            {
                path.push_back('D');
                r--;
            }
            else
            {
                path.push_back('R');
                c--;
            }
        }
    }

    // вывести путь черепашки
    int steps{ N - 1 + M - 1 };
    for (int step{ steps - 1 }; step >= 0; step--)
    {
        std::cout << path[step] << ((step != 0) ? ' ': '\n');
    }

    return 0;
}

Выводы

На первый взгляд веб-сервис «CodeRun» мне понравился. Могу его рекомендовать. Если будет, что еще про него написать, то напишу об этом в каком-нибудь из следующих постов.

Насчет легкости рассмотренной задачи. В плане синтаксиса и приемов программирования на языке C++ соглашусь, что задача относительно легкая. В плане алгоритма решения я бы отнес эту задачу к задачам между легкой сложностью и средней сложностью. Думаю, авторам веб-сервиса «CodeRun» стоит добавить еще один вид сложности задач между легким и средним. Например: легкие, легко-средние, средние, сложные.