Se dă o matrice cu n linii şi m coloane, în care liniile sunt sortate lexicografic crescător. Se dau q întrebări de forma: este şirul A, cu m elemente, o linie a matricei citite?
Date de intrare
Pe prima linie se vor afla numerele n şi m. Pe următoarele n linii se vor afla câte m numere naturale, reprezentând elementele matricei. Pe linia următoare se va afla numărul q, iar pe următoarele q linii se vor afla câte m numere reprezentând şirurile cărora trebuie să le determinăm prezenţa în matricea dată.
Date de ieşire
Pe ecran se vor afişa q mesaje, fiecare pe câte o linie, reprezentând răspunsurile la întrebări. Dacă şirul citit la întrebarea i se află în matrice, atunci se va afişa "DA". În caz contrar, se va afişa "NU".
Restricţii şi precizări
1 ≤ n, m, q ≤ 1 000
1 ≤ x ≤ 1 000, unde x este un element din matricea dată sau din şirurile din întrebări
Fie două șiruri de aceeași lungime,
X
1
X
2
.
.
.
X
k
și
Y
1
Y
2
.
.
.
Y
k
. Șirul
X
se numește mai mic lexicografic decât șirul
Y
dacă
X
i
<
Y
i
în prima poziție i la care Xi și Yi diferă
Exemplu
Date de intrare Date de ieşire
3 3
1 2 3
2 5 6
5 4 3
2
1 2 3 DA
3 2 1 NU
Limbaj C++
Răspunsuri la întrebare
Răspuns:
#include <iostream>
using namespace std;
const int MAX_N = 1000;
const int MAX_M = 1000;
int n, m;
int matrix[MAX_N][MAX_M];
bool isRow(int row[], int m) {
for (int i = 0; i < n; i++) {
bool isEqual = true;
for (int j = 0; j < m; j++) {
if (matrix[i][j] != row[j]) {
isEqual = false;
break;
}
}
if (isEqual) {
return true;
}
}
return false;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> matrix[i][j];
}
}
int q;
cin >> q;
while (q--) {
int row[MAX_M];
for (int i = 0; i < m; i++) {
cin >> row[i];
}
if (isRow(row, m)) {
cout << "DA" << endl;
} else {
cout << "NU" << endl;
}
}
return 0;
}