Fișierul intrare/ieșire balba.in, balba.out Sursă OJI 2022 clasa a 9-a
Autor Liviu-Armand Gheorghe Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 1 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Balba (clasa a 9-a)

Punctarea poate diferi față de cea din cadrul concursului OSEPI.

Regele George al VI-lea al Regatului Unit s-a confruntat cu o problemă neobișnuită pentru o persoană care trebuia să țină discursuri: era bâlbâit. Acesta se bâlbâia chiar și când spunea numere. Interesant este faptul că, atunci când spunea un număr, el repeta doar una dintre cifrele acelui număr, imediat după ce pronunța cifra respectivă.

Spre exemplu, numărul 70243 putea fi rostit atunci când se bâlbâia ca 770243 sau ca 700243 sau ca 702243 sau ca 702443 sau ca 702433.

Un palilindrom este un număr natural pentru care există o bâlbâială a regelui care îl transformă într-un palindrom.

Spre exemplu, 25373552 este un palilindrom, pentru că după o bâlbâială poate deveni 255373552, acesta fiind un număr palindrom.

Cerințe

Fiind dat un număr natural nenul X să se determine:

  • Câte numere diferite poate genera X după o bâlbâială și câte numere diferite pot deveni X după o bâlbâială.
  • Cel mai mare număr palilindrom care se poate forma cu cifrele lui X. Nu este obligatoriu să se folosească toate cifrele lui X.

Date de intrare

Pe prima linie a fișierului de intrare balba.in se află numărul C, număr care poate fi 1 sau 2 și reprezintă cerința ce trebuie rezolvată.
Pe cea de-a doua linie se află numărul N, reprezentând numărul de cifre al numărului X.
Pe următoarea linie se află, în ordine, cifrele lui X, separate prin câte un spațiu.

Date de ieșire

Dacă C este 1, fișierul de ieșire balba.out va avea obligatoriu două linii, fiecare linie conținând exact un număr.
Pe prima linie se va scrie un număr natural ce reprezintă câte numere diferite poate genera X după o bâlbâială.
Pe cea de-a doua linie se va scrie un număr natural ce reprezintă câte numere diferite pot deveni X după o bâlbâială.

Dacă C este 2, pe prima linie a fișierului de ieșire balba.out se va scrie cel mai mare număr palilindrom ce se poate crea cu cifrele lui X.

Restricții

  • 1 ≤ N ≤ 105
  • Numărul X este un număr natural nenul cu maxim 100000 de cifre.
  • Un număr palindrom este un număr care are aceeași valoare dacă este citit de la stânga la dreapta sau de la dreapta la stânga.
  • Pentru rezolvarea corectă a cerinței 1 se vor acorda 40 de puncte.
  • Pentru rezolvarea corectă a cerinței 2 se vor acorda 60 de puncte.

Exemplu

balba.in balba.out
1
8
7 0 2 2 4 3 3 3
5
2
1
25
1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7
25
0
2
11
2 4 7 8 1 4 8 7 4 2 1
87442112478
2
7
1 2 3 4 0 0 0
4

Explicație

Pentru exemplul 1, numerele diferite care pot fi generate din 70224333 printr-o bâlbâială sunt: 770224333, 700224333, 702224333, 702244333, 702243333.
Numerele diferite din care 70224333 poate fi generat printr-o bâlbâială sunt: 7024333, 7022433.

Pentru exemplul 2, sunt 25 de numere diferite care pot fi generate din X printr-o bâlbâială, însă X nu poate fi generat de niciun număr printr-o bâlbâială.

Pentru exemplul 3, mai există și alte palilindroame care se pot forma cu cifrele lui 24781487421, însă 87442112478 este cel mai mare dintre ele. Numărul 87442112478 este palilindrom, pentru ca acesta se poate transforma după o bâlbâială într-un număr palindrom, și anume 874421124478.

Pentru exemplul 4, nu se poate forma un palilindrom care să aibă toate cifrele lui X. Astfel, cel mai mare palilindrom care se poate crea folosind cifrele lui X este 4. Numărul 4 este palilindrom, pentru că acesta se poate transforma după o bâlbâială într-un număr palindrom, și anume 44.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii