Время

14:59:16
24 May 2012
Версия для печати

Волки


Нам не страшен серый волк,
Серый волк, серый волк!
Где ты ходишь, глупый волк,
Старый, страшный волк?


prb238

   Всем вам хорошо известна сказка о трех поросятах – братьях Ниф-Нифе, Нуф-Нуфе и Наф-Нафе. Ниф-Ниф построил себе дом из соломы, Нуф-Нуф – из веток и тонких прутьев, а Наф-Наф сделал свой дом из кирпичей, надежный и прочный, как крепость. Когда пришел Волк, чтобы съесть поросят, каждый из них спрятался в своем домике. Волк подошел к домику из соломы, набрал полную грудь воздуха и стал выпускать его на домик, сдувая постепенно крышу, окна, стены и т.д. Совсем немного времени понадобилось ему, чтобы разрушить этот дом и съесть Ниф-Нифа. Немного больше времени ушло на то, чтобы сдуть домик из веток и съесть Нуф-Нуфа. А вот дом из кирпичей оказался настолько прочным, что Волку не хватило всей жизни на то, чтобы разрушить его…

   Много лет прошло с тех пор. Популяция поросят за это время выросла до N особей. Каждый из них построил себе дом с некоторой прочностью. Но за это же время увеличилось и количество волков. Теперь есть K волков, которые очень голодны и хотят съесть всех поросят. Для этого надо разрушить их домики. Наученные горьким опытом своего предка, волки решили разбиться на несколько стай, каждая из которых одновременно с остальными начнет атаковать определенный домик. Переходить затем от одного домика к другому волки не могут. Известно, что один волк сможет сдуть дом прочности P за P часов, два волка – за P/2 часов и т.д. K волкам на разрушение дома прочности P потребуется P/K часов.

   Помогите волкам определить за сколько времени им удастся поймать и съесть всех поросят.


Технические условия

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

   Входной файл состоит из нескольких наборов данных. В первой строке каждого набора записаны два целых числа K и N – количество волков и поросят соответственно. (1K108, 1N105). Вторая строка содержит N целых чисел P1, P2, …, PN, отделенных друг от друга одним пробелом, где Pi (1Pi109) — прочность домика 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


← Неподвижные элементы матрицы Список задач Треугольники →