| 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 |
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 |
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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.
