АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Hackerland үндэсний банк харилцагчийнхаа дансан дахь мөнгийг дараах байдлаар ажиглан хууль бусаар мөнгө олж

байна уу үгүй юу гэдгийг мэддэг. Хэрэв миний шалгаж байгаа өдрийн орлого өмнөх d өдрийн орлогын медианыг

2 дахин авсанаас тэнцүү юм уу их байх юм бол тэр өдөр сэжигтэй гэсэн үг.

Харилцагчийн n өдрийн орлогын мэдээлэл байгаа бол хэдэн луйвар хийсэн магадлалтай сэжигтэй өдөр байгааг олоорой.

Жишээлбэл

d=3 n=5  {10, 20, 30, 40, 50}  гэсэн орлоготой эхний 3 өдрийг шалгаж чадахгүй.

4 дэх өдрөөс эхлэе.

40 орлого орж ирсэн. Өмнөх 3 өдрийн орлого {10 20 30}. Медиан нь 20.  20 * 2 = 40 тул энэ өдөр сэжигтэй.

5 дахь өдөр

50 орлого орсон. Өмнөх 3 өдрийн орлого {20, 30, 40}. Медиан нь 30.     30 * 2 > 50 тул энэ өдөр зүгээр.

Бидэнд дээрх өгөгдлөөр бол 1 сэжигтэй тохиолдол байна.

Тэмдэглэл

d тэгш тоо бол голын 2 тооны арифематик дундаж медиан нь болно.

Оролт

Эхний мөрөнд n, d тоо зайгаар тусгаарлагдан өгөгдөнө.

1 <= n < 2*10^5,  1 <= d <= n.

Дараагийн мөрөнд n өдрийн орлого зайгаар тусгаарлагдан өгөгдөнө.

0 <= орлого <= 200.

Гаралт

Сэжигтэй тохиолдлын тоог хэвлэнэ.

Жишээ

Оролт

9 5

2 3 4 2 3 6 8 4 5

Гаралт

2

Тайлбар

6 дахь өдрөөс эхэлж шалгана.

Эхний 5 өдрийн медиан {2 2 3 3 4} 3 * 2 > 5 учир зүгээр.

2-оос 6 дахь өдрийн медиан {2 3 3 4 6}  3 * 2 < 8 учир зүгээр.

3-аас 7 дахь өдрийн медиан {2 3 4 6 8}  4 * 2 > 4 учир сэжигтэй.

4-өөс 8 дахь өдрийн медиан {2 3 4 6 8} 4 * 2 > 5 учир сэжигтэй.

8, 9 дэх өдрүүд сэжигтэй.

Орчуулсан : Монгол Оюу сургуулийн 11-р ангийн сурагч Э.Цэлмэг