Bottles
TopCoder TCO2017 China
Time Limit: 0.1s, Memory Limit: 64MiB
Ели решава стари задачи в TopCoder. Както може би знаете, отварянето на стар practice room може да отнеме цяла вечност…

Докато чака стаята да се зареди, момичето се забавлява по следния начин. Пред себе си тя е наредила N бутилки с еднаква вместимост, съдържащи различни количества вода: бутилка i съдържа Ai милилитра. Ели намира най-пълната и най-празната бутилка и изсипва известно количество вода от първата във втората, докато двете станат еднакво пълни. Ако има няколко възможни най-пълни или най-празни бутилки, тя избира които и да е от тях (това не влияе на крайния резултат). След това момичето отново намира най-пълната и най-празната бутилка измежду всички N и прелива вода от едната в другата, докато се изравнят.

Ели изпълнява тази процедура K пъти, докато най-накрая стаята се зареди и тя почне да решава. Сега момичето се чуди какво ще е количеството вода в най-празната бутилка накрая?
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K – съответно броя бутилки и броя повторения на описаната процедура. На следващия ред ще бъдат зададени N цели числа A1, A2, ..., AN – началното количество вода в бутилките.
Изход
На стандартния изход изведете едно число с плаваща запетая – количеството вода в най-празната бутилка след K итерации на описаната процедура. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 2 ≤ N ≤ 50
  • 1 ≤ K ≤ 1,000,000,000
  • 0 ≤ Ai ≤ 1,000,000,000
Примерен Вход Примерен Изход
5 8 42 13 17 7 22 20.0625
40 1234567 937831252 223252363 706118333 954711869 819583497 520873195 879422756 464831418 156067240 646868794 894534170 23380905 855234472 319560027 305097549 374217481 86837363 718892301 952809474 558293585 91833518 862607400 982038771 942620013 507984782 546527456 615697673 237645185 53645793 780959476 136257699 969658933 959150775 43875123 9012 349823412 85123543 349085123 194357213 229834565 508428837.725
В първия пример Ели има пет бутилки, първоначално съдържащи 42, 13, 17, 7, и 22 милилитра вода.
Момичето прилага описаната процедура осем пъти.
  1. Тя налива от бутилка, съдържаща 42 милилитра в бутилка, съдържаща 7, правейки количеството вода в бутилките {24.5, 13, 17, 24.5, 22}
  2. Тя налива от бутилка, съдържаща 24.5 милилитра в бутилка, съдържаща 13, правейки количеството вода в бутилките {18.75, 18.75, 17, 24.5, 22}
  3. Тя налива от бутилка, съдържаща 24.5 милилитра в бутилка, съдържаща 17, правейки количеството вода в бутилките {18.75, 18.75, 20.75, 20.75, 22}
  4. Тя налива от бутилка, съдържаща 22 милилитра в бутилка, съдържаща 18.75, правейки количеството вода в бутилките {20.375, 18.75, 20.75, 20.75, 20.375}
  5. Тя налива от бутилка, съдържаща 20.75 милилитра в бутилка, съдържаща 18.75, правейки количеството вода в бутилките {20.375, 19.75, 19.75, 20.75, 20.375}
  6. Тя налива от бутилка, съдържаща 20.75 милилитра в бутилка, съдържаща 19.75, правейки количеството вода в бутилките {20.375, 20.25, 19.75, 20.25, 20.375}
  7. Тя налива от бутилка, съдържаща 20.375 милилитра в бутилка, съдържаща 19.75, правейки количеството вода в бутилките {20.0625, 20.25, 20.0625, 20.25, 20.375}
  8. Тя налива от бутилка, съдържаща 20.375 милилитра в бутилка, съдържаща 20.0625, правейки количеството вода в бутилките {20.21875, 20.25, 20.0625, 20.25, 20.21875}
Най-малкото количество вода в бутилките след всички транзакции е 20.0625 милилитра.
Мрън!