Sa
consideram un teanc format din n
carti. Acest teanc va fi partitionat în mai multe teancuri, executând,
cât timp este posibil, mutari de tipul urmator:
alegem un teanc ce contine cel putin doua carti mai mult decât teancul
din dreapta sa si mutam cartea din vârful acestui teanc în teancul
din dreapta sa (se considera ca dupa ultimul teanc – cel mai din dreapta –exista
un teanc vid).
Când nu se mai poate executa nici o astfel de mutare, consideram ca am
obtinut o configuratie finala.
Cerinta
Dat fiind n, sa se determine
o configuratie finala.
Date de
intrare
Fisierul de intrare teanc.in
contine o singura linie pe care se afla numarul natural n.
Date de
iesire
Fisierul de iesire teanc.out
va contine doua linii. Pe prima linie va fi scris un numar natural k
reprezentând numarul de teancuri din configuratia finala. Pe cea de a
doua linie vor fi scrise k numere
naturale separate prin câte un singur spatiu, reprezentând în
ordinea de la stânga la dreapta numarul de carti existente în cele
k teancuri din configuratia finala.
Restrictii
3 <= n <= 2 000 000 000
| teanc.in | teanc.out | Explicatie |
| 7 |
4 3 2 1 1 |
Se
pot obtine (în ordine) configuratiile: 7 6 1 5 2 4 3 4 2 1 3 3 1 3 2 2 3 2 1 1 |
Timp maxim de executie/test: 0.1 secunde
prof.
Emanuela Cerchez
Liceul de
Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com