Rezolvare PBinfo #3764

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 orice i = 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.