Mikro

Mirko je na državnom natjecanju iz biologije za prvu nagradu dobio novi mikroskop i sada provodi svo svoje slobodno vrijeme proučavajući mikro-svijet. U jednom od svojih eksperimenata Mirko proučava kretanje bakterija u kapljici vode iz potoka koji prolazi pored njegove zgrade. Primijetio je da se bakterije kreću na vrlo specifičan način. Kapljicu vode možemo predstaviti beskonačnom kvadratnom mrežom. Za svaku bakteriju poznate su koordinate kvadrata na kojem se ona nalazi i smjer u kojem se kreće. Smjer kretanja opisujemo brojkom od 1 do 8 kao što je prikazano na slici dolje. Kretanje se odvija u diskretnim trenucima i to tako da će bakterija, koja se u nekom trenutku nalazi na kvadratu označenom slovom B, u sljedećem trenutku skočiti na kvadrat označen odgovarajućom brojkom. Sve bakterije skaču istovremeno.

Ponekad se dogodi da se dvije ili više bakterija susretne na nekom kvadratu u istom trenutku. Kažemo da se u trenutku T dogodio susret ranga K ako se nekih K bakterija nakon točno T skokova od početka promatranja nađe na istom kvadratu. Mirku su najzanimljiviji susreti visokog ranga, pa bi htio predvidjeti koji će susret imati najveći rang i kada će se taj susret desiti. Ako ima više takvih susreta, zanima ga samo prvi od njih. Napišite program koji će za zadane koordinate i smjerove kretanja bakterija odrediti kojeg će ranga biti susret maksimalnog ranga i kada će se prvi takav dogoditi.