C. Вэт Шарк ба Цэцэг

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

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

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

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

Вэт Шарк-д зориулж цэцэг ургуулдаг $n$ шаркууд байдаг. Тэд бүгд ширээ тойрон сууж байна, бүх $1$-с $n - 1$ хүртэлх бүх $i$-н хувьд $i$ болон $i + 1$ нь хөршүүд. $n$ болон $1$ дахь шаркууд бас хөршүүд.

Шарк бүр $s_{i}$ тооны цэцэг ургуулна. $i$-р шаркын хувьд $s_{i}$ утга $l_{i}$-с $r_{i}$ хүртэлх тооноос тэнцүү магадлалтайгаар санамсаргүй сонгосон бүхэл тоон утга байна. Вэт Шарк дуртай анхны тоо болох $p$ гэсэн тоотой ба үүндээ үнэхээр дуртай! Хэрвээ ямар ч хоёр хөрш $i$ болон $j$-н хувьд $s_{i}*s_{j}$-н үр дүн $p$ тоонд хуваагдаж байвал Вэт Шарк баяртай байх бай эдгээр шарк бүрт $1000$ доллар өгдөг.

Өдрийн төгсгөлд бүх шаркууд Вэт Шаркын тэдэнд өгсөн мөнгөний нийлбэрийг олдог. Уг утгын байж болох утгуудын дундаж утгыг.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n$ ба $p$ ($3 ≤ n ≤ 100 000, 2 ≤ p ≤ 10^{9}$) байх ба шаркуудын тоо болон Вэт Шаркын дуртай анхны тоо юм. $p$ бол анхны тоо.

Дараагийн $n$ мөрийн $i$-р мөр бүрт $i$-р шаркын мэдээлэл байх ба зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ 10^{9}$) байх ба $i$-р шаркын үйлдвэрлэж чадах цэцгийн тоо. $s_{i}$ тоо нь $l_{i}$-с $r_{i}$ хүртэлх(оролцуулаад) тооноос тэнцүү магадлалтайгаар сонгогдсон гэдгийг сана.

Гаралт

Гаралтанд ганц бодит тоог хэвлэх ба энэ нь шаркуудын хүлээн авч болох долларын бүх тохиолдлын дундаж утга. Таны хариуны үнэмлэхүй болон харьцангуй алдаа нь $10^{ - 6}$-с их байж болохгүй.

Өөрөөр хэлбэл таны хариулт $a$ гэж бодъё харин шүүгчийн хариу $b$. Шалгагч програм дараах нөхцөлийг хангавал таны хариуг зөв гэж үзнэ .

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 2
1 2
420 421
420420 420421
Гаралт
4500.0
Оролт
3 5
1 4
2 3
11 14
Гаралт
0.0

Тэмдэглэл

Анхны тоо нь зөвхөн $1$ болон өөртөө хуваагдах эерэг бүхэл тоо байна. $1$ өөрөө анхны тоо биш.

Эхний жишээг авч үзье. Эхний шарк $1$-с $2$ хүртэлх тооны цэцэг ургуулдаг, хоёр дахь шарк $420$-с $421$ хүртэлх тооны цэцэг харин гурав дахь шарк $420420$-с $420421$ хүртэлх тооны цэцэг ургуулдаг. Энд $(s_{0}, s_{1}, s_{2})$ шарк бүрийн ургуулж чадах цэцгүүдийн найман тохиолдол байна:

  1. $(1, 420, 420420)$: $s_{0}*s_{1} = 420$, $s_{1}*s_{2} = 176576400$, $s_{2}*s_{0} = 420420$. Хослол бүрийн хувьд шарк бүр $1000$ доллар авна. Шарк бүр $2000$ доллар авах ба нийт $6000$ доллар болно.
  2. $(1, 420, 420421)$: Одоо, $s_{2}*s_{0}$ үржвэр $2$-т хуваагдахгүй. Ингээд $s_{0}$ болон $s_{2}$ шаркууд $1000$ доллар, харин $s_{1}$ шарк $2000$ доллар авна. Нийлбэр $4000$.
  3. $(1, 421, 420420)$: нийлбэр $4000$
  4. $(1, 421, 420421)$: нийлбэр $0$.
  5. $(2, 420, 420420)$: нийлбэр $6000$.
  6. $(2, 420, 420421)$: нийлбэр $6000$.
  7. $(2, 421, 420420)$: нийлбэр $6000$.
  8. $(2, 421, 420421)$: нийлбэр $4000$.

Нийт утга нь .

Хоёр дахь жишээн дээр мөнгө авах боломжгүй.

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