Prin concatenarea a două numere naturale și se pot obține numerele naturale și . De exemplu, dacă și , atunci prin concatenare se poate obține numărul , iar dacă și , atunci prin concatenare se pot obține numerele și respectiv .
Cerință
Scrieți un program care să rezolve următoarele două cerințe:
- Pentru un număr natural nenul dat, să se calculeze , numărul numerelor naturale distincte , unde , astfel încât concatenat cu sau concatenat cu este palindrom.
- Date fiind numărul natural și un șir de numere naturale , să se calculeze , numărul de numere palindrom distincte care se pot obține prin concatenarea numerelor din perechile , unde și .
Date de intrare
Fișierul de intrare cat2pal.in
conține pe prima linie numărul natural , reprezentând cerința care urmează să fie rezolvată ( sau ). Dacă , atunci pe linia a doua se află numărul natural . Dacă , atunci pe linia a doua se află numărul natural și pe linia a treia se află numere naturale separate prin spațiu, reprezentând șirul .
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 din fișierul de intrare.
Restricții și precizări
- ; pentru orice
- Pentru cazul , trebuie luate în considerare și perechile , adică concatenarea unui element cu el însuși.
- Pentru teste valorând de puncte: și
- Pentru alte teste valorând de puncte: și nu există restricții suplimentare.
- Pentru teste valorând puncte: și
- Pentru teste valorând puncte: și nu există restricții suplimentare.
Exemplul 1
cat2pal.in
1
2
cat2pal.out
3
Explicație
, , numerele care concatenate cu produc numere palindrom sunt , și , deci .
Exemplul 2
cat2pal.in
2
3
2 12 21
cat2pal.out
4
Explicație
, , , numerele palindrom distincte care pot fi obținute sunt , , , , deci .