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 <= n <= 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
Bemenet |
Kimenet |
5
#-##----# -----#- ---#- -#- -
4
#-#-#-- #---# ##- -
0
|
9
4
|
Tesztadatok
Címkék
A feladat forrása: ???
Algoritmusok: geometriai algoritmusok, háromszög rács, üres háromszög, dinamikus programozás
megoldás |