Zeno are n cutii cu bomboane, iar în fiecare cutie se găsește un număr natural nenul de bomboane. Zeno poate împărți bomboanele din toate cutiile colegilor în două moduri: frățește sau diferențiat.
Împărțirea frățească se realizează astfel:
* numărul de colegi care primesc bomboane din fiecare cutie este același (dacă din prima cutie primesc bomboane k colegi și din cutia 2 vor primi tot k colegi, și din cutia 3 tot k colegi etc).
* bomboanele din fiecare cutie se împart în mod egal între cei k colegi, aceștia primind un număr nenul de bomboane.
* în final în fiecare cutie trebuie să rămână un număr identic de bomboane (posibil zero) care îi revin lui Zeno. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, din prima cutie oferă câte 4 bomboane pentru 3 colegi, din a * doua cutie câte 7 bomboane pentru 3 colegi, iar din ultima cutie câte 5 bomboane pentru 3 colegi, iar în fiecare cutie rămân 2 bomboane.
* numărul de colegi care primesc bomboane din fiecare cutie este același (dacă din prima cutie primesc bomboane k colegi și din cutia 2 vor primi tot k colegi, și din cutia 3 tot k colegi etc).
* bomboanele din fiecare cutie se împart în mod egal între cei k colegi, aceștia primind un număr nenul de bomboane.
* în final în fiecare cutie trebuie să rămână un număr identic de bomboane (posibil zero) care îi revin lui Zeno. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, din prima cutie oferă câte 4 bomboane pentru 3 colegi, din a doua cutie câte 7 bomboane pentru 3 colegi, iar din ultima cutie câte 5 bomboane pentru 3 colegi, iar în fiecare cutie rămân 2 bomboane.
Împărțirea diferențiată se realizează în felul următor:
* dintre colegii care primesc bomboane din aceeași cutie fiecare coleg primește un număr diferit de bomboane (număr nenul), neexistând doi colegi care primesc număr identic de bomboane din aceeași cutie;
* din fiecare cutie Zeno oferă bomboane unui număr cât mai mare de colegi.
* diferențele în modul dintre numărul de bomboane primite consecutiv de doi colegi sunt distincte două câte două. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, bomboanele din prima cutie se pot împărți astfel (3, 4, 6, 1), bomboanele din a doua cutie (6, 2, 7, 1, 3, 4), iar bomboanele din a treia cutie se pot împărți astfel (2, 1, 3, 7, 4).
* dintre colegii care primesc bomboane din aceeași cutie fiecare coleg primește un număr diferit de bomboane (număr nenul), neexistând doi colegi care primesc număr identic de bomboane din aceeași cutie;
* din fiecare cutie Zeno oferă bomboane unui număr cât mai mare de colegi.
* diferențele în modul dintre numărul de bomboane primite consecutiv de doi colegi sunt distincte două câte două. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, bomboanele din prima cutie se pot împărți astfel (3, 4, 6, 1), bomboanele din a doua cutie (6, 2, 7, 1, 3, 4), iar bomboanele din a treia cutie se pot împărți astfel (2, 1, 3, 7, 4).
h2. Cerinta
Cunoscând n numărul de cutii și numărul de bomboane din fiecare cutie să se scrie un program care determină:
a). Numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.
b). O modalitate de împărțire a bomboanelor din fiecare cutie, dacă se face împărțirea diferențiată
a) Numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.
b) O modalitate de împărțire a bomboanelor din fiecare cutie, dacă se face împărțirea diferențiată
h2. Date de intrare
h2. Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ p ≤ 2
* Dacă p = 1 atunci 1 ≤ n ≤ 10.000 și 1 ≤ numărul de bomboane din cutii ≤ 10[^6^].
* Dacă p = 2 atunci 1 ≤ n ≤ 200 și 1 ≤ numărul de bomboane din cutii ≤ 100.000.
* Dacă există mai multe soluții se poate afișa oricare.
* Pentru rezolvarea fiecărei cerințe se acordă 50% din punctaj.
h2. Exemplu
table(example).
|_. bomboane3.in |_. bomboane3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. bomboane3.in |_. bomboane3.out |_. Explicatie |
| 1 3
14 23 17
| 3
| Se rezolvă numai punctul a). Numărul maxim de colegi care pot primi bomboane dacă Zeno alege împărțirea frățească e 3.
|
| 2 3
14 23 17
| 4 3 4 6 1
6 6 2 7 1 3 4
5 2 1 3 7 4
|Se rezolvă numai punctul b). Din prima cutie pot primi bomboane maxim 4 colegi.
O modalitate de împărțire astfel încât fiecare coleg să primească un număr diferit de bomboane,
iar diferențele dintre bomboanele primite de doi colegi consecutivi să fie distincte
două câte două este (3, 4, 6, 1). Este corectă și soluția (1, 2, 7, 4).
|
== include(page="template/taskfooter" task_id="bomboane3") ==
