cat2pal

Time limit: 0.05s Memory limit: 64MB Input: cat2pal.in Output: cat2pal.out

Prin concatenarea a două numere naturale AA și BB se pot obține numerele naturale ABAB și BABA. De exemplu, dacă A=8A = 8 și B=8B = 8, atunci prin concatenare se poate obține numărul 8888, iar dacă A=7A = 7 și B=17B = 17, atunci prin concatenare se pot obține numerele 717717 și respectiv 177177.

Cerință

Scrieți un program care să rezolve următoarele două cerințe:

  1. Pentru un număr natural nenul AA dat, să se calculeze P1P1, numărul numerelor naturale distincte XX, unde 1X10A1 \leq X \leq 10 * A, astfel încât XX concatenat cu AA sau AA concatenat cu XX este palindrom.
  2. Date fiind numărul natural NN și un șir de NN numere naturale v[1],v[2],,v[N]v[1], v[2], \dots, v[N], să se calculeze P2P2, numărul de numere palindrom distincte care se pot obține prin concatenarea numerelor din perechile (v[i],v[j])(v[i], v[j]), unde 1iN1 \leq i \leq N și 1jN1 \leq j \leq N.

Date de intrare

Fișierul de intrare cat2pal.in conține pe prima linie numărul natural CC, reprezentând cerința care urmează să fie rezolvată (11 sau 22). Dacă C=1C = 1, atunci pe linia a doua se află numărul natural AA. Dacă C=2C = 2, atunci pe linia a doua se află numărul natural NN și pe linia a treia se află NN numere naturale separate prin spațiu, reprezentând șirul vv.

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 CC din fișierul de intrare.

Restricții și precizări

  • 1A<100 000 0001 \leq A \lt 100 \ 000 \ 000
  • 1N10 0001 \leq N \leq 10 \ 000
  • 0v[i]<100 0000 \leq v[i] \lt 100 \ 000; pentru orice i=1Ni = 1 \dots N
  • Pentru cazul C=2C = 2, trebuie luate în considerare și perechile (v[i],v[i])(v[i], v[i]), adică concatenarea unui element cu el însuși.
  • Pentru teste valorând 2020 de puncte: C=1C = 1 și A<100 000A < 100 \ 000
  • Pentru alte teste valorând 3030 de puncte: C=1C = 1 și nu există restricții suplimentare.
  • Pentru teste valorând 1515 puncte: C=2C = 2 și N1 000N ≤ 1 \ 000
  • Pentru teste valorând 3535 puncte: C=2C = 2 și nu există restricții suplimentare.

Exemplul 1

cat2pal.in

1 
2

cat2pal.out

3

Explicație

C=1C = 1, A=2A = 2, numerele XX care concatenate cu AA produc numere palindrom sunt 22, 1212 și 2020, deci P1=3P1 = 3.

Exemplul 2

cat2pal.in

2
3
2 12 21

cat2pal.out

4

Explicație

C=2C = 2, N=3N = 3, v=2,12,21v = {2, 12, 21}, numerele palindrom distincte care pot fi obținute sunt 2222, 212212, 12211221, 21122112, deci P2=4P2 = 4.

Log in or sign up to be able to send submissions!