Задача E. Нарезка фантиков ≡

Условие

Для производства конфетных фантиков изготовлена длинная узкая лента с напечатанными на ней картинками. Длина каждой картинки — L мм, расстояние между двумя соседними картинками — d мм, расстояние от начала ленты до первой картинки — a мм.

Нужно получить N фантиков длиной W мм каждый. Аппарат по производству фантиков работает так: сперва от начала ленты отрезается и выбрасывается кусок длиной x мм. Затем от начала ленты один за другим отрезаются фантики длиной W мм каждый.

Каким должно быть x, чтобы на каждом фантике была целиком расположена ровно одна картинка? Картинки, попадающие на фантик только частично, не считаются.

Формат входного файла

Входной файл содержит целые числа L d a N W.

Формат выходного файла

Выходной файл должен содержать целое число x.

Число x должно удовлетворять неравенству 0 ≤ x < L + d.

Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N, L, W, d ≤ 1000.

0 ≤ a < L + d.

Гарантируется, что существует хотя бы одно решение.

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

3 1 2 3 7

1

Разбор

Рассмотрим i-й фантик в отдельности. Смещением ленты относительно i-го фантика назовём величину наименьшего расстояния от начала i-го фантика до картинки, целиком лежащей правее его начала.

Смещение ленты относительно i-го фантика характеризует изображение на i-м фантике, то есть то, что на нём нарисовано.

В дальнейшем смещение ленты относительно i-го фантика будем обозначать p_i.

Зададимся вопросом: при каких значениях смещения на фантике целиком расположена ровно одна картинка?

Рассмотрим самую левую из картинок, начало которых находится правее, чем начало данного фантика. По определению смещения ленты относительно i-го фантика расстояние от начала фантика до этой картинки равно p_i. Эта картинка будет целиком расположена на i-м фантике, если и только если p_i + L ≤ W. А следующая картинка уже не будет целиком располагаться на i-м фантике в том и только том случае, если p_i + 2L + d > W.

Итак, мы получили необходимое и достаточное условие того, что на i-м фантике целиком расположена ровно одна картинка. Это имеет место тогда и только тогда, когда
W − 2L − d < p_i ≤ W − L. (*)

Сформулируем теперь нашу задачу.

Задача. Подобрать такое x, чтобы неравенство (*) выполнялось для всех i = 1, 2, 3, ..., N.

Замечание. В неравенстве (*) смещение p_i ленты относительно i-го фантика зависит от x (p_i — функция от x).

Для решения поставленной задачи вычислим значение p_i. Из рисунка видно, что (это утверждение приводится здесь без доказательства)
p₁ = (a − x)mod(L + d).

Далее,
p₂ = (a − x − W)mod(L + d) и т. д.
p_i = (a − x − (i − 1)W)mod(L + d). (**)

Подставляя (**) в (*), получим
W − 2L − d < (a − x − (i − 1)W)mod(L + d) ≤ W − L. (***)

Таким образом, для того чтобы при некотором наперёд заданном x на каждом фантике была целиком расположена ровно одна картинка, необходимо и достаточно, чтобы неравенство (***) выполнялось при любом i = 1, 2, 3, ..., N.

Отсюда получаем алгоритм. Для каждого x: 0 ≤ x < L + d проверить выполнение неравенства (***) для любого i от 1 до N. Если неравенство выполнено для любого такого i, то x является ответом.

Запишем алгоритм в псевдокоде.

Alg:
for x = 0, ..., L + d − 1
    flag = 1;
    for i = 1, ..., N
        if not (W − 2L − d < (a − x − (i − 1)W)mod(L + d) ≤ W − L)
            flag = 0;
            выйти из цикла по i;
    if (flag = 1)
        вывести x;
        выйти из цикла по x;

Скачать другой разбор