Matrix Masterclass

Time limit: 0.5s Memory limit: 64MB Input: matrix.in Output: matrix.out

Andrei este gata de o nouă zi de liceu. Înainte de a intra la ore, el îşi dă seama de faptul că a avut loc o rearanjare a claselor. Noua structură a liceului privită de sus în jos are forma unei matrici pătratice, cu NN linii şi NN coloane, fiecare pătrăţel reprezentând o clasă. Deoarece elevii nu au fost de acord cu noua aranjare a claselor (din motive bine cunoscute), mai nou, acolo vor învăţa furnici. Având în vedere rigorile impuse de liceu, Andrei primeşte de la conducerea şcolii o foaie sub formă de matrice în care pentru fiecare coordonată (i,j)(i, j), unde ii este linia, iar jj coloana, este trecut MijM_{ij}, numărul de furnici care vor urma să înveţe în clasa de aceleaşi coordonate.
Cum furnicile doresc să afle cât mai mult despre noul lor liceu, iar lui Andrei îi este interzis să le comunice repartizarea în forma ei actuală, va trebui ca voi să ajutaţi furnicile în noul an şcolar!

Cerință

Problema este formată din 44 cerinţe:

  1. Furnicile sunt impresionate de spirale, aşa că ele doresc să afişaţi numărul de furnici din fiecare clasă, având în vedere că parcurgerea lor se va face în spirală, începând de la coordonata (1,1)(1, 1) şi prima direcţie fiind la dreapta. (vezi exemplul 11)
  2. Furnicile devin obsedate de spirale, aşa că ele doresc să afişaţi numărul de furnici din fiecare clasă, fiind garantat faptul că N=2kN=2^k, unde kk este număr natural şi având în vedere următoarea parcurgere: La fiecare pas se va împărţi matricea în 4 cadrane. Prima oara se va parcurge cel din stânga-sus, apoi cel din dreapta-sus, urmat de cel din dreapta-jos şi la final, cel din stânga-jos. Parcurgerea fiecărui cadran se va face asemănător cu parcurgerea matricei întregi, împărţindu-se şi acesta în 44 cadrane, parcurse în aceaşi ordine. Împărţirea se opreşte în momentul în care rămânem cu o singură clasă în cadran. (vezi exemplul 22)
  3. Furnicile sunt impresionate de numerele prime, aşa că ele doresc să afişaţi numărul de clase care au un număr prim de furnici şi coordonatele acestora. (vezi exemplul 33)
  4. Furnicile devin obsedate de numerele prime, aşa că ele doresc să pună QQ întrebări de forma: câte clase cu numere prime de furnici există în submatricea care are colţul stânga-sus în poziţia (L1,C1)(L_1, C_1) şi colţul dreapta-jos în poziţia (L2,C2)(L_2, C_2). Răspundeţi la aceste întrebări. (vezi exemplul 44)

Date de intrare

Pe prima linie a fișierului de intrare matrix.in se găsește numărul cerinței C{1,2,3,4}C \in \{1, 2, 3, 4\}.
Pe a doua linie se găseşte numărul natural NN, dimensiunea matricei.
Pe următoarele NN linii se găsesc NN numere naturale, reprezentând numărul de furnici din clasele de pe linia respectivă.
Doar dacă C=4C=4, atunci pe următoarea linie se va găsi QQ, numărul de întrebări, urmată de alte QQ linii pe care se vor găsi câte 44 numere naturale, în ordine: L1L_1 , C1C_1 , L2L_2 , C2C_2.

Date de ieșire

  • Afișarea se va face în fișierul de ieșire matrix.out.
  • Dacă C=1C=1, atunci se vor afișa numărul de furnici din fiecare clasă, în ordinea parcurgerii de la cerința 1, cu spații între ele.
  • Dacă C=2C=2, atunci se vor afișa numărul de furnici din fiecare clasă, în ordinea parcurgerii de la cerința 2, cu spații între ele.
  • Dacă C=3C=3, atunci se va afișa pe prima linie numărul de clase care au un număr prim de furnici, iar pe fiecare dintre liniile următoare se vor afișa 22 numere: coordonata liniei clasei, respectiv coordonata coloanei clasei, despărțite prin spațiu, pentru fiecare clasă care respectă condiția de a avea un număr prim de furnici. Clasele vor fi ordonate după linie, iar dacă sunt mai multe clase care respectă condiţia de mai sus, după coloană.
  • Dacă C=4C=4, atunci se vor afișa QQ linii, unde pe linia qq , 1qQ1\le q\le Q se va afișa răspunsul la a qq-a întrebare.

Restricții și precizări

  • C{1,2,3,4}C \in \{1, 2, 3, 4\};
  • 1N1 0001 \le N \le 1 \ 000;
  • Pentru C=2C=2, N=2k,kN=2^k, k număr natural;
  • 1Q1 000 0001 \le Q \le 1 \ 000 \ 000;
  • 1i,jN1 \le i, j \le N;
  • 0Mij1 000 0000 \le M_{ij} \le 1 \ 000 \ 000;
  • 1L1L2N1 \le L_1 \le L_2 \le N;
  • 1C1C2N1 \le C_1 \le C_2 \le N.
# Punctaj Restricții
1 25 C=1C=1
2 25 C=2C=2
3 5 C=3C=3, Mij10M_{ij} \le 10
4 20 C=3C=3
5 15 C=4C=4, N,Q100N, Q \le 100
6 10 C=4C=4

Exemplul 1

matrix.in

1
4
7 10 98 52
2 36 80 13
61 79 9 0
21 1 43 45

matrix.out

7 10 98 52 13 0 45 43 1 21 61 2 36 80 9 79

Explicație

Numerele din matrice se vor afișa în spirală, în ordinea săgeților din figura de mai sus.

Exemplul 2

matrix.in

2
4
7 10 98 52
2 36 80 13
61 79 9 0
21 1 43 45

matrix.out

7 10 36 2 98 52 13 80 9 0 45 43 61 79 1 21

Explicație

Matricea inițială este împărțită în 44 cadrane: (710236),(98528013),(904345),(6179211)\begin{pmatrix} 7 & 10\\ 2 & 36 \end{pmatrix}, \begin{pmatrix} 98 & 52\\ 80 & 13 \end{pmatrix}, \begin{pmatrix} 9 & 0\\ 43 & 45 \end{pmatrix}, \begin{pmatrix} 61 & 79\\ 21 & 1 \end{pmatrix}, care la rândul lor sunt împărțite din nou în 44 cadrane, în ordinea parcurgerii de la cerința 2, rezultând astfel răspunsul dat.

Exemplul 3

matrix.in

3
4
7 10 98 52
2 36 80 13
61 79 9 0
21 1 43 45

matrix.out

6
1 1
2 1
2 4
3 1
3 2
4 3

Explicație

În matrice se află 66 numere prime: 7,2,13,61,79,437, 2, 13, 61, 79, 43, ordonate după linie și apoi după coloană

Exemplul 4

matrix.in

4
4
7 10 98 52
2 36 80 13
61 79 9 0
21 1 43 45
5
1 1 2 3
3 2 3 2
1 4 4 4
1 2 2 3
3 1 4 3

matrix.out

2
1
1
0
3

Explicație

  • Pentru prima întrebare, submatricea analizată este (7109823680)\begin{pmatrix}7 & 10 & 98\\2 & 36 & 80\end{pmatrix}, care are 22 numere prime: 7,27, 2.
  • Pentru a doua întrebare, submatricea analizată este un singur element, și anume 7979, care este prim.
  • Pentru a treia întrebare, submatricea analizată este (5213045)\begin{pmatrix}52\\13\\0\\45\end{pmatrix}, care are un singur număr prim: 1313.
  • Pentru a patra întrebare, submatricea analizată este (10983680)\begin{pmatrix}10 & 98\\36 & 80\end{pmatrix}, care nu are niciun număr prim.
  • Pentru a cincea întrebare, submatricea analizată este (6179921143)\begin{pmatrix}61 & 79 & 9\\21 & 1 & 43\end{pmatrix}, care are 33 numere prime: 61,79,4361, 79, 43.

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