Fișierul intrare/ieșire bomboane3.in, bomboane3.out Sursă ONI 2017, clasa a 9-a
Autor Sandor Lukacs Adăugată de avatar TincaMatei Tinca Matei TincaMatei
Timp de execuție pe test 0.1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate N/A

Bomboane3 ( clasa a 9-a )

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

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ă

Date de intrare

Fișierul de intrare bomboane3.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 bomboane3.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

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii