Fișierul intrare/ieșire | qmatrix.in, qmatrix.out | Sursă | infoarena, preOJI 2016, clasa a 9-a |
---|---|---|---|
Autor | Dan Pracsiu | Adăugată de | 10C Vlad Costin • isav_costin |
Timp de execuție pe test | 1 sec | Limită de memorie | 4096 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Qmatrix (clasa a 9-a)
Se dă o matrice A cu N linii și N coloane. Liniile și coloanele sunt numerotate de la 1 la N. Matricea A memorează doar cifre. Elementele matricei se generează astfel: vi se dau valorile X și Y, apoi se constuiește un șir v în care:
v[ 1 ] = X, v[ 2 ] = Y, v[k] = A[i][j] = (v[k-2] * i + v[k-1]* j + 1) % 10, 1 <= i, j <= N , k = N*(i-1) + j + 2
Trebuie să răspundeți la Q întrebări de forma:
- L k p – pe ce linie se află a k-a cifră egală cu p (unde p este o cifră) dacă am parcurge matricea linie cu linie
- C k p – pe ce coloană se află al k-lea număr p (unde p este o cifră) dacă am parcurge matricea coloana cu coloana
Date de intrare
Fișierul de intrare qmatrix.in conține pe prima linie numerele N, X, Y, Q. Pe următoarele Q linii se află trei valori ch k p, unde ch poate fi unul din caracterele L sau C.
Date de ieșire
Fișierul de ieșire qmatrix.out va conține exact Q linii. Pe fiecare linie se află un singur număr natural care reprezintă răspunsul la câte o întrebare.
Restricții
- 2 ≤ N ≤ 4000
- 1 ≤ Q ≤ 100 000
- 1 ≤ X,Y ≤ 10 000
- Pentru toate întrebările, 0 ≤ p ≤ 9 și 1 ≤ k ≤ 1 000 000 000
- Dacă în matrice se află mai puțin de k valori egale cu p, atunci veți afișa valoarea 0.
Exemplu
qmatrix.in | qmatrix.out |
---|---|
6 121 97 3 C 3 9 L 5 8 C 200 9 |
3 6 0 |
Explicație
Matricea generată este
9 6 8 9 4 4
3 5 2 9 0 9
0 8 5 5 1 2
7 3 8 5 8 9
0 6 9 7 1 2
9 1 8 9 4 9
Prima întrebare: a treia cifră 9 este pe coloana 3
A doua întrebare: a cincea cifră 8 se află pe linia 6
A treia întrebare: în matrice se află mai puțin de 200 de valori de 9, deci se afișează 0.