expandmat

Time limit: 0.1s Memory limit: 256MB Input: expandmat.in Output: expandmat.out

Fie o matrice AA de dimensiuni 2N2^N x 2N2^N date. Aceasta se construiește astfel:
Se pornește de la o matrice de dimensiune 22 x 22 având ca elemente litere mici ale alfabetului englez. Matricea BB de dimensiune 2k2^k x 2k2^k se formează din patru submatrice de dimensiune 2k12^{k-1} x 2k12^{k-1} și se obține din matricea CC de dimensiune 2k12^{k-1} x 2k12^{k-1}, astfel:

  • Submatricea din stânga sus va fi CC
  • Submatricea din dreapta sus va fi formată din CC, crescând fiecare element cu 33 (a devine d, b devine e, z devine c)
  • Submatricea din stânga jos va fi formată din CC, scăzând fiecare element cu 44 (a devine v, b devine x, \dots, z devine u)
  • Submatricea din dreapta jos este CC rotită cu 180180 de grade
  • De exemplu dacă CC de dimensiune 22 x 22 are valoarea:

De exemplu dacă CC de dimensiune 22 x 22 are valoarea:

Atunci matricea BB de dimensiune 222^2 x 222^2 are valoarea:

Cerința

Se dau QQ triplete (i,j,L)(i, j, L), cu semnificația: pe poziția Ai,jA{i,j} se află litera LL. Care este numărul maxim de triplete care se pot selecta astfel încât toate să fie adevărate?

Exemplu:
N=2,Q=7N = 2, Q = 7
(1, 2, b)
(2, 3, f)
(2, 1, d)
(1, 2, z)
(4, 1, y)
(4, 4, a)
(3, 3, d)

Răspunsul este 55 (prima, a doua și ultimele trei). De exemplu, dacă matricea de pornire este:

  • (abcd)\begin{pmatrix} a & b \\ c & d \end{pmatrix}

Atunci matricea AA va fi:

  • (abdecdfgvxdcyzba)\begin{pmatrix} a & b & d & e \\ c & d & f & g \\ v & x & d & c \\ y & z & b & a \end{pmatrix}

Date de intrare

Fișierul de intrare expandmat.in conține pe prima linie numerele NN și QQ, despărțite printr-un spațiu, cu semnificaţia de mai sus, iar pe fiecare din următoarele QQ linii va fi câte un triplet de numere i,j,Li, j, L 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

  • 1N601 \leq N \leq 60
  • 1Q100 0001 \leq Q \leq 100 \ 000
  • Matricea este indexată de la 11.
# Punctaj Restricții
1 21 matricea inițială conține doar literele a,b,c,d şi N8,Q100N \leq 8, Q \leq 100
2 19 matricea inițială conține doar literele a,b,c,d şi N60,Q300N \leq 60, Q \leq 300
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 Q/2Q/2
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 55 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:

  • (abcd)\begin{pmatrix} a & b \\ c & d \end{pmatrix}

Atunci matricea finală este:

  • (abdecdfgvxdcyzba)\begin{pmatrix} a & b & d & e \\ c & d & f & g \\ v & x & d & c \\ y & z & b & a \end{pmatrix}

Această matrice satisface toate cele 55 triplete.

Log in or sign up to be able to send submissions!