Nizovi 0 i 1 bez dve susedne 1


#1

Pozdrav! Imam problem sa rješenjem ovog zadatka. Testirao sam program na velikom broju vlastitih primjera i izbacivao je tačan rezultat, ali na sajtu je WA.

https://pastebin.com/iCGHvu3M


#2

Nisam detaljno čitao kod ali u drugom delu nisi kao veličinu niza koristio y koje je dato nego n koje si dobio kao as.size() u prvom delu.


#3

I usput mislim da je u potpunosti suvišno koristiti binarnu za drugi deo jer se k uvek smanjuje i onda možeš jednom da prodjes kroz ceo niz c u O(n) umesto da radiš u najgorem slučaju n puta binarnu u O(nlogn), čak se i lakše kuca :grinning: i za binarnu možeš da koristiš funkcije lower_bound() i upper_bound() što takodje pomaže u kucanju. I nemoj da stavljas promenjive za veličine niza, možeš na internetu da nadjes zašto.


#4

Glavni problem jeste bio u korištenju as.size(), a ne y, jer sam mislio da je to uvijek jednako (bar je tako bilo u ponuđenim testovima :slightly_smiling_face: ). Da, moglo je proći i bez binarne, a i c[i] se može izračunati kao zbir c[i-1]+c[i-2] itd. Hvala na pomoci i savjetima!


#5

Da, to sam razmišljao da napišem ali bi bili malo suviše :grinning: i nema na čemu.