Олимпиадный тренинг

Задача . Wifi Setup

Задача

N (1 <= N <= 2000) коров Фермера Джона расположены на прямой линии (дороге от амбара до пастбища). ФД хочет расставить вдоль этой прямой точки беспроводного доступа в Internet, так чтобы все коровы были в зоне покрытия.
Стоимость wifi-станции зависит от расстояния, ан которое она может передавать сигнал. Станция с мощностью(радиусом действия) r стоит A + B*r , где A - фиксированная цена установки станции B - стоимость на 1 расстояния, на которое передается информация.
Если такая станция установлена в позиции x, то она может передавать данные до любой коровы, расположенной в интевале x-r...x+r. Допускается станция с мощностью передачи 0, но, поскольку r=0, она будет работать только для коровы, размещенной в самой точке x размещения станции.
По заданным величинам A и B, а также координатам коров, определите самый дешевый способ, которым ФД сможет обеспечить беспроводное покрытие всех своих коров.
PROBLEM NAME: wifi
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа: N A B (0 <= A, B <= 1000).
* Строки 2..1+N: Каждая строка содержит одно целое число в диапазоне 0..1,000,000 описывающее размещение одной коровы.
Формат выходных данных
* Строка 1: Минимальная стоимость обеспечения беспроводным покрытием всех коров.
Примечание
Оптимальное решение - построить базовую станцию в позиции 3.5 (с мощностью/радиусом действия 3.5) и другую станции в позиции 100 с мощностью (радиусом действия) 0. Первая станция обеспечит покрытие коров 1 и 2, вторая - коровы 3.

Примеры

№	Входные данные	Выходные данные
1	3 20 5 7 0 100	57.5

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет