| Fişierul intrare/ieşire: | popularitate.in, popularitate.out | Sursă | Algoritmiada 2010, Runda 2 |
| Autor | Stefan Alexandru Filip | Adăugată de |  Stefan-Alexandru Filip •Prostu |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Popularitate
Se dau K si M grupuri de numere. Fiecare din cele M grupuri contine Ni numere. Fie Gi produsul numerelor din grupul i. Definim popularitatea unui grup ca fiind P daca KP divide Gi si KP+1 nu divide Gi, sau, echivalent, de cate ori se imparte Gi la K. Se cere sa determinati grupul cu popularitatea maxima.
Date de intrare
Fişierul de intrare popularitate.in contine pe prima linie K, iar pe a doua linie din fisier se gaseste M. Pe urmatoarele M linii se gasesc descrierile grupurilor. Pe linia i+2 prima valoare reprezinta Ni. Ea e urmata de Ni numere asociate grupului i.
Date de ieşire
În fişierul de ieşire popularitate.out veti afisa 2 valori reprezentand popularitatea cea mai mare si grupul care are aceasta popularitate. In caz ca sunt mai multe grupuri care au popularitate maxima afisati grupul cu indice minim.
Restricţii
- 2 ≤ K ≤ 10000000 (10 milioane)
- 1 ≤ M ≤ 100
- 1 ≤ Ni ≤ 2000
- Grupurile sunt formate din numere naturale din intervalul [1, 100000000] (100 milioane)
- Pentru 30% din teste K este prim.
- Pentru 30% din teste Ni ≤ 100.
Exemplu
| popularitate.in | popularitate.out |
|---|---|
| 6 3 6 2 3 5 8 12 9 4 5 7 64 11 3 4 9 81 | 4 1 |
Explicaţie
grupul 1 are popularitate 4, 2 * 3 * 5 * 8 * 12 * 9 = 25920 = 64 * 20
grupul 2 are popularitate 0, 5 * 7 * 64 * 11 = 24640 nu se divide cu 6
grupul 3 are popularitate 2, 4 * 9 * 81 = 2916 = 62 * 81
