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 S. 145. feladat (2020. szeptember)

S. 145. Van egy szótárunk \(\displaystyle N\) db szóval. Azt szeretnénk tudni, hányféleképpen tudjuk a szótárból választott szavakat a dominóhoz hasonlóan összeilleszteni úgy, hogy azok \(\displaystyle K\) betű hosszan átfedjék egymást. Tehát a kérdés: hány olyan \(\displaystyle (i,j)\) rendezett számpár (\(\displaystyle 1\le i,j\le N\)) van, melyre az \(\displaystyle i\)-edik szó utolsó \(\displaystyle K\) betűjéből alkotott sorozat megegyezik a \(\displaystyle j\)-edik szó első \(\displaystyle K\) betűjéből alkotott sorozattal.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) és \(\displaystyle K\) számokat. A következő \(\displaystyle N\) sor mindegyike egy, az angol ABC kisbetűiből álló (nem feltétlenül értelmes) szót tartalmaz.

Kimenet: a megfelelő összeillesztések, vagyis számpárok száma.

Példa:

Korlátok: \(\displaystyle 2\le N\le {10}^{5}\), \(\displaystyle 1\le K\le 100\), minden szó legalább \(\displaystyle K\) és legfeljebb 100 betű hosszú. Időkorlát: 1 mp.

Értékelés: a pontok 30%-a kapható \(\displaystyle K=1\) esetén. A pontok további 30%-a kapható, ha \(\displaystyle N\le 100\).

Beküldendő egy s145.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ő 2020. október 15-én LEJÁRT.


Statisztika:

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


A KöMaL 2020. szeptemberi informatika feladatai