Adott két vektor v1=(x1,x2,...,xn) és v2 = (y1,y2,...,yn). A két vektor skalárszorzata egyetlen szám: x1*y1+x2*y2+...+xn*yn.
Tegyük fel, hogy a vektorok koordinátáit szabadon permutálhatjuk (tetszőleges sorrendben írhatjuk). Határozzuk meg az így kapható minimális skalárszorzatot. FeladatÍrjunk programot, ami megadja a skalárszorzat lehetséges értékei közül a minimálisat.
BemenetA bemenet első sora a tesztesetek T számát tartalmazza. (1 <= T <= 1000). Ezután T teszteset következik, három-három sorban kódolva. Az első sor n értékét adja meg (1 <= n <= 800), majd az xi és yj koordináták következnek, egy-egy sorban, szóközökkel elválasztva (-100000 <= xi, yj <= 100000).
KimenetA kimenet T sort tartalmaz, mindegyik sorban a megfelelő tesztesetre kapható minimum szerepel.
Példa
TesztadatokCímkékA feladat forrása: Google Code Jam 2008 1A (online tesztelő)
Algoritmusok: mohó algoritmus
megoldás |
Programozás > Feladatok >