ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Лучше поздно, чем никогда

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Полина и коммиты

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Полина работает в компании «Тындекс». Сегодня менеджер проекта назначил ей целых n заданий, но это не огорчило Полину, ведь она пишет код быстро и без ошибок, а единственное, что замедляет её — необходимость коммитить выполненные задания. Коммит — это сохранение изменений в коде в системе контроля версий.
В «Тындексе» действуют строгие правила относительно содержания коммитов: не разрешается коммитить после изменения каждой строчки кода, с другой стороны, коммиты должны быть небольшими и логически однородными. Чтобы формализовать эти требования, каждому заданию был сопоставлен коэффициент изменения кода — целое число от 1 до 109. Коммит считается хорошим, если произведение коэффициентов изменения кода заданий, входящих в коммит, принадлежит отрезку [l; r]. Также не разрешается коммитить частично выполненное задание.
Полина должна выполнять задания по очереди, то есть сделать первые несколько заданий, затем закоммитить изменения, потом сделать следующие несколько заданий, снова закоммитив изменения, и так далее. Поэтому Полину интересует минимальное количество хороших коммитов, достаточное для выполнения всех заданий. Поможете Полине?

Исходные данные

В первой строке даны целые числа n, l, r (1 ≤ n ≤ 50000; 1 ≤ lr ≤ 1018) — количество заданий и ограничения на произведение коэффициентов изменения кода соответственно.
В следующей строке дано n целых чисел — коэффициенты изменения кода заданий. Все коэффициенты — целые числа от 1 до 109.

Результат

Если Полина не сможет выполнить и закоммитить все задания, в единственной строке выведите «-1».
Иначе в единственной строке выведите целое число — минимальное количество хороших коммитов, достаточное для выполнения всех заданий.

Примеры

исходные данныерезультат
7 8 20
2 4 8 16 1 3 5
4
7 10 20
2 4 8 16 1 3 5
-1

Замечания

В первом тестовом примере одним из оптимальных разбиений на коммиты является следующее: 2 4 | 8 | 16 1 | 3 5.
Автор задачи: Анна Ханова
Источник задачи: Контест "Лучше поздно, чем никогда"
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2135. Полина и коммиты