Az I/S. 53. feladat (2021. április)

I/S. 53. Adott egy $\displaystyle N$ hosszú bitsorozat. Az $\displaystyle i$-edik bitet $\displaystyle B[i]$-vel jelöljük. Minden lehetséges $\displaystyle 1\le x\le y\le N$-re a bitsorozat $\displaystyle x$-edik elemétől az $\displaystyle y$-adik eleméig terjedő részét kiegyensúlyozottnak nevezzük, ha ugyanannyi 1-es értékű bitet tartalmaz, mint 0-s értékűt (tehát ha a $\displaystyle B[x]$, $\displaystyle B[x+1]$, ..., $\displaystyle B[y]$ bitek közt azonos számú az 1-es és a 0-s értékű).

Adjuk meg, hogy hány olyan $\displaystyle x$, $\displaystyle y$ páros van, amire kiegyensúlyozott részt kapunk.

Bemenet: az első sor tartalmazza az $\displaystyle N$ számot, a második az $\displaystyle N$ hosszú bitsorozatot.

A kimenet egyetlen sorában adjuk meg, hogy hány kiegyensúlyozott rész van.

A keresett $\displaystyle x$, $\displaystyle y$ párosok: $\displaystyle (1,2)$, $\displaystyle (2,3)$, $\displaystyle (3,4)$, $\displaystyle (4,5)$, $\displaystyle (1,4)$, $\displaystyle (2,5)$.

Korlátok: $\displaystyle 1\le N\le {10}^{5}$.

Értékelés: a pontok 50%-a kapható, ha $\displaystyle N\le 1000$.

Beküldendő egy is53.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2021. május 17-én LEJÁRT.

Minden 0-t írjunk át -1-re. Ekkor a kérdés, hogy hány olyan intervallum van, ahol az összeg 0.

Naívan a megoldás köbös,

Prefix összegeket számolva négyzetes,

Az előlő megoldás gyorsítható lineáris futási időre Varga Péter által leírt módon:

VargaPeter.docx

Statisztika:

13 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Kovács Alex, Melján Dávid Gergő, Tóth 057 Bálint, Varga 256 Péter.
9 pontot kapott:	Ürmössy Dorottya.
6 pontot kapott:	4 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2021. áprilisi informatika feladatai