turnuri

Time limit: 0.01s
Memory limit: 64MB
Input: turnuri.in
Output: turnuri.out

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 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:

Problem info

ID: 114

Editor: liviu

Author:

Source: ONI 2004 XI-XII: Ziua 1, Problema 3

Tags:

ONI 2004 XI-XII

Log in or sign up to be able to send submissions!