0403. Трубы

Валентин и Святослав на уроке физики собрали странную конструкцию из труб. Конструкция представляет собой квадратную в сечении горизонтальную трубу длиной D дециметров с припаянными к ней трубами, ведущими вертикально вверх. Сечение всех труб составляет 1 квадратный дециметр. Таким образом каждый дециметр трубы по длине вмещает в себя ровно один литр воды.

Одна из вертикальных труб намного длиннее остальных. Валентин назвал её главной трубой. Высота всех остальных вертикальных труб известна и составляет целое количество дециметров. Вся конструкция представляет собой набор сообщающихся сосудов: если заливать воду в главную вертикальную трубу, то уровень воды будет подниматься во всех вертикальных ответвлениях одновременно. На верхней части каждого из вертикальных ответвлений установлен воздухоотводчик, который позволяет выходить из трубы воздуху, но не пропускает воду, когда труба заполнится. После того как какая-либо вертикальная труба заполняется доверху, вода продолжает подниматься одновременно во всех остальных трубах.

Валентин начинает заливать через главную вертикальную трубу воду со скоростью W литров в минуту, а Святослав хочет заранее рассчитать, через сколько минут уровень воды в главной вертикальной трубе достигнет или преодолеет отметку в L дециметров. Ребята обозначили за A_i высоту каждой из вертикальных труб системы (высота даётся в дециметрах, причем считается от низа горизонтальной трубы). Высота главной вертикальной трубы заведомо больше высоты требуемой отметки. Это означает, что вода всегда достигнет уровня отметки прежде, чем начнет переливаться через край главной вертикальной трубы.

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

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

В первой строке ввода указаны четыре целых числа: N – количество вертикальных сегментов, не считая главного (0 ≤ N < D), D – длина горизонтального сегмента (1 ≤ D ≤ 1000), W – скорость подачи воды в систему (1 ≤ W ≤ 1000), L – конечная отметка по высоте (1 ≤ L < 1000).

В следующей строке содержится N чисел A_i – высота каждой из вертикальных труб (1 ≤ A_i ≤ 1000).

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

Выведите одно целое число – минимальное целое количество минут, по прошествии которых вода в главной вертикальной трубе достигнет или превысит заданную отметку.

Пример:

На рисунках изображено пояснение к первому примеру.

1) Начальное состояние системы.

2) Уровень воды через 5 минут.

3) Уровень воды через 8 минут.

4) Уровень воды через 9 минут. Вода превысила отметку в 5 дециметров по вертикали.

Источник: Муниципальный этап всероссийской олимпиады школьников по информатике, 12 декабря 2014 года.

Обсудить       Отправить решение



Версия для печати