Masala J
Lampalar
Bobur qorong'i xonada \(n\) ta lampa qatoriga ega. Har bir lampa dastlab yoniq \((1)\) yoki o'chiq \((0)\) holatda bo'ladi.
Har soniyada quyidagi jarayon sodir bo'ladi: agar o'chiq lampaning kamida bitta qo'shnisi (chapda yoki o'ngda turgan lampa) yoniq bo'lsa, u ham yonib ketadi. Yoniq lampalar yoniq bo'lib qolaveradi.
\(k\) soniya o'tgandan keyin nechta lampa yoniq bo'ladi?
Birinchi qatorda \(t\) \((1 \le t \le 10^4)\) — testlar soni beriladi.
Har bir test uchun:
Birinchi qatorda \(n\) va \(k\) \((1 \le n \le 2 \cdot 10^5), (0 \le k \le 2 \cdot 10^5)\) — lampalar soni va soniyalar soni.
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) \((a_i \in {0, 1})\) — lampalarning boshlang'ich holati. \(1\) yoniq, \(0\) o'chiq.
Barcha testlar bo'yicha \(n\) larning yig'indisi \(2 \cdot 10^5\) dan oshmasligi kafolatlanadi.
Har bir test uchun bitta butun son — \(k\) soniyadan keyin yoniq lampalar soni.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 1 1 0 0 0 1 4 2 0 0 0 0 6 1 0 1 0 0 1 0 |
4 0 6 |
Birinchi testda: dastlab lampalar holati [1, 0, 0, 0, 1]. \(1\) soniya o'tgandan keyin, \(1\)-lampa \(2\)-lampani yoqadi (chapdan qo'shni), va \(5\)-lampa \(4\)-lampani yoqadi (o'ngdan qo'shni). Natija: [1, 1, 0, 1, 1] — \(4\) ta yoniq lampa.
Ikkinchi testda: hech qanday lampa yoniq emas, shuning uchun hech narsa yonmaydi. Javob \(0\).
Uchinchi testda: dastlab [0, 1, 0, 0, 1, 0]. \(1\) soniyadan keyin \(2\)-lampa \(1\)- va \(3\)-lampalarni yoqadi, \(5\)-lampa \(4\)- va \(6\)-lampalarni yoqadi. Natija: [1, 1, 1, 1, 1, 1] — \(6\) ta yoniq lampa.
Telegram kanalimizga obuna bo'ling