2157 - Bomboane 3

Enunt

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ţa

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 bomboane3.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 şi precizări

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

Exemplul 1

bomboane3.in

 1 3
 14 23 17

bomboane3.out

 3

Explicație

Se rezolvă numai punctul a). Numărul maxim de colegi care pot primi bomboane dacă Zeno alege împărțirea frățească e 3.

Exemplul 2

bomboane3.in

 2 3
 14 23 17

bomboane3.out

 4 3 4 6 1
 6 6 2 7 1 3 4 
 5 2 1 3 7 4

Explicație

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

Rezolvare

<syntaxhighlight lang="python" line> def max_colleagues_fraternally(boxes):

   min_bombs = min(boxes)
   max_colleagues = 0
   for i in range(1, min_bombs + 1):
       valid = True
       for box in boxes:
           if box % i != 0:
               valid = False
               break
       if valid:
           max_colleagues = max(max_colleagues, i)
   return max_colleagues

def division_differently(boxes):

   min_bombs = min(boxes)
   max_colleagues = min_bombs
   result = []
   for box in boxes:
       diff = max_colleagues - min_bombs
       curr_division = [min_bombs + i * (diff + 1) for i in range(min_bombs)]
       result.append((max_colleagues, curr_division))
   return result

def main():

   with open("bomboane3.in", "r") as fin:
       p, n = map(int, fin.readline().split())
       boxes = list(map(int, fin.readline().split()))

   if p == 1:
       max_colleagues = max_colleagues_fraternally(boxes)
       with open("bomboane3.out", "w") as fout:
           fout.write(f"{max_colleagues}\n")
   elif p == 2:
       divisions = division_differently(boxes)
       with open("bomboane3.out", "w") as fout:
           for division in divisions:
               fout.write(f"{division[0]} {' '.join(map(str, division[1]))}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>