Nicoleta este pasionată de cifre. Fiind într-o bibliotecă, s-a întrebat dacă luând n
cărţi din bibliotecă, cu cifrele cu care sunt numerotate paginile celor n
cărţi, poate forma un număr care citit de la stânga la dreapta este identic cu cel citit de la dreapta la stânga (un palindrom)
.
Cerința
Cunoscându-se numrul n
de cărţi şi numărul p
de pagini ale fiecărei cărţi să se determine dacă cu cifrele cu care sunt numerotate paginile cărţilor se poate forma un palindrom.
Date de intrare
Fişierul de intrare pagini.in
conţine pe prima linie numărul de teste T
. Fiecare dintre următoarele T
linii conţin câte n+1
numere naturale; primul dintre acestea reprezintă numărul de cărţi n
, următoarele n
valori reprezintă numărul p
de pagini pentru fiecare carte dintre cele n
.
Date de ieșire
Fişierul de ieşire pagini.out
conţine T
linii. Pe fiecare linie se va afla mesajul DA
dacă cu cifrele cu care sunt numerotate paginile cărţilor de pe linia respectivă din fişierul de intrare se poate forma un palindrom sau mesajul NU
în caz contrar.
Restricții și precizări
1 <= T <= 3
1 ≤ n ≤ 10.000
10 ≤ p ≤ 1000
- Mesajele
DA/NU
sunt scrise cu majuscule - Numerotarea paginilor începe pentru fiecare carte de la
1
Exemplul 1:
pagini.in
3 1 19 2 19 19 1 18
pagini.out
DA DA NU
Exemplul 2:
pagini.in
1 6 11 73 243 53 33 604
pagini.out
NU
Exemplul 3:
pagini.in
2 5 199 929 325 299 325 6 11 73 243 53 33 604
pagini.out
NU NU
#include <bits/stdc++.h> using namespace std; ifstream cin("pagini.in"); ofstream cout("pagini.out"); int main() { int x , n , p; cin >> p; for(int i = 0 ; i < p ; ++i) { long long ok = 1 , cnt = 0 , f[10]={0}; cin >> n; for(int j = 0 ; j < n ; ++j) { cin >> x; for(int k = 1 ; k <= x ; ++k) { int aux = k; while(aux != 0) { f[aux%10]++; aux /= 10; } } } for(int j = 0 ; j < 10 ; ++j) { if(f[j]%2!=0 && cnt==0) cnt++; else if(f[j]%2!=0 && cnt==1)ok = 0; } if(ok)cout << "DA" << endl; else cout << "NU" << endl; } }