Lista de probleme 888

Se dă o matrice pătratică cu n lini şi n coloane şi elemente numere întregi. Determinaţi cea mai mare sumă a n elemente din matrice, adunând câte un element de pe fiecare linie a matricei.

Se consideră un graf cu N noduri numerotate de la 1 la N și M operații de trei tipuri:

• 1 x y – se adaugă în graf muchia (x, y). Dacă muchia există deja, operația nu se efectuează
• 2 x y – întrebare: nodurile x și y se află sau nu în aceeași componentă conexă?
• 3 – care este numărul maxim de noduri dintr-o componentă conexă?

Trebuie să răspundeți la toate întrebările de tip 2 și 3.

• orice cub se așează peste un altul ce are latura mai mare sau egală cu a lui;
• să nu existe două cuburi consecutive de aceeași culoare;

Se consideră un cuvânt C format din litere mici, nu neapărat distincte. Să se afișeze în ordine lexicografică toate cuvintele distincte formate cu exact aceleași caractere ca și C.

Avem la dispoziție oricâți căței și oricâte pisici, câte așezări ale acestora în linie dreaptă de lungime n există astfel incât să nu avem o pisică între 2 căței și configurația să înceapă cu un câine și să se termine cu o pisică? Răspunsul se afișează modulo \(10^9+7\).

Într-o clasă sunt n elevi, numerotați de la 1 la n, iar unii dintre ei pot cunoaște numerele de telefon ale altor elevi. Dirigintele dorește să-i anunțe pe elevi despre un eveniment deosebit și pentru aceasta vrea să transmită informația unui singur elev din clasă, urmând ca acesta să-și anunțe colegii cărora le cunoaște numărul de telefon, aceștia să-și anunțe colegii cărora le cunosc numărul de telefon etc, astfel încât toți elevii să afle informația respectivă.

Determinați care sunt elevii din clasă care pot fi anunțați inițial astfel încât, toți elevii să fie în cele din urmă informați.

Considerăm un ansamblu format din n roți dințate, numerotate de la 1 la n. Fiecare roată se poate roti spre dreapta sau spre stânga. Dacă o roată se rotește spre dreapta, toate roțile pe care le angrenează se vor roti spre stânga, și invers.
Una dintre roți este conectată la un motor și se va roti spre dreapta, iar toate roțile din ansamblu se vor roti în mod corespunzător. Ansamblul este construit astfel încât toate roțile vor fi angrenate și fiecare roată va fi angrenată de o unică altă roată.

Dându-se numărul de roți n, numărul de ordine x al roții conectate la motor și perechile de roți conectate între ele, să se determine sensul de rotație al fiecărei roți.

În judeţul lui Dorel sunt n localităţi legate între ele prin m drumuri. Dorel e interesat să afle în câte moduri se pot alege n-1 drumuri din cele m date, astfel încât folosind aceste drumuri să se poată ajunge de la orice localitate la oricare alta.

Se dau două șiruri de caractere, litere mici ale alfabetului englez. Să se afișeze cel mai lung subșir comun al lor.

La balul din acest an participă n băieți și n fete, numerotați de la 1 la n. Compatibilitățile dintre aceștia pot fi reprezentate sub forma unui graf bipartit. Fie mat matricea de adiacentă. Atunci, băiatul i se poate cupla cu fata j doar dacă sunt compatibili, adică mat[i][j] = 1. Aflați numărul de moduri de a forma cele n cupluri.