Renumitul arhitect Prăbuşilă doreşte să construiască unul din cele mai interesante turnuri de pe planetă. Acest turn, în mod cu totul deosebit, va avea etaje de diverse lăţimi, între 1 şi 100, numere întregi.
Prăbuşilă s-a hotărât deja ce dimensiune va avea fiecare din etajele turnului, dar nu şi cum să le aşeze pe orizontală. El ar dori mai întâi să ştie câte variante are.
Etajele pot fi aşezate la coordonate întregi şi va trebui ca un astfel de turn să nu se dărâme.
- Condiţia pentru ca un turn să fie stabil este ca la fiecare etaj perpendiculara coborâtă din centrul de greutate al grupului etajelor superioare să cadă strict în interiorul acelui etaj (nu are voie să fie pe margini sau în afară - de ex. turnurile
2şi3sunt instabile). - Centrul de greutate al unui etaj se află la mijlocul etajului respectiv.
- Centrul de greutate al unui grup de etaje are drept coordonată
x(orizontală) media coordonatelor x ale centrelor de greutate ale etajelor componente. (Etajele au mase egale, indiferent de cât de late sunt).
În exemplul 1, etajul din vârf are coordonata x a centrului de greutate 2, iar grupul celor 2 etaje din vârf are centrul de greutate la coordonata x=1.75 (media aritmetică intre 2 şi 1.5)
Se observă în figura 1 că, deşi perpendiculara din centrul de greutate al etajului 2 cade în afara etajului 1, totuşi turnul este stabil, deoarece perpendiculara din centrul de greutate al grupului format din etajele 2–8 cade strict în interiorul etajului 1.
Cerinţă
Să se afle câte turnuri stabile există.
Date de intrare
Fişierul de intrare turnuri.in conţine pe o singură linie lista de numere naturale separate prin câte un spaţiu, numere reprezentând lăţimile etajelor turnului, începând cu cel mai de sus. Lista se termină cu un 0.
Date de ieşire
Fişierul de ieşire turnuri.out conţine numărul de turnuri.
Restricţii şi precizări:
- numărul maxim de turnuri nu va depăşi
2 000 000 000 - numărul maxim de etaje ale unui turn este
200 - lăţimea maximă a unui etaj este
100
Exemplu:
turnuri.in
1 3 4 1 0
turnuri.out
6
Cele 6 variante sunt:
