Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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.

Bemenet (a / jel sortörést jelent) Kimenet
5 /101016

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.


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