Tourist Assignments
TopCoder SRM 577
Time Limit: 0.1s, Memory Limit: 64MiB
Ели ще участва в TopCoder SRM. Преди началото на състезанието всеки състезател е разпределен във виртуална "стая". Това се случва по следния алгоритъм:
  1. Нека броя регистрирали се участници е N.
  2. Броят стаи R е N / 20, ако N се дели на 20, или R = N / 20 + 1 в противен случай. Тук операторът '/' означава целочислено деление.
  3. Регистриралите се участници биват сортирани по рейтинг в намаляващ ред.
  4. Първите R с най-висок рейтинг са разпределени на случаен принцип в стаите, така че никои двама да не са в една и съща. След това същото е направено със следващите R по рейтинг, и т.н., докато на всеки е намерена стая. Забележете, че е възможно на последната стъпка да има по-малко от R останали участника, но и те са разпределени по такъв начин, че да няма двама в една и съща стая.
Ели ви е дала рейтингите на всички регистрирали се състезатели A1, A2, ..., AN, като нейният рейтинг е първият в списъка. Сега тя се чуди какъв е шансът да е в стаята на човека с най-висок рейтинг?
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N – колко състезателя са се регистрирали. На следващия ред ще има N цели числа A1 A2 ... AN – рейтингите на състезателите. Гарантирано е, че няма да има двама с еднакъв рейтинг.
Изход
На стандартния изход изведете очакването Ели да бъде в стаята на човека с най-висок рейтинг. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 8 ≤ N ≤ 2500
  • 1200 ≤ Ai ≤ 3923
Примерен Вход Примерен Изход
91 2011 1395 1639 1842 1426 2393 2348 1571 2077 1222 1966 1495 1309 1251 3039 1566 1989 2083 1819 1875 1579 2206 1503 1461 2262 2116 1429 2150 1834 2097 2093 1518 1923 1796 1669 2342 1826 2374 1635 1683 1656 2190 1632 1946 1207 1293 2029 2243 2252 1559 2366 1590 1563 2319 1391 1255 1727 1565 1911 1679 1282 2358 1682 2148 3555 2362 1208 2044 1949 1980 1983 2215 2184 1545 1665 2146 1272 2110 1889 1829 1808 2065 1987 1297 2216 1609 1318 1816 1444 2000 1404 0.2
Рейтингът на Ели е 2011, а 91-мата състезатели са разделени в 5 стаи.
Мрън!