Rezolvare PBinfo #1473

Cerința

Cei n elevi de la grupa pregătitoare au primit câte două cartonaşe, fiecare cartonaş având scris pe el un număr natural. Ei s-au aşezat în cerc şi, la un semnal dat, fiecare a scos la întâmplare un cartonaş din buzunar. Copiii vă roagă să răspundeţi la următoarele întrebări:
1. Care poate fi suma maximă S a numerelor de pe cartonaşele scoase, ştiind că produsul acestora este divizibil cu un număr prim p?
2. Care poate fi lungimea maximă L a unei secvenţe de copii de pe cerc pentru care suma numerelor de pe cartonaşele scoase de către oricare doi vecini din secvenţă este pară?

Date de intrare

Fișierul de intrare grupapregatitoare.in conține pe prima linie numerele n şi p, iar pe următoarele n linii câte două numere naturale reprezentând numerele de pe cartonaşele fiecărui elev, în ordinea în care s-au aşezat pe cerc.

Date de ieșire

Fișierul de ieșire grupapregatitoare.out va conține pe prima linie numărul S, iar pe a doua linie numărul L.

Restricții și precizări

• 3 ≤ n ≤ 2000
• 2 ≤ p ≤ 1000
• numerele de pe cartonaşele elevilor sunt nenule şi mai mici decât 1001
• există cel puţin un număr divizibil cu p pe un cartonaş
• se acordă 40% din punctaj pentru prima cerinţă şi 60% pentru a doua, în fişierul grupapregatitoare.out trebuind să fie afişate două numere

Exemplu:

grupapregatitoare.in

3 7
1 2
21 4
5 6

grupapregatitoare.out

29
3

Explicație

Sunt 3 elevi, iar p=7. Primul elev a primit cartonaşe cu numerele 1 şi 2, al doilea 21 şi 4, iar al treilea 5 şi 6.
1. Luând cartonaşele cu numerele 2, 21 şi 6, produsul lor este 252, divizibil cu p=7 şi suma lor este maximă, egală cu 29.
2. Luând cartonaşele cu numerele 2, 4 şi 6 avem 2+4=6 par, 4+6=10 par şi 6+2=8 par, deci secvenţa de lungime maximă cu proprietatea cerută are lungimea 3.