Fișierul intrare/ieșire qmatrix.in, qmatrix.out Sursă infoarena, preOJI 2016, clasa a 9-a
Autor Dan Pracsiu Adăugată de avatar isav_costin 10C Vlad Costin isav_costin
Timp de execuție pe test 1 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii