Fie o matrice de dimensiuni x date. Aceasta se construiește astfel:
Se pornește de la o matrice de dimensiune x având ca elemente litere mici ale alfabetului englez. Matricea de dimensiune x se formează din patru submatrice de dimensiune x și se obține din matricea de dimensiune x , astfel:
- Submatricea din stânga sus va fi
- Submatricea din dreapta sus va fi formată din , crescând fiecare element cu (
a
devined
,b
devinee
,z
devinec
) - Submatricea din stânga jos va fi formată din , scăzând fiecare element cu (
a
devinev
,b
devinex
, \dots,z
devineu
) - Submatricea din dreapta jos este rotită cu de grade
- De exemplu dacă de dimensiune x are valoarea:
De exemplu dacă de dimensiune x are valoarea:
Atunci matricea de dimensiune x are valoarea:
Cerința
Se dau triplete , cu semnificația: pe poziția se află litera . Care este numărul maxim de triplete care se pot selecta astfel încât toate să fie adevărate?
Exemplu:
(1, 2, b)
(2, 3, f)
(2, 1, d)
(1, 2, z)
(4, 1, y)
(4, 4, a)
(3, 3, d)
Răspunsul este (prima, a doua și ultimele trei). De exemplu, dacă matricea de pornire este:
Atunci matricea va fi:
Date de intrare
Fișierul de intrare expandmat.in
conține pe prima linie numerele și , despărțite printr-un spațiu, cu semnificaţia de mai sus, iar pe fiecare din următoarele linii va fi câte un triplet de numere cu semnificațiile din enunț.
Date de ieșire
Fișierul de ieșire expandmat.out
va conține pe prima linie numărul maxim de triplete care se pot selecta astfel încât toate să fie adevărate.
Restricții și precizări
- Matricea este indexată de la .
# | Punctaj | Restricții |
---|---|---|
1 | 21 | matricea inițială conține doar literele a ,b ,c ,d şi |
2 | 19 | matricea inițială conține doar literele a ,b ,c ,d şi |
3 | 13 | literele matricei inițiale sunt egale |
4 | 21 | în matricea inițială literele de pe aceeași linie sunt egale |
5 | 9 | se garantează că răspunsul este cel puțin |
6 | 17 | Fără restricții suplimentare |
Exemplul 1
expandmat.in
2 7
1 2 b
2 3 f
2 1 d
1 2 z
4 1 y
4 4 a
3 3 d
expandmat.out
5
Explicație
N = 2 și Q = 7.
Cele triplete care se pot alege sunt:
(1, 2, b)
(2, 3, f)
(4, 1, y)
(4, 4, a)
(3, 3, d)
Dacă matricea inițială este:
Atunci matricea finală este:
Această matrice satisface toate cele triplete.