Lista de probleme 3

Gigel este curios să afle în ce zonă a țării au trăit cei mai mulți dintre strămoșii săi. El reușește să adune informații despre structura genetică a persoanelor din diferite părți ale țării și speră că, prin compararea cu propria structură genetică, să identifice o zonă pătratică în care au trăit cei mai mulți dintre strămoșii săi.

Structura genetică a unei persoane este reprezentată sub forma unei secvențe cu cel mult 20 de caractere (litere mici ale alfabetului englez). O persoană poate fi considerată strămoș a lui Gigel dacă gradul de similaritate dintre secvența corespunzătoare persoanei respective și cea a lui Gigel este mai mare strict decât un număr K, cunoscut.

Gradul de similaritate dintre două secvențe este reprezentat de numărul de caractere comune celor două secvențe. De exemplu pentru secvențele abcdabd și acbdaad gradul de similaritate este 6 (2 caractere a, 2 caractere d, 1 caracter b, 1 caracter c).

Gigel reprezintă harta țării sub forma unui tablou bidimensional cu N linii și M coloane în care fiecare element reprezintă structura genetică a unei persoane din zona respectivă.

Cunoscând N , M , K , structura genetică pentru Gigel și reprezentarea hărții identificată de acesta, să se determine:

1) poziția pe hartă și structura genetică pentru persoana, sau persoanele, pentru care gradul de similaritate cu structura genetică a lui Gigel este maxim;
2) o zonă pătratică, de dimensiune maximă în care toate persoanele ar putea fi strămoși ai lui Gigel.

Pe o foaie dintr-un caiet de matematică de dimensiune N x M (N numărul de linii și M numărul de coloane) sunt completate toate pătrățelele cu X sau 0. Pentru un număr natural K dat, numim șir corect, o secvență de K elemente consecutive pe linie, coloană sau diagonale care au aceeași valoare (X sau 0). Două pătrățele de pe foaie sunt vecine pe aceeași diagonală dacă au un singur colț comun.

Exemplu din figura alăturată, pentru care N=4, M=5, K=3 conține 6 șiruri corecte de X și 5 șiruri corecte de 0.

Cerințe:

1. Se dau numerele naturale N, M și K și o foaie de matematică plină cu X și 0. Determinați câte șiruri corecte de X și câte șiruri corecte de 0 se găsesc pe foaia dată.
2. Se dau Q întrebări de forma A B, în care A este caracterul X sau 0 și B este un număr natural. Determinați în câte moduri putem tăia foaia de matematica vertical pentru a obține în subtabloul din partea stângă exact B șiruri corecte de A. Foia se poate tăia în M -1 variante: după prima coloană, a doua coloană, după a treia coloană, ș.a.m.d, până după penultima coloană.

Determinaţi costul total minim al segmentelor care pot fi alese pentru a obtura orice fascicul de lumină care
ar pleca din origine către un punct cu ordonata pozitivă.