5. naloga

Žabe

Nad močvirjem leta r rojev muh. Vsak roj je sestavljen iz zelo velikega števila muh. Gibanje posameznega roja opišemo z zaporedjem koordinat in časov, ko se roj na svoji poti za trenutek ustavi. Tako bi postanke i-tega roja muh opisali s seznamom trojic (xi,j,yi,j,ti,j), ki predstavljajo j-ti postanek i-tega roja na koordinati (xi,j,yi,j) ob času ti,j. Predpostavimo lahko, da so postanki na poti posameznega roja podani po naraščajočih časih, torej ti,j < ti,j+1.

Poleg muh se v močvirju nahaja tudi z žab, ki lovijo muhe. Žaba lahko ulovi muho iz roja samo v trenutku, ko se roj ustavi, če se ravno takrat nahaja na istem mestu kot roj. Poznamo tudi lokacije žab: i-ta žaba se trenutno (ob času 0) nahaja na koordinati (ai,bi). Vse žabe se lahko premikajo po močvirju s hitrostjo 1 enote na sekundo (lahko pa tudi stojijo pri miru). Žaba se lahko med poljubnima dvema točkama premika v ravni črti, torej za merjenje razdalje uporabi evklidsko razdaljo (Pitagorov izrek).

Žabe načrtujejo lov na muhe. Ulovile bodo nekaj muh, nato pa se zbrale v koordinatnem izhodišču (0, 0), kjer si bodo plen razdelile. Vsaka žaba bo ujela največ eno muho. Ker so muhe dobro rejene, je žabam dovolj, če vse skupaj ujamejo k muh (velja k ≤ z), ki si jih nato razdelijo.

Opiši in utemelji postopek, ki bo določil najkrajši čas, v katerem se lahko vse žabe zberejo v izhodišču in pri tem skupaj ulovijo k muh. Koordinate in časi so realna števila.