Спецкурс по программированию, 2016 г.


Общая информация

На спецкурсе мы будем разбирать задачи из турниров по программированию, возможно также поговорим об актуальных математических проблемах, проистекающих из программирования. Спецкурс проходит по субботам в 12:35, аудитория (ориентировочно) 417. Начало 1 октября. Информацию можно уточнить по почте mail@dcherukhin.info. Разбор задач мы начали с турнира Russian Code Cup (RCC). Слушателям предлагается самостоятельно решать задачи (в том числе разобранные в классе) и загружать их решения по ссылке ниже, при этом программа будет проверяться на оригинальных тестах из турнира. Программы можно загружать в любом порядке.

Таблица задач, решённых слушателями


Задачи

Тема: динамическое программирование

Задача 1. Солдаты армии выстроились в шеренгу. Генерал хочет так разбить эту шеренгу на подразделения из рядом стоящих солдат, чтобы в каждом подразделении солдаты были выстроены по возрастанию или по убыванию роста и мощь армии была максимальна. Мощь армии определяется как произведение мощностей подразделений, мощность подразделения - число солдат в нём. (RCC-2012, квалификация 1, условие, решение).

Задача 2. Возраст жителей некоторой планеты определяется не одним числом, а вектором размерности k. При рождении все координаты вектора равны 0. Каждый год каждая координата вектора увеличивается на ненулевое целое число. Вектора за всю жизнь образуют историю жизни. Нужно найти число всех возможных историй жизни, у которых сумма координат последнего вектора равна n. (RCC-2012, финал, условие, решение)

Задача 3. Есть n двухядерных процессоров и 2n программ, состоящих из инструкций A-Z. Нужно распределить эти программы на ядра так, чтобы общее время их выполнения было минимально. Ядра работают параллельно, но два ядра одного процессора могут одновременно выполнять только одинаковые инструкции. (RCC-2012, финал, условие, решение)

Задача 4. Игра состоит из n клеток, выстроенных в ряд, на которые каждую секунду падают монеты в количестве a1, ..., an соответственно. Игрок каждую секунду может либо оставаться на месте, либо перемещаться в соседнюю клетку, забирая все монеты там, куда он переходит. Игра длится k секунд, в начале игрок находится в клетке t. Найти максимально возможный выигрыш игрока. (RCC-2015, финал, условие, решение)

Задача 5. Есть прямоугольное поле n x m клеток, некоторые из которых являются препятствиями. Нужно найти число неэквивалентных путей, ведущих из правого верхнего в левый нижний угол поля и обходящих препятствия. Из каждой точки путь может идти в клетку налево или вниз. Пути эквивалентны, если каждое препятствие они обходят с одной и той же стороны. (RCC-2016, финал, условие)

Тема: разное

Задача 6. Есть прямоугольный зрительный зал на n x m мест и два входа в него. У первого входа скопилось k зрителей, у второго nm - k. Для каждого зрителя известно максимальное число шагов, которые он может пройти до своего места. До места с координатами (i, j) от первого входа нужно пройти i + j шагов, от второго i + m + 1 - j шагов. Можно ли распределить билеты между зрителями так, чтобы каждый дошёл до своего места? (RCC-2016, финал, условие, решение)

Задачи московского четвертьфинала студенческого чемпионата ACM 2016 г.: условия, решения.

Тема: теория графов

Задача 7. Найти в графе кратчайшее расстояние между вершинами. На входе: число вершин, число рёбер, сами рёбра, заданные парами вершин (вершины нумеруются с 0), далее номера вершин, между которыми найти расстояние. На выходе искомое расстояние.


Страница обновлена: T12.650