Fişierul intrare/ieşire:	bomboane.in, bomboane.out	Sursă	ONI 2017, clasa a 9-a
Autor	Sandor Lukacs	Adăugată de	Bogdan Ciobanu •bciobanu
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

Bomboane

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.

Î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).

Cerinţe

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ă

Date de intrare

Fişierul de intrare bomboane.in conţine pe prima linie două numere naturale p (numărul cerinţei de rezolvat), şi n (numărul de cutii), despărţite printr-un spaţiu. Pe următoarea linie se găsesc n valori naturale, separate prin câte un spaţiu, reprezentând numărul de bomboane din fiecare cutie.

Date de ieşire

Dacă p = 1 se va rezolva numai punctul a) din cerinţă. În acest caz fişierul de ieşire bomboane.out va conţine o valoare naturală reprezentând numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărţirea frăţească.
Dacă p = 2 se rezolvă numai punctul b). Fişierul de ieşire bomboane.out va conţine n linii. Pe fiecare linie i, prima valoare nr_i reprezintă numărul maxim de colegi care pot primi bomboane din cutia i, urmată de nri valori separate prin câte un spaţiu reprezentând o modalitate de împărţire a bomboanelor din cutia i, dacă Zeno alege împărţirea diferenţiată.

Restricţii

• 1 ≤ p ≤ 2
• Dacă p = 1 atunci 1 ≤ n ≤ 10.000 şi 1 ≤ numărul de bomboane din cutii ≤ 10⁶.
• 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.

Exemplu

Cum se trimit solutii?