Masala #0984

Xotira 32 MB Vaqt 3000 ms Qiyinchiligi 55 %

4.0 (Baholar 4)

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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida satrlarda Santa Clous kamida nechchi marotaba sovg'alarni ulashgani yo'lga chiqishini chop eting.

Misollar

#	input.txt	output.txt
1	3 4 4 2 2 2 2 1 1 4 4 3 2 1	4 0 5

Izoh:

$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 Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin