|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 14-3. Резисторы
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 3 секунды |
Радиолюбитель Петя решил собрать детекторный приемник. Для этого ему понадобился конденсатор емкостью C мкФ. В распоряжении Пети есть набор из n конеденсаторов, емкости которых равны c1, c2, ... ,cn соответственно. Петя помнит, как вычисляется емкость параллельного соединений двух конденсаторов (Cnew = C1 + C2) и последовательного соединения двух конеденсаторов ( Cnew = (C1*C2)/(C1+C2) ). Петя хочет спаять некоторую последовательно-параллельную схему из имеющегося набора конеденсаторов, такую, что ее емкость ближе всего к искомой (то есть абсолютная величина разности значений минимальна). Разумеется, Петя не обязан использовать для изготовления схемы все конденсаторы.
Напомним определение последовательно-параллельной схемы.Схема, составленная из одного конденсатора, - последовательно-параллельная схема. Любая схема, полученная последовательным соединением двух последовательно-параллельных схем, - последовательно-параллельная, а также любая схема, полученная параллельным соединением двух последовательно-параллельных схем, - последовательно-параллельная.
Формат входных данных
В первой строке каждого входного файла заданы числа n и C. Во
второй строке содержится последовательность емкостей имеющихся
в наличии конеденсаторов с1, с2, ..., сn.
Значения всех емокостей - вещественные числа.
Для всех входных файлов n < 7.
Формат выходных данных
В выходной файл необходимо вывести емкость такой схемы, емкость
которой меньше всего отличается от C. Результат выводите с шестью знаками
после запятой.
Пример
| input.txt | output.txt |
3 1.66 1 2 1 |
1.666666 |
Пояснение к примеру: последовательно соединим первый и второй конденсаторы, а затем полученную схему соединим параллельно с третьим.