B. Дундаж хандалтууд

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

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

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

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

Энэхүү бодлогонд та ВК олон нийтийн сүлжээнд ашигласан жинхэнэ алгоритмтэй тулгарах болно.

Өндөр ачаалалтай вэбсайт ажиллуулдаг бусад бүх компаний адил ВК хөгжүүлэгчид нь хандалтын статистикын асуудалтай тогтмол тулгардаг. Вэбсайтын нэгэн чухал үзүүлэлт бол $T$ секундын туршид хандаж буй хандалтуудын дундаж хандалтын тоо юм (Жишээ нь: $T = 60 seconds = 1 min$, $T = 86400 seconds = 1 day$). Жишээ нь, хэрвээ энэхүү утга огцом багасвал вэбсайтад хандахад асуудал байна гэсэн үг. Харин энэ утга ихэсвэл, өсөлтийн шалтгааныг олох ба шаардлага гарвал вэбсайтад нэмэлт серверүүд нэмнэ.

Гэхдээ хэрвээ таны боловсруулах гэж байгаа дата том хэмжээний олон нийтийн сүлжээнийх бол иймэрхүү дундаж утга олох даалгавар ч гэсэн томоохон асуудал болдог. Тиймээс хөгжүүлэгчид асуудлыг шийдвэрлэхдээ оригнал техникийг илүү үр бүтээлтэйгээр ашигладаг.

Дараах загварыг авч үзье. Бидэнд $n$ секундын турш ажилладаг үйлчилгээ байна. Энэ $t$ ($1 ≤ t ≤ n$) хугацааны мөч болгон дахь хандалтын тоо болох $a_{t}$-г бид мэднэ. Дараах огцом өөрчлөлтийн дундажыг тооцоолдог алгоритмыг тодорхойльё. Энд $c$-г нэгээс их жинхэнэ тоо гэж үзье.

// энэ тогтмол утгыг зөв тодорхойлох нь тооцоологдох статистикийн
// хугацааны интервалыг зөв тодорхойлоход тустай  
давхар c = тогтмол утга;   

// алгоритмын үр дүнгээс хамаарч  
// энэ хувьсагч нь сүүлийн T секундын турш
// ирсэн хандалтын дундажыг олдог  
давхар дундаж = 0.0;   

t = 1..n утгуудад: // секунд болгонд дараах үйлдлийг хийнэ:
    // $a\_{t}$ нь сүүлийн секундэд ирсэн хандалтын тоо;  
    дундаж = (дундаж + $a\_{t}$ / T) / c;

Тиймээс дундаж хувьсагч нь сүүлийн секундэд ирсэн хандалтын тооноос шалтгаалан секунд болгонд шинээр тооцоологддог. Бид зарим математикийн тооцоолол ашиглан тогтмол $c$-ийн утгыг зөв сонгох нь дундажын утгыг жинхэнэ дундаж утга $a_{x}$-ээс нэг их ялгаагүй гэдгийг харуулж чадах юм (энд $t - T + 1 ≤ x ≤ t$).

Ийм тооцооллын давуу тал нь тооцоолол зөвхөн сүүлийн секундэд ирсэн хандалтын тоог ашигладаг бөгөөд том хэмжээний хугацааны интервалын хандалтын түүх хадгалах шаардлагагүй болдог. Үүнээс гадна, энэ тооцоолол нь хуучин датаны оронд шинэ датаг ихээхэн ашигладаг учир тухайн утганд гарсан огцом өөрчлөлтийг илүү хурдан мэдээлэлдэг.

Харин энэхүү тооцооллыг програмчлалд ашиглахын өмнө заавал шаардагдах нэг үйлдэл бий. Энэ нь тооцооллыг өгөгдсөн датан дээр туршилт хийн тооцооллын баталгаатай байдлыг шалгах юм. Таны даалгавар нь алгоритмын үр дүнд гарсан датаг жинхэнэ дататай харьцуулах юм.

Танд $n$ ширхэг $a_{t}$ болон бүхэл тоо $T$, жинхэнэ тоо $c$ өгөгдөнө. Үүнээс гадна, $p_{j}$ ($1 ≤ j ≤ m$) мөчүүд өгөгдөнө. Эдгээр мөчүүдэд бидний сонирхож байгаа сүүлийн $T$ секундэд хандсан хандалтуудын дундаж утгуудыг бид олох гэж байгаа. 2 алгоритмыг ажиллуулна уу. Эхний алгоритм нь томьёо ёсоор шаардлагатай утгыг тооцоолно. 2 дахь алгоритм нь дээр тайлбарлагдсан дундаж утгыг тооцоолно. 2 утгыг хэвлэх ба 2 дахь алгоритмын харьцангуй алдааг дараах томьёогоор олно уу: . Энд $approx$ нь 2 дахь алгоритмын дагуу олдсон ойролцоолсон дундаж утга ба $real$ нь эхний алгоритмоор олдсон жинхэнэ утга.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 2*10^{5}$), бүхэл тоо $T$ ($1 ≤ T ≤ n$), жинхэнэ тоо $c$ ($1 < c ≤ 100$) өгөгдөнө. Эдгээр нь үйлчилгээний ажиллах хугацаа, хандалтын дундаж утгыг тодорхойлох хугацааны интервалын урт, ойролцоосон алгоритмын коэффициент $c$. Тоо $c$ нь таслалын ардаас яг 6-н орон өгөгдөнө.

Дараагийн мөрөнд $n$ ширхэг бүхэл тоонууд $a_{t}$ ($1 ≤ a_{t} ≤ 10^{6}$) өгөгдөнө. Эдгээр нь хугацааны мөч болгонд хандсан хандалтын тоо юм.

Дараагийн мөрөнд бидний сонирхож байгаа мөчүүдийн нийт тоо болох бүхэл тоо $m$ ($1 ≤ m ≤ n$) өгөгдөнө. Тодруулбал эдгээр мөчүүдэд сүүлийн $T$ секундэд хандсан хандалтын дундаж утгыг бид олох юм.

Дараагийн мөрөнд дээр дурьдагдсан мөчүүд болох $m$ ширхэг бүхэл тоонууд $p_{j}$ ($T ≤ p_{j} ≤ n$) өгөгдөнө. Мөчүүд $p_{j}$ нь ихсэх дарааллаар өгөгдөнө.

Гаралт

$m$ ширхэг мөр хэвлэнэ үү. $j$ дэхь мөр нь 3 тоонууд $real$, $approx$, $error$-ыг агуулна. Энд:

  • нь сүүлийн $T$ секундэд хандсан хандалт болох дундаж жинхэнэ тоо;
  • $approx$ нь өгөгдсөн алгоритмээр тооцоологдох ба хугацааны $t = p_{j}$ (циклийн $p_{j}$ дэхь давталтыг ажиллуулсаны дараа) мөч дэхь $mean$ утгатай тэнцэнэ;
  • нь ойролцоолсон алгоритмын харьцангуй алдаа.

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

Орчуулсан: Энхлут

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

Оролт
1 1 2.000000
1
1
1
Гаралт
1.000000 0.500000 0.500000
Оролт
11 4 1.250000
9 11 7 5 15 6 6 6 6 6 6
8
4 5 6 7 8 9 10 11
Гаралт
8.000000 4.449600 0.443800
9.500000 6.559680 0.309507
8.250000 6.447744 0.218455
8.000000 6.358195 0.205226
8.250000 6.286556 0.237993
6.000000 6.229245 0.038207
6.000000 6.183396 0.030566
6.000000 6.146717 0.024453
Оролт
13 4 1.250000
3 3 3 3 3 20 3 3 3 3 3 3 3
10
4 5 6 7 8 9 10 11 12 13
Гаралт
3.000000 1.771200 0.409600
3.000000 2.016960 0.327680
7.250000 5.613568 0.225715
7.250000 5.090854 0.297813
7.250000 4.672684 0.355492
7.250000 4.338147 0.401635
3.000000 4.070517 0.356839
3.000000 3.856414 0.285471
3.000000 3.685131 0.228377
3.000000 3.548105 0.182702
Сэтгэгдлүүдийг ачааллаж байна...