Lista de probleme 3

În Sosmania sunt N fabrici de sos, numerotate de la 1 la N. Aceste fabrici folosesc pentru prepararea sosului o mulțime proprie de ingrediente. La nivel național, sunt acceptate M tipuri de ingrediente, numerotate de la 1 la M. Se consideră că o secvență formată din două sau mai multe fabrici este compatibilă, dacă toate fabricile din secvență folosesc cel puțin un ingredient comun. O secvență de fabrici (i, j) (1 ≤ i < j ≤ n) este formată din toate fabricile care au numărul de ordine x astfel încât i ≤ x ≤ j. Cunoscându-se N, M și mulțimea ingredientelor folosite de fiecare dintre cele N fabrici, să se determine numărul de subsecvențe compatibile.

Costin are o matrice pătratică A cu N linii (numerotate de sus în jos de la 1 la N) și N coloane (numerotate de la stânga la dreapta de la 1 la N). Inițial toate elementele matricei sunt egale cu 0. Scrieți un program care, cunoscând N, precum și o succesiune de M operații, afișează matricea rezultată în urma efectuării în ordine a operațiilor din succesiune.

O pereche de șiruri de caractere S și T, formate doar din literele A, B și C, este egalabilă dacă șirurile pot deveni egale după o transfomare constând din aplicarea unei succesiuni formate din 0 sau mai multe operații. O operație constă din inserarea sau ștergerea din unul dintre șiruri a uneia dintre subsecvențele: AAA, BBB, CCC, ABC sau BAC. Atât inserarea, cât și ștergerea se pot realiza de pe orice poziție. În urma unei operații este posibil ca șirul rezultat să devină vid. Pentru o succesiune dată de perechi de șiruri, să se determine, pentru fiecare pereche, dacă este egalabilă.