Fișierul intrare/ieșire forma.in, forma.out Sursă Olimpiada locala 2012, Clasa a 8-a
Autor Doina Druță | Luminița Ciocaru Adăugată de avatar ioanab Ioana Bica ioanab
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Forma (clasa a 8-a)

“Forma de bază” a unui număr cu cifre distincte se creează prin renumerotarea cifrelor sale în funcție de mărimea cifrei în cadrul numărului. De exemplu, pentru numărul 34597 “forma de bază” este 12354. Două numere naturale x și y scrise în baza 10, ambele formate doar din cifre distincte, se numesc echivalente dacă au același număr de cifre (adică p=q) și dacă au aceeași “formă de bază”.

Cerinta

Scrieți un program care citește două numere naturale b și n, apoi n numere naturale a1, a2, ..., an, distincte două câte două, reprezentând cele n elemente ale unei mulțimi A = {a1, a2, ..., an} și care determină:

  • Numărul elementelor mulțimii A care sunt echivalente cu b;
  • Numărul maxim de elemente ale unei submulțimi C a lui A, cu proprietatea că oricare două elemente din C sunt echivalente.

Date de intrare

Fișierul forma.in conține pe prima linie numărul b, pe a doua linie numărul n reprezentând numărul de elemente ale mulțimii A, iar pe a treia linie cele n elementele ale mulțimii A: a1, a2, ..., an, separate prin câte un spațiu.

Date de ieșire

Fișierul forma.out va conține:

  • pe prima linie, un număr natural reprezentând numărul elementelor mulțimii A echivalente cu b;
  • pe a doua linie, un număr natural reprezentând numărul maxim de elemente ale submulțimii C.

Restricții

  • 10 ≤ b ≤ 109; b numar natural
  • 1 ≤ n ≤ 10.000; n numar natural
  • 10 ≤ a1, a2, ..., an ≤ 109
  • a1, a2, ..., an nu sunt formate neaparat din cifre distincte
  • Pentru rezolvarea corectă a cerinței a) se acordă 40% din punctaj, iar pentru rezolvarea corectă a ambelor cerințe se acordă 100% din punctaj.

Exemplu

forma.in forma.out
54
9
15 254 73 475 95 697 136 30 183
3
4

Explicație

a) “Forma de bază” a numărului 54 este 21 deoarece cifra 5 este a doua ca mărime în numărul 54, iar cifra 4 este prima ca mărime în cadrul aceluiași număr. În mod analog numerele 73, 95 și 30 au aceeași “formă de bază” cu numărul 54, deci se va afișa 3.
b) Oricare două elemente din mulțimea C = {254, 475, 697, 183} sunt echivalente deoarece au aceeași “formă de bază” deci se va afișa 4.

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

Indicii de rezolvare

Arată 2 categorii