Programozás‎ > ‎Feladatok‎ > ‎

Ellentámadás

Az edzőtáborban különböző mozgás sorozatokat tanulunk. Védekezésnél csak két csatárunk van a támadó térfélen. Amikor megszereztük a labdát, valamelyik csatárt rögtön indítani próbáljuk egy hosszú átadással. A csatárok ismerik egymás mozgását és passzolhatnak egymásnak.

Több döntést kell hozniuk. Az ábrán körökkel jelölt fix pontokon eldönthetik, hogy a másik csatár következő körrel jelölt pontjára passzolnak, vagy tovább vezetik a labdát a saját útvonalukon. Végül az utolsó pontból kapura kell lőni. Mind a négy elemnek (hosszú indítás, rövid passz, labdavezetés, kapura lövés) ismert a nehézsége. A rövid passzok és a labdavezetés nehézsége minden pozícióban és mindkét csatárra más és más.

Mi a minimális nehézségű mozgássorozat amivel gólt szerezhetünk, ha optimálisan játszunk?

Feladat

Írjunk programot, ami kiszámítja, a minimális nehézséget, amivel gól szerezhető.

Bemenet

A bemenet első sora a tesztesetek C számát adja meg (1 <= C <= 100). Minden teszteset 5 sorból áll:
  • Az első sor öt számot tartalmaz: N, L0, L1, S0, S1
    • A csatárok mozgását leíró út  rögzített pontjainak N száma (2 <= N <= 100 000).
    • 0<= L0, L1 < 100 annak nehézsége, hogy a védő hosszan indítja az első illetve második csatárt
    • 0<= S0, S1 < 100 annak nehézsége, hogy az első illetve második csatár belövi a gólt
  • A következő négy sor mindegyike N-1 számot tartalmaz, amelyek nemnegatív és 1000-nél kisebb egészek
    • az első csatár passzolásának nehézségét az i. pontról a másik csatár (i+1). pontjára
    • az első csatár labdavezetésének nehézségét az i. és (i+1). pont között
    • majd ugyanezek az adatok a másik csatárra

Kimenet

Minden sorba egyetlen egész számot kell írni, az adott  tesztesethez tartozó minimális nehézséget, amivel gól szerezhető.

Példa

Bemenet  Kimenet
2
3 3 5 7 999
9 13
60 5
22 6
5 5
5 3 5 7 999
9 13 8 4
60 5 17 13
22 6 15 11
5 5 18 29		23
42

Tesztadatok

ellen.zip (2,7 MB)

Címkék

A feladat forrása: ACM / German Collegiate Programming Contest 2012 /Counter Attack/
Algoritmusok: 

megoldás