Prin concatenarea a două numere naturale A
și B
se pot obține numerele naturale AB
și BA
. De exemplu, dacă A = 8
și B = 8
, atunci prin concatenare se poate obține numărul 88
, iar dacă A = 7
și B = 17
, atunci prin concatenare se pot obține numerele 717
și respectiv 177
.
Cerința
Scrieți un program care să rezolve următoarele două cerințe:
1. Pentru un număr natural nenul A
dat, să se calculeze P1
, numărul numerelor naturale distincte X
, unde 1 ≤ X ≤ 10 * A
, astfel încât X
concatenat cu A
sau A
concatenat cu X
este palindrom.
2. Date fiind numărul natural N
și un șir de N
numere naturale v[1]
, v[2]
, …, v[N]
, să se calculeze P2
, numărul de numere palindrom distincte care se pot obține prin concatenarea numerelor din perechile (v[i], v[j])
, unde 1 ≤ i ≤ N
și 1 ≤ j ≤ N
.
Date de intrare
Fișierul de intrare cat2pal.in
conține pe prima linie numărul natural C
, reprezentând cerința care urmează să fie rezolvată (1
sau 2
). Dacă C = 1
, atunci pe linia a doua se află numărul natural A
. Dacă C = 2
, atunci pe linia a doua se află numărul natural N
și pe linia a treia se află N
numere naturale separate prin spațiu, reprezentând șirul v
.
Date de ieșire
Fișierul de ieșire cat2pal.out
va conține o singură linie pe care se va scrie un singur număr natural, reprezentând rezultatul pentru cerința C
din fișierul de intrare.
Restricții și precizări
1 ≤ A < 100.000.000
1 ≤ N ≤ 10.000
0 ≤ v[i] < 100.000
; pentru oricei = 1..N
- Pentru cazul
C = 2
, trebuie luate în considerare și perechile(v[i], v[i])
, adică concatenarea unui element cu el însuși.
Exemplul 1:
cat2pal.in
1 2
cat2pal.out
3
Explicație
C = 1
, A = 2
, numerele X
care concatenate cu A
produc numere palindrom sunt 2
, 12
și 20
, deci P1 = 3
.
Exemplul 2:
cat2pal.in
2 3 2 12 21
cat2pal.out
4
Explicație
C = 2
, N = 3
, v = {2, 12, 21}
, numerele palindrom distincte care pot fi obținute sunt 22
, 212
, 1221
, 2112
, deci P2 = 4
.