Fişierul intrare/ieşire:cluburi.in, cluburi.outSursăONI 2010 clasa a 5-a
AutorSuzana GalatanAdăugată deIsabela_comanComan Isabela Patricia Isabela_coman
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Cluburi ( clasa a 5-a )

La şcoala Iuliei, în clasa a V-a sunt n elevi. Pentru că aşa e moda la această şcoală, fiecare dintre cei n copii şi-a creat câte un club. Fiecare club are iniţial un singur membru: copilul care l-a creat. Copiii au hotărât că numărul membrilor unui club poate să crească prin unificarea cu un alt club după următoarea regulă: două cluburi se pot unifica dacă au acelaşi număr de membri. Prin unificare, unul dintre cluburi continuă să existe, iar celălalt se desfiinţează. Clubul care continuă să existe preia toţi membrii clubului care se desfiinţează. Deoarece elevii se distrează mai bine atunci când clubul are mai mulţi membri, ei au hotărât să unifice cluburile după regula de mai sus, cât timp unificarea este posibilă.

Cerinţe:

Scrieţi un program care să citească numărul natural n şi care să determine:
a) cel mai mic număr natural k de cluburi care continuă să existe după ce s-au produs toate unificările;
b) pentru fiecare dintre cluburi, numărul de membri.

Date de intrare

Fişierul de intrare cluburi.in conţine o singură linie pe care este scris un număr natural nenul n, reprezentând numărul de elevi din clasa a V-a.

Date de ieşire

Fişierul de ieşire cluburi.out va conţine:
- pe prima linie un număr natural k, reprezentând cel mai mic număr de cluburi care continuă să existe după ce s-au produs toate unificările
- pe a doua linie, k numere naturale nenule, separate prin câte un spaţiu, reprezentând numărul de membri ai fiecărui club, în ordinea crescătoare a numărului de membri.

Restricţii

  • 1 <= n <= 30000
  • În cazul în care numărul elevilor este impar se consideră că elevul rămas singur formează un club.
  • Pentru fiecare test de intrare se poate determina cel puţin un club.
  • Se acordă punctaje parţiale: cerinţa a) 30% din punctaj, cerinţa b) 70% din punctaj

Exemplu

cluburi.incluburi.outExplicatii
7
3
1 2 4
6 elevi formează 3 cluburi având fiecare câte 2 membri, iar elevul
rămas formează la rândul lui un club (cu un singur membru).
Apoi 2 dintre cluburile cu câte 2 membri se unesc şi formează un
singur club cu 4 membri, deci sunt 3 cluburi: 1 cu un membru, 1
cu 2 membri şi 1 cu 4 membri.
24
2
8 16
Iniţial se formează 12 cluburi cu câte 2 membri, apoi 6 cu câte 4
membri.
Din cele 6 cluburi se vor forma apoi 3 cu câte 8 membri.
Două dintre cluburile cu 8 membri se unesc formand unul cu 16
membri. În final rămân 2 cluburi, unul cu 8, iar celălalt cu 16
membri.
Trebuie sa te autentifici pentru a trimite solutii. Click aici