C. Эхний цифрийн хууль

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

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

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

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

Магадлалын онолд дараах олонд танигдсан логик зөрчилдөөнийг Бенфорд-ын хууль хэмээн нэрлэдэг: "бодит эх сурвалжаас авсан дурын тоонуудын маш олон бүртгэл дунд 1 гэсэн цифрээр эхлэсэн тоонууд нь бусад ямар ч цифрээр эхэлсэн тоонуудаас илүү олон удаа орсон байна" (энэ нь уг хуулийн хамгийн хялбар бөгөөд энгийн хэлбэр юм).

Зараа Codeforces-оос уг хуулийн талаар олж уншсан бөгөөд тэрээр уг онолын талаар сайтар судалж үзэхийг хүсжээ. Тэрээр нэгэн онц сонирхолтой бөгөөд төстэй дараах бодлогыг олжээ: Нийт $N$ ширхэг дурын хувьсагч байх ба эдгээрийн $i$-дахь нь $[L_{i};R_{i}]$ сегмент доторх дурын бүхэл тоон утга авч болох юм (уг сегмент доторх бүх тоонууд нь тэнцүү магадлалтай байна). Өөрөөр хэлбэл $i$-дахь хувьсагч нь өгөгдсөн интервал $[L_{i};R_{i}]$-ын дурын бүхэл тоон утгыг $1 / (R_{i} - L_{i} + 1)$ магадлалтайгаар авч чадах юм.

Зараа эдгээр хувьсагчдын дор хаяж $K%$ ширхгийнх нь эхний цифр нь 1-тэй тэнцүү байх үзэгдлийн магадлалыг олохыг хүсжээ. Өөрөөр хэлбэл эдгээр дурын хувьсагчдын ямар нэгэн тогтсон утгуудын олонлогийг авч үзэх ба хувьсагчдын утга бүрийн зөвхөн эхний цифрийг (ХАХЦ- хамгийн ач холбогдолтой цифр) үлдээнэ. Дараа нь энэ дунд 1 гэсэн цифр нь хэдэн удаа орсон болохыг тоолох ба хэрэв эдгээр $N$ ширхэг утгууд дунд дор хаяж $K$ ширхэг нь 1 байвал, ийм байх утгуудын олонлогийн сайн олонлог гэж үзэх юм. Тэгвэл та өгөгдсөн дурын хувьсагчдын дээр дүрслэгдсэн тогтсон утгуудын олонлог нь сайн олонлог байх магадлалыг олно уу.

Оролт

Эхний мөрөнд дурын хувьсагчдын тоог илэрхийлэх $N$ ($1 ≤ N ≤ 1000$) тоо өгөгдөнө. Дараагийн $N$ мөрийн мөр болгонд хос бүхэл тоо $L_{i}, R_{i}$ өгөгдөх ба энэ нь дурын хувьсагчын тайлбарыг илэрхийлнэ. Өөрөөр хэлбэл бодлогод дүрслэгдсэн интервал өгөгдөнө. Мөн $1 ≤ L_{i} ≤ R_{i} ≤ 10^{18}$ байна.

Сүүлийн мөрөнд бүхэл тоо $K$ ($0 ≤ K ≤ 100$) өгөгдөнө.

Түүнчлэн оролтод өгөгдөх бүх тоонууд нь бүхэл тоонууд байна.

C++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийн бүү ашиглана уу. Та cin эсвэл %I64d тодорхойлогчийг ашиглахыг илүүд үзнэ үү.

Гаралт

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

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

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

Оролт
1
1 2
50
Гаралт
0.500000000000000
Оролт
2
1 2
9 11
50
Гаралт
0.833333333333333
Сэтгэгдлүүдийг ачааллаж байна...