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
|