La Şcoala de Vrăjitorie Hogswarts, Harry Potter şi colegii săi îşi pun la încercare puterea vrăjilor cu ajutorul baghetelor magice. O vrajă constă în mutarea unuia sau a mai multor obiecte din încăperile şcolii în ‘camera vrăjilor’ unde se află adunaţi toţi elevii.
Fiecare dintre cei n ‘elevi vrăjitori’ este înzestrat cu o anumită putere; dacă un elev are puterea 1, cu o vrajă el aduce 1 obiect, dacă puterea este 2 cu o vrajă el va aduce 2 obiecte, … pentru un elev cu puterea de valoare p, cu o vrajă el va aduce p obiecte. Pe de altă parte, fiecare elev are o anumită rapiditate (viteză) de efectuare a vrăjilor. Astfel, pe parcursul unei ore, un elev cu viteza 1 va reuşi să facă o singură vrajă, un elev cu viteza 2 va reuşi două vrăji una după alta etc. Evident, un elev cu puterea 3 şi care are viteza 4, va reuşi să aducă până la sfârşitul orei 12 obiecte (3 la prima vrajă, încă 3 la a doua vrajă, încă 3 la a treia vrajă şi încă 3 la ultima vrajă).
La sfârşitul orei de vrăjitorie, fiecare elev primeşte un număr de cutii pentru a ambala în ele numai obiectele aduse de el, astfel încât în fiecare dintre cutiile sale să se afle acelaşi număr de obiecte. Profesorul Dumbledore vrea în plus ca fiecare elev să primească acelaşi număr de cutii. O soluţie simplă ar fi să distribuie fiecărui elev o singură cutie, însă el şi-ar dori să distribuie cât mai multe cutii.
Cerinţă
Cunoscând pentru fiecare dintre cei n ‘elevi vrăjitori’ ai şcolii Hogswarts, puterea cu care este înzestrat şi viteza cu care reuşeşte să facă vrăjile, determinaţi:
- cel mai mare număr de obiecte ce pot fi aduse până la sfârşitul orei de către un singur ‘elev vrăjitor’
- care este numărul maxim de cutii pe care le va primi fiecare elev ţinând cont de faptul că fiecare elev va trebui să îşi distribuie în mod egal obiectele sale în aceste cutii.
Date de intrare
Din fişierul de intrare vraji.in se citeşte de pe prima linie numărul natural n, reprezentând numărul elevilor. De pe următoarele n linii se citesc informaţiile despre elevi, câte un elev pe o linie, sub forma a două numere separate prin spaţiu, reprezentând puterea şi viteza elevului.
Date de ieşire
Fişierul de ieşire vraji.out va conţine pe prima linie cel mai mare număr de obiecte ce pot fi aduse în ‘camera vrăjilor’ de către un singur ‘elev vrăjitor’ la sfârşitul orei. Pe cea de a doua linie va fi scris cel mai mare număr de cutii pe care îl poate primi fiecare elev respectând condiţiile din problemă.
Restricţii
Numărul n al elevilor, puterea şi viteza fiecăruia sunt numere naturale mai mari decât zero şi mai mici sau egale cu 100.
Fiecare cutie va conţine numai obiecte ale unui singur ‘elev vrăjitor’.
Fiecare elev va primi acelaşi număr de cutii.
Exemple
vraji.in
vraji.out
Explicaţii
5
5 2
6 4
3 10
20 2
7 2
40
2
5 - ‘elevi vrăjitori’
elev 1 : Număr total de obiecte =5*2=10
elev 2 : Număr total de obiecte=6*4=24
elev 3 : Număr total de obiecte=3*10=30
elev 4 : Număr total de obiecte=20*2=40
elev 5 : Număr total de obiecte=7*2=14
40 este cel mai mare număr de obiecte aduse de un vrăjitor
2 este cel mai mare număr de cutii pe care îl poate primi fiecare elev
3
4 2
6 8
6 6
48
4
3 - ‘elevi vrăjitori’
elev 1 : Număr total de obiecte =4*2=8
elev 2 : Număr total de obiecte=6*8=48
elev 3 : Număr total de obiecte=6*6=36
48 este cel mai mare număr de obiecte aduse de un vrăjitor
4 este cel mai mare număr de cutii pe care îl poate primi fiecare elev