Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Оптимизация сепарабельной функции

(Время: 1 сек. Память: 16 Мб Сложность: 31%)

Функцию n переменных f(x1, x2, ... , xn) назовем сепарабельной, если она представима как сумма следующего вида: f(x1, x2, ... , xn) = f1(x1) + f2(x2) + ... + fn(xn), где каждая fi зависит только от xi. В рассматриваемой задаче каждая из функций fi является многочленом второй степени от xi.

Задача минимизации заданной функции на гиперпараллелепипеде формулируется следующим образом: «Задана функция f(x1, x2, ... , xn) и множество ограничений a1 ≤ x1 ≤ b1, a2 ≤ x2 ≤ b2, ... , an ≤ xn ≤ bn. Необходимо найти точку (x1*, x2*, ... , xn*) такую, что она удовлетворяет всем ограничениям, и значение функции в ней минимальное среди всех возможных».

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

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 1000). Каждая из последующих n строк содержит по пять целых чисел: ai, bi, pi, qi, ri – они соответствуют ограничению ai ≤ xi ≤ bi и функции fi(xi) = pi•xi2 + qi•xi + ri (−1000 ≤ ai ≤ bi ≤ 1000, −10 ≤ pi, qi, ri ≤ 10, pi ≠ 0).

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите минимальное возможное значение f (x1*, x2*, ... , xn*). Во второй строке выведите x1*, x2*, ... , xn*, на которых достигается указанное минимальное значение. Ответ будет считаться правильным, если найденное минимальное значение отличается от правильного не более, чем на 10−3.

Примеры

INPUT.TXTOUTPUT.TXT
12
1 2 3 4 5
-1 1 1 2 3
14.0
1.0 -1.0
21
-1 1 1 0 0
0.0
-0.0

Пояснение

В первом примере задана функция f(x1, x2) = (3x12+4x1+5) + (x22+2x2+3), где x1 принадлежит отрезку [1, 2] и x2 принадлежит отрезку [-1, 1]. Минимум данной функции достигается при x1=1 и x2=-1, а ее значение равно 14.


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Оптимизация сепарабельной функции
 B. Мотивация
 C. Умножение многочленов
 D. Провода
 E. Биты
 F. Суперпозиция
 G. Отрезки - 2
 H. Последовательность

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru