 |
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 /10101 | 6 |
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:
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