C. Төвшнүүд ба Бүс нутгууд

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Радэвүүш нэгэн компьютерын тоглоом тоглож байв. Уг тоглоом нь $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг төвшинтэй бөгөөд төвшнүүд нь $k$ ширхэг бүс нутгуудад (бүлэг) хуваагдсан байв. Бүс нутаг болгон нь ямар нэгэн эерэг тоон ширхэг дараалсан төвшнүүдийг агуулсан байх юм.

Уг тоглоом нь дараах үйл явцыг давтан хийнэ:

  1. Хэрэв бүх бүс нутгууд нь ялагдсан байвал уг тоглоом нь шууд дуусах юм. Бусад тохиолдолд систем дор хаяж нэг ширхэг ялагдаагүй төвшин агуулах хамгийн эхний бүс нутгийг хайж олно. Уг бүс нутгийг $X$ гэж тэмдэглэе.
  2. Систем нь хясаануудад зориулан нэгэн хоосон цүнх бий болгосон байна. Хясаа болгон нь нэг төвшинг илэрхийлэх бөгөөд олон тооны хясаанууд нь нэгэн ижил төвшинг илэрхийлсэн байж болох юм.
    • $X$ бүс нутагт байх аль хэдийн ялагдсан төвшин $i$ бүрийн хувьд систем $t_{i}$ ширхэг хясааг цүнхэнд нэмж хийнэ(өөрөөр хэлбэл $i$-р төвшинг илэрхийлэх бүх хясаануудыг хийх юм).
    • $j$-ээр $X$ бүс нутагт байх хамгийн эхний ялагдаагүй төвшинг тэмдэглэе. Тэгвэл систем нь $t_{j}$ ширхэг хясаануудыг цүнхэнд хийнэ.
  3. Эцэст нь систем уг цүнхнээс нэг ширхэг хясааг жигдхэн бөгөөд дурын байдлаар сонгон авах бөгөөд тоглогч уг хясаагаар илэрхийлэгдэх төвшнөөс эхлэн тоглоомыг тоглох юм. Тоглогч нэг төвшинг ялахын тулд нэг цаг зарцуулах бөгөөд тэрээр урьд нь уг төвшинг ялж байсан хэдий ч мөн л нэг цаг зарцуулах юм.

Өгөгдсөн $n$, $k$ болон $t_{1}, t_{2}, ..., t_{n}$ утгуудын хувьд та эдгээр төвшнүүдийг бүс нутгуудад хуваах юм. Төвшин болгон нь заавал яг нэг ширхэг бүс нутагт харьяалагдсан байх ёстой ба бүс нутаг болгон нь заавал хоосон биш дараалсан төвшнүүдийн олонлогоос тогтсон байна. Тэгвэл тоглоомыг дуусгахын тулд шаардагдах нийт цагийн боломжит хамгийн бага хүлээгдэж буй утгыг (expected value) олно уу.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n ≤ 200 000$, $1 ≤ k ≤ min(50, n)$) өгөгдөх ба эдгээр нь харгалзан төвшнүүдийн тоо болон бүс нутгуудын тоог тус тус илэрхийлнэ.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($1 ≤ t_{i} ≤ 100 000$)-ууд өгөгдөнө.

Гаралт

Хэрэв төвшнүүд нь эдгээр бүс нутгуудын хооронд оновчтой байдлаар тархсан гэж үзвэл тоглоомыг дуусгахад шаардагдах нийт цагийн боломжит хамгийн бага хүлээгдэж буй утгыг илэрхийлэх нэг бодит тоог хэвлэнэ үү. Хэрэв таны хариултын абсолют болон харьцангуй алдаа нь $10^{ - 4}$-өөс хэтрэхгүй бол таны хариултыг зөвөөр тооцно.

Тодруулбал: таны хариултыг $a$, шүүх хариултыг $b$ гэж үзье. Тэгвэл хэрэв байвал шалгагч программ таны хариултыг зөвөөр тооцох юм.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
4 2
100 3 5 7
Гаралт
5.7428571429
Оролт
6 2
1 2 4 8 16 32
Гаралт
8.5000000000

Тэмдэглэл

Эхний жишээнд бид $4$ ширхэг төвшинг $2$ ширхэг бүс нутгуудад хуваана. Эхний бүс нутгийг зөвхөн нэг ширхэг төвшинтэй (энэ нэг ширхэг төвшин нь хамгийн эхний төвшин байх ёстой юм) байхаар 2-дахь бүс нутгийг үлдсэн 3-н төвшинг агуулж байхаар хуваах нь хамгийн оновчтой байна.

2-дахь жишээнд тус бүр нь $3$ төвшин агуулах 2 бүс нутаг болгон хуваах нь хамгийн оновчтой байна.

Сэтгэгдлүүдийг ачааллаж байна...