Programozás‎ > ‎Feladatok‎ > ‎

Szabályos háromszögek

Van N darab pálcánk, amelyek hossza S1, S2, ..., SN. A pálcák összeilleszthetők: egy Si és egy Sj hosszúságúból készíthetünk Si+Sj hosszúságút. Szeretnénk a pálcákból egy szabályos háromszöget készíteni, amelynek oldala a lehető legnagyobb.

Feladat

Írjunk programot, ami megadja, hogy mekkora a legnagyobb elkészíthető szabályos háromszög oldalhossza. Ha nem készíthető egyenlő oldalú háromszög a pálcákból, akkor 0-t kell kiírni. Nem kötelező az összes pálcát felhasználni.

Bemenet

A bemenet több tesztesetet tartalmaz. Minden eset két sorból áll: az első sor a pálcák DB darabszámát tartalmazza, a második pedig a pálcák Hi hosszát, szóközökkel elválasztva. ( 4 <= DB <= 100, 1<= Hi <= 100 )

Kimenet

Minden sorba egyetlen számot kell kiírni, az adott tesztesethez tartozó legnagyobb lehetséges oldalhossz értékét.

Példa

Bemenet  Kimenet
5
1 1 1 1 1
4
1 2 3 4
8
2 4 4 9 3 7 6 2
0
1
0
11


Tesztadatok

Címkék

A feladat forrása: BME Challenge 24, 2011 EC
Algoritmusok: dinamikus programozás