698C орчуулах · Codeforces.mn

# LRU
Өндөр ачаалалтай системийг зохион бүтээхийн тулд та заавал cache хийх үйл явц дээр тусгай анхаарал хандуулах хэрэгтэй юм. Уг бодлого нь хамгийн алдартай cache-лах алгоритм болох LRU (Least Recently Used)-ын талаар өгүүлнэ.

Бид cache-ыг $k$-аас ихгүй тооны зүйл(объект) хадгалж чадна гэж үзье. Ажлын үйл явцын эхэнд cache нь хоосон байх юм.

Хэрэв ямар нэгэн зүйл(объект) нь эргэлзээтэй байвал бид уг зүйлийг яг одоо cache дотор байгаа эсэхийг шалгах ба хэрэв уг зүйл(объект) нь cache дотор байхгүй бол уг зүйлийг cache-уруу шилжүүлнэ. Хэрэв үүний дараа cache дотор $k$-аас олон тооны зүйлс байвал хамгийн ойрын хугацаанд хэрэглэсэн зүйлийг (the least recently used one) нь cache дотроос хасах юм. Өөрөөр хэлбэл, бид хамгийн сүүлийн эргэлзээтэй зүйлүүд дундаас хамгийн бага хугацаатай нэгэн зүйлийг хасах ажээ.

Бүгд ижилхэн хэмжээ бүхий $n$ ширхэг бичлэг сервер дотор хадгалагдаж байгаа гэж үзье. Cache $k$-аас олонгүй тооны бичлэгийг хадгалж чадах ба дээр дүрсэлсэн cache-лах алгоритмыг хэрэгжүүлэх юм. Бид ямар ч үед хэрэглэгч серверт орж ирээд $i$ гэсэн бичлэгийг $p_{i}$ магадлалтайгаар үздэг болохыг мэдэж байв. Түүнчлэн бичлэг сонголт нь өмнө болсон үзэгдлүүдээс ямар нэгэн хамааралгүй байна.

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

## Оролт
Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ k ≤ n ≤ 20$) өгөгдөх ба эдгээр нь харгалзан нийт бичлэгийн тоо болон cache-ын хэмжээг тус тус илэрхийлнэ. Дараагийн мөрөнд $n$ ширхэг бодит тоонууд  $p\_{i}$ ($0 ≤ p\_{i} ≤ 1$)-ууд өгөгдөх ба эдгээр тус бүр нь таслалаас хойш 2-оос ихгүй оронгын нарийвчлалтайгаар өгөгдсөн байна.

Мөн түүнчлэн бүх $p_{i}$-уудын нийлбэр нь $1$-тэй тэнцүү байна.

## Гаралт
$n$ ширхэг бодит тоонууд хэвлэх ба эдгээрийн $i$-дахь тоо нь нийт $10^{100}$ ширхэг эргэлзээтэй үйл явц болж өнгөрсний дараа $i$-дахь бичлэг нь cache дотор хадгалагдаж үлдсэн байх магадлалтай тэнцүү байх юм. Хэрэв таны хариултын абсолют болон харьцангуй алдаа нь $10^{ - 6}$-аас хэтрэхгүй байвал таны хариултыг зөвөөр тооцно.

Тодруулбал, таны хариултыг $a$, шүүх хариултыг $b$ гэж үзье. Тэгвэл ![](http://codeforces.com/predownloaded/c6/2e/c62ea64d4651240724c5ac4779b671c741edec24.png) байвал шалгагч программ таны хариултыг зөвөөр тооцох юм.

-- Баатархүү

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

Оролт

3 1
0.3 0.2 0.5

Гаралт

0.3 0.2 0.5

Оролт

2 1
0.0 1.0

Гаралт

0.0 1.0

Оролт

3 2
0.3 0.2 0.5

Гаралт

0.675 0.4857142857142857 0.8392857142857143

Оролт

3 3
0.2 0.3 0.5

Гаралт

1.0 1.0 1.0