Волки
Нам не страшен серый волк,
Серый волк, серый волк!
Где ты ходишь, глупый волк,
Старый, страшный волк?
Всем вам хорошо известна сказка о трех поросятах – братьях Ниф-Нифе, Нуф-Нуфе и Наф-Нафе. Ниф-Ниф построил себе дом из соломы, Нуф-Нуф – из веток и тонких прутьев, а Наф-Наф сделал свой дом из кирпичей, надежный и прочный, как крепость. Когда пришел Волк, чтобы съесть поросят, каждый из них спрятался в своем домике. Волк подошел к домику из соломы, набрал полную грудь воздуха и стал выпускать его на домик, сдувая постепенно крышу, окна, стены и т.д. Совсем немного времени понадобилось ему, чтобы разрушить этот дом и съесть Ниф-Нифа. Немного больше времени ушло на то, чтобы сдуть домик из веток и съесть Нуф-Нуфа. А вот дом из кирпичей оказался настолько прочным, что Волку не хватило всей жизни на то, чтобы разрушить его…
Много лет прошло с тех пор. Популяция поросят за это время выросла до N особей. Каждый из них построил себе дом с некоторой прочностью. Но за это же время увеличилось и количество волков. Теперь есть K волков, которые очень голодны и хотят съесть всех поросят. Для этого надо разрушить их домики. Наученные горьким опытом своего предка, волки решили разбиться на несколько стай, каждая из которых одновременно с остальными начнет атаковать определенный домик. Переходить затем от одного домика к другому волки не могут. Известно, что один волк сможет сдуть дом прочности P за P часов, два волка – за P/2 часов и т.д. K волкам на разрушение дома прочности P потребуется P/K часов.
Помогите волкам определить за сколько времени им удастся поймать и съесть всех поросят.
Технические условия
Входные данные
Входной файл состоит из нескольких наборов данных. В первой строке каждого набора записаны два целых числа K и N – количество волков и поросят соответственно. (1 ≤ K ≤ 108, 1 ≤ N ≤ 105). Вторая строка содержит N целых чисел P1, P2, …, PN, отделенных друг от друга одним пробелом, где Pi (1 ≤ Pi ≤ 109) — прочность домика i-го поросенка. Пара значений K=N=0 означает конец файла.
Выходные данные
В выходной файл необходимо вывести одно вещественное число с точностью не менее 6 знаков — минимальное время, которое потребуется волкам для того, чтобы разрушить домики всех поросят. В случае невозможности разрушения всех домиков, выведите слово "Impossible" (без кавычек). Ответ для каждого набора данных должен выводиться в отдельной строке.
Информация о задаче
Лимит времени: 2 секундыЛимит памяти: 64 MB
Баллы за пройденный тест: 50
Сложность: 67% 4/12
Пример
Пример входных данных1 3 1 2 1000 5 3 1 2 3 10 3 1 2 3 0 0 |
Пример выходных данныхImpossible 1.500000 0.666667 |
| ← Неподвижные элементы матрицы | Список задач | Треугольники → |
