Задача 6. Интервальные тренировки

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

План тренировки представляет собой набор целых положительных чисел a1, a2, …, am, где ai описывает нагрузку спортсмена в i-й день. Любые два соседних дня должны иметь различную нагрузку: ai ≠ ai + 1. Чтобы рост нагрузки и её снижение чередовались, для i от 1 до m − 2 должно выполняться следующее условие: если ai < ai + 1, то ai + 1 > ai + 2, если же ai > ai + 1, то ai + 1 < ai + 2.

Суммарная нагрузка в процессе выполнения плана должна составлять n, то есть a1 + a2 + …  + am = n. Ограничения на количество дней в плане нет, m может быть любым, но нагрузка в первый день тренировок зафиксирована: a1 = k.

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

Требуется написать программу, которая по заданным n и k определяет, сколько различных планов тренировок удовлетворяют описанным ограничениям, и выводит остаток от деления количества таких планов на число 109 + 7.

Формат входных данных

В первой строке входных данных находятся целые числа n, k.

Формат выходных данных

Выведите одно число: остаток от деления количества планов тренировок на 109 + 7.

Ограничения

1 ≤ n ≤ 5000, 1 ≤ k ≤ n

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1231 ≤ n ≤ 10полная
2201 ≤ n ≤ 301первая ошибка
3231 ≤ n ≤ 5001, 2первая ошибка
4341 ≤ n ≤ 50001, 2, 3только баллы

Пояснения к примерам

В первом примере подходят следующие планы: [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [2, 4].

Во втором примере единственный подходящий план [3].

Примеры тестов

Стандартный вход Стандартный выход
1
6 2
4
2
3 3
1

Разбор

Для решения подзадачи 1 можно применить рекурсивный перебор вариантов.

Тот же метод решает и подзадачу 2 при использовании аккуратного перебора с отсечениями. Если для n порядка 30 перебор не успевает найти ответ за отведенное ограничение по времени, можно применить метод предподсчёта: заранее на своём компьютере найти ответы для всех тестов с 1 ≤ k ≤ n ≤ 30 и отправить на проверку программу, которая выводит найденный заранее ответ.

Для решения подзадач 3 и 4 необходимо применить динамическое программирование. Рассмотрим сначала решение за O(n3), которое решает подзадачу 3.

Обозначим как up[n][k] количество планов тренировок, которые удовлетворяют описанным ограничениям, суммарная нагрузка которых равна n, нагрузка в первый день k, а нагрузка во второй день строго больше нагрузки в первый день. Аналогично введём величину down[n][k], для количества таких планов, где нагрузка во второй день строго меньше нагрузки в первый день.

Заметим, что up[n][n] = down[n][n] = 1. Для k < n значения можно вычислить по формулам:

up[n][k] = n − ki = k + 1down[n − k][i],

down[n][k] = k − 1i = 1up[n − k][i].

Величина, которую требуется найти по условию задачи, равна up[n][k] + down[n][k], не забудем также отдельный случай n = k, когда ответ равен 1.

Чтобы получить решение для подзадачи 4, для которой решение за O(n3) слишком медленное, можно использовать два подхода.

Подход 1: другая формула пересчёта. Заметим, что формула для up[n][k] отличается от up[n][k + 1] одним слагаемым: down[n − k][k + 1], поэтому up[n][k] = up[n][k + 1] + down[n − k][k + 1]. Аналогично, down[n][k] = down[n][k − 1] + up[n][k − 1]. Теперь значения вычисляются за O(1) и время подсчёта всех значений есть O(n2). Следует обратить внимание, что значения up[n][k] следует вычислять по убыванию k, а значения down[n][k] по возрастанию k.

Подход 2: префиксные суммы. Введем дополнительные величины:

sumUp[n][k] = ki = 1up[n][i],

sumDown[n][k] = ki = 1down[n][i].

Тогда up[n][k] = sumDown[n − k][n − k] − sumDown[n − k][k], down[n][k] = sumUp[n][k − 1].

Отметим, что во всех случаях следует аккуратно следить за тем, чтобы индексы значений, к которым происходит обращение в формулах, не выходили за пределы массивов и за порядком вычислений.


0.146s 0.018s 13