Fişierul intrare/ieşire:popularitate.in, popularitate.outSursăAlgoritmiada 2010, Runda 2
AutorStefan Alexandru FilipAdăugată deProstuStefan-Alexandru Filip Prostu
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inpopularitate.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?