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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Для производства конфетных фантиков изготовлена длинная узкая лента с напечатанными на ней картинками. Длина каждой картинки — 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.

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1 2 3 7
1

Разбор

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

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

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

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

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

Итак, мы получили необходимое и достаточное условие того, что на i-м фантике целиком расположена ровно одна картинка. Это имеет место тогда и только тогда, когда

W2 Ld < pi ≤ WL. (*)

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

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

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

Для решения поставленной задачи вычислим значение pi. Из рисунка видно, что (это утверждение приводится здесь без доказательства)

p1 = (ax)mod(L+d).

Далее,

p2 = (axW)mod(L+d) и т. д.

pi = (ax−(i1)W)mod(L+d). (**)

Подставляя (**) в (*), получим

W2 Ld < (ax−(i1)W)mod(L+d) ≤ WL. (***)

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

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

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

Alg:

for x = 0, ..., L+d1

    flag = 1;

    for i = 1, ..., N

        if not (W2 Ld < (ax−(i1)W)mod(L+d) ≤ WL)

            flag = 0;

            выйти из цикла по i;

    if (flag = 1)

        вывести x;

        выйти из цикла по x;

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


0.192s 0.012s 17