Fişierul intrare/ieşire:bomboane.in, bomboane.outSursăONI 2017, clasa a 9-a
AutorSandor LukacsAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 nri 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 ≤ 106.
  • 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

bomboane.inbomboane.outExplicaţie
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).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?