Lista de probleme 3

Fie un șir de caractere S format din litere mici ale alfabetului englez, indexat de la 0. Aflați pentru fiecare i ≥ 2 cel mai mare l pentru care există 0 < j < i − l + 1 unde stringurile \( [{s}_{0}{s}_{1}…{s}_{l-1}] \), \( [{s}_{j}{s}_{j+1}…{s}_{j+l-1}] \) și \( [{s}_{i-l+1}{s}_{i-l+2}…{s}_{i}] \) sunt egale. Dacă nu există un astfel de l, afișați valoarea 0.

Satul Binăreni se află în pericol în urma incendiilor provocate în ultima lună. Acesta este reprezentat printr-o matrice binară cu N linii și M coloane. Toate celulele care au luat foc sunt reprezentate prin valoarea 0. Toate celulele în care nu este produs un incendiu, reprezentate prin valori de 1, conțin, inițial, câte o casă a unui sătean. Gosu, cel mai renumit pompier din sat, își dorește să salveze toate casele care nu se află în celule "safe", folosindu-și superputerea: acesta poate stinge o singură dată focul din toate celulele care au luat foc pe o linie x și toate celulele care au luat foc pe o coloană y, plasându-se la intersecția acestora, în celula (x, y). Acesta se poate plasa atât pe o celulă cu incendiu, cât și pe o celulă care conține o casă. Având în vedere că Gosu își poate folosi superputerea o singură dată, aflați toate perechile de coordonate (x, y) posibile pe care se poate plasa acesta, astfel încât să salveze toate casele care sunt în pericol.

Dându-se o listă conținând KDA-urilor celor N prieteni ai lui Gigel și mărimea unei echipe k, Gigel dorește să afle care este qE-ul celei mai neechilibrate echipe. Astfel el calculează qE-ul tuturor echipelor posibile (\(\frac{N!}{k!(N-k)!}\) la număr) și apoi alege qE-ul maxim posibil.