Тренер по программированию

Разберём простую задачу на динамическое программирование, автором которой являюсь я сам - сочинил эту задачу для одного из контестов, а потом она попала в архив задач. Читаем условие: Задача является сильным упрощением общего случая с разделением прямоугольника размера NxM, который надо решать с помощью динамического программирования по профилю. В этой же задаче можно поступить проще, рассмотрев все варианты. Для начала считаем размер шоколадки: Сразу можем обработать случай с нечётным N, так как...

Разберём простую прекрасную задачу, в которой есть математика и строгое доказательство. Читаем условие: Для начала надо убедиться, что возможно разложить любое число, большее 7, на сумму пятёрок и троек. Докажем это с помощью математической индукции. База индукции: N = 8 = 5 + 3. Выполняется. Шаг индукции: пусть для всех чисел от 8 от N выполнено, докажем, что и для N+1 имеется разложение. Если в разложении N имеется хотя бы одна пятёрка, то можно заменить её на две тройки, таким образом получим разложение для N+1...

Рассмотрим простую задачу на динамическое программирование, в которой построение ответа почти в два раза больше, чем само решение. Читаем условие: Задача не является продолжением или вариацией задачи 16. Лесенка, но решать будем тоже с помощью динамики. Считаем входные данные и сразу преобразуем их к числовым типам: Состоянием в динамическом программировании будет номер ступеньки, на которой стоит Вова. Чтобы узнать переходы, надо ответить на вопрос "Как Вова мог здесь оказаться?". Ответ очень простой - или с предыдущей ступеньки или через одну от неё...

Несложная классическая задача на структуры данных, которая усложнена форматом входных данных. Читаем условие: Итак, первая сложность в этой задаче - как считать данные? Действительно, нет классического N - количества строк. А это значит, что надо считывать все строки до конца. Построчное считывание в Python можно организовать через следующую конструкцию: Такой цикл считает весь входной файл и сам разделит его на строки. Единственная особенность - в строках l будут находиться и символы переноса строки, поэтому при их обходе надо делать l...

Несложная задача про написание обхода в ширину, на которой можно потренировать и применить несколько трюков. Читаем условие: В этой задаче нужно построить кратчайший путь, поэтому это явно поиск в ширину или BFS. Этот алгоритм подробно разбирали при решении Задачи 127. Путь. Если вы с ним не знакомы, то рекомендую сначала прочитать тот разбор. По условию задачи, поле очень маленькое (помним, что алгоритм BFS работает за линейное время от количества вершин и рёбер в графе, то есть O(V + E)). Поэтому,...

Задача, которая на Python решается практически в одну строчку. Но благодаря ей, познакомимся с ещё одной полезной функцией стандартной библиотеки. Читаем условие: Для начала надо определить, сколько может быть перестановок, чтобы понять, можем ли мы использовать Python или потребуется что-нибудь быстрее. Так как символы не повторяются, количество различных перестановок равно факториалу от N. То есть в самом худшем случае будет 8! = 40,320 перестановок. Вывод очередной перестановки (как и построение следующей из предыдущей) занимает O(N) времени...

Довольно простая задача на комбинаторику, позволяющая вспомнить формулы числа сочетаний и размещений. Читаем условие: Вспомним, что ладья может ходить только по горизонтали и по вертикали. Это значит, что на каждой строке (и в каждом столбце) может стоять не больше одной ладьи. Решать будем в два этапа. Сначала давайте зафиксируем строки, на которые поставим ладьи. Количество различных способов это сделать равно числу сочетаний из n по k (C(n, k)). Как говорит Википедия: В комбинаторике сочетанием...

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

Обобщение классической школьной задачи по математике про три котлеты и одну сковородку. Попробуем решить её одной простой формулой. Но сначала читаем условие: Заметим, что домножать на m можно в самом конце, поэтому дальше будем считать, что m = 1. Для начала вспомним исходную задачу: Вам необходимо за 3 минуты пожарить 3 котлеты. Каждая котлета с одной стороны жарится ровно минуту. Но сковородка у нас маленькая, на ней помещаются одновременно всего лишь 2 котлеты. Как в таком случае выйти из положения?...

Немного упрощённый вариант Задачи 155. Конденсаторы, поэтому и решать будет простой рекурсивной функцией без всяких премудростей. Читаем условие: Чисел всего 4, деления нет, поэтому можно написать функцию, которая будет возвращать список со всеми числами, которые можно получить с помощью заданных арифметических операций. Так как функция будет рекурсивной, то назовём её rec. Тогда основное решение будет очень простым: Функция rec будет разделять входящий список чисел на две части во всех возможных местах и рекурсивно вызываться для каждой из них...

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

Очень классная задача на динамическое программирование, в которой надо ещё придумать, как быстро посчитать результат. Читаем условие: Идея динамического программирования лежит на поверхности - чтобы вычислить стоимость для N надо знать стоимость для S и N - S (и правильно распределить, к чему прибавить 1, а к чему - 2). Получаем одномерную динамику - ответ зависит лишь от количества элементов в множестве. База динамики: для 1 ответ 0. Если загаданное число среди одного, то не надо задавать вопросов, чтобы узнать, что это за число...