Masala #0984
Santa Claus
Yangi yilda Santa Claus bolakaylarga har yilgidan o'zgacha sovg'a ulashish istagida bolakaylarga xar xil turdagi kitoblarni sovg'a qilmoqchi.
Santa Clous ning \(1\) dan \(n\) gacha raqamlangan kitob javoni bor \(i-\)javonda \(S_i\) ta kitob ma'vjud. Barcha kitoblar Santaning chang'isiga sig'maydi shuning uchun u quyidagi qonuniyat asosida kitoblarni ma'lum qismini navbat bilan ajratib olib tarqatishga qaror qildi.
Har safar Santa Clous yo'lga chiqishidan oldin kitoblarni quyidagicha yig'ib oladi:
- Santa \(i-\)javondan\((S_i>1)\) \(1\) ta kitob oladi;
- \(i\) ning yangi qiymati uchun \(i=i+S_i\) ni tanlaydi;
- Ushbu jarayon \(n < i\) bo'lguncha davom etadi.
Sizning vazifangiz Santa Clousning barcha javonlarida 1 tadan kitob qolishi uchun eng kamida nechchi marotaba sovg'alarni tarqatishi uchun junab ketishini aniqlashdan iborat.
Kirish faylining dastlabki satrida \(t(1\leq t\leq 500)\) testlar soni beriladi;
Kiyingi satrlarda testlar beriladi har bir testning birinchi satrida \(n(1\leq n\leq 5000)\) Santaning javonlari soni va kiyingi satrda \(n\) tadan son \(S_i(1\leq S_i\leq 10^9)\) \(i-\)javonda nechta kitob borligini anglatadi.
Har bir test uchun alohida satrlarda Santa Clous kamida nechchi marotaba sovg'alarni ulashgani yo'lga chiqishini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 4 4 2 2 2 2 1 1 4 4 3 2 1 |
4 0 5 |
\(1-\)testda: Javonda \([4,2,2,2]\) kitoblar joylashgan.
Santa \(i=2\) ikkinchi javondan kitob olishni boshlaydi va kiyingi kitobni \(i+S_i=4-\)javondan oladi. Javondagi kitoblar \([4,1,2,1]\).
Kiyingi qadamlarda
[4, 1, 2, 1] \(1-\)javondan;
[3, 1, 2, 1] \(1-\)javondan;
[2, 1, 2, 1] \(1\) va \(3\) javonlardan oladi. Nateja [1, 1, 1, 1] jami bo'lib 4 marotaba.
Telegram kanalimizga obuna bo'ling