Fişierul intrare/ieşire: | forma.in, forma.out | Sursă | Olimpiada locala 2012, Clasa a 8-a |
Autor | Doina Druta, Luminita Ciocaru | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 2048 kbytes |
Scorul tău | N/A | Dificultate | N/A |
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.