| Fișierul intrare/ieșire | cluburi.in, cluburi.out | Sursă | ONI 2010 clasa a 5-a |
|---|---|---|---|
| Autor | Susana Gălățan | Adăugată de |
Coman Isabela Patricia
•
Isabela_coman
|
| Timp de execuție pe test | 0.1 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate |
  1.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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.in | cluburi.out | Explicatii |
|---|---|---|
| 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. |
