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. 37. feladat (2019. szeptember)

I/S. 37. Béla a titkosszolgálatnak dolgozik, feladata egy szuperintelligens idegen civilizáció által küldött üzenetek feldolgozása. Az üzentek \(\displaystyle N\) hosszú jelsorozatok, melyek `0'-t és `1'-et tartalmaznak. Mivel ez egy nem túl izgalmas munka, Béla úgy döntött megkeresi a számára érdekes részeket az üzenetben. Bélának az üzenet azon részei érdekesek, melyek `00'-val kezdődnek és `11'-gyel végződnek. Segítsünk Bélának megmondani, hogy mennyi érdekes része van az üzenetnek, vagyis hány olyan \(\displaystyle x\); \(\displaystyle y\) (\(\displaystyle x< y\)) számpár van, amelynél az üzenet \(\displaystyle x\)-edik és \(\displaystyle (x+1)\)-edik helyén `0', \(\displaystyle y\)-adik és \(\displaystyle (y+1)\)-edik helyén `1' szerepel.

Standard bemenet: az első és egyetlen sora tartalmazza az üzenetet.

Standard kimenet: az első sora tartalmazza az érdekes részek számát.

Korlátok: \(\displaystyle 1\le N\le {10}^{5}\), időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható \(\displaystyle N\le {10}^{4}\) esetén.

Példa:

BemenetKimenet
100010110114

Beküldendő egy is37.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ő 2019. október 10-én LEJÁRT.


Statisztika:

Az I/S. 37. feladat értékelése még nem fejeződött be.


A KöMaL 2019. szeptemberi informatika feladatai