Pracsiu Dan (dnprx) 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 şi 3 sunt 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 coordonatelorxale 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 două 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ța
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
Explicație
Cele 6 variante sunt:
