Informatika gyűjtemény

Egy szinttel feljebb Háromszög

2004050607080910

NézetNyomtat

Háromszög

Egy háromszög alakú papírból szeretnénk papírdíszt készíteni. A háromszöget oldalaival párhuzamos egyenesek kisebb háromszögekre osztják, és csak ezek mentén tudunk pontosan vágni. Sajnos a papírból már kivágtak néhány kisebb háromszöget, ezért a megmaradt anyagból kell kivágni a lehetséges legnagyobbat.

Feladat

Írj programot, amely megadja a maximális területű kivágható háromszög méretét! A méretet a kisháromszögek számával kell megadni.

Bemenet

A haromszog.be szöveges állomány tartalmazza a teszteseteket. Az első sor a papírháromszög oldalának hosszát tartalmazza ($ 1\le {\tt n} \le 100 $). Utána a háromszög leírása következik n sorban. Minden sor háromféle karaktert tartalmazhat:
  • - jelzi a használható háromszögeket
  • # jelzi a már kivágott háromszögeket
  • szóközök formázzák a bemenetet háromszög alakúra
A bemenet több ilyen blokkot tartalmazhat, a bemenet végét egy "0" jelzi.

Kimenet

A haromszog.ki szöveges állományba soronként egy-egy számot, a megfelelő tesztesetben kivágható maximális háromszög területét kell írni.

Példa

haromszog.beharomszog.ki
5 #-##----# -----#- ---#- -#- - 4 #-#-#-- #---# ##- - 0 9 4

Tesztadatok