Problema saptamanii (Solutie)

Cosmin Negruseri
04 noiembrie 2007

Problema a fost rezolvata de Mihai Patrascu, Radu Cebanu, Adrian Vladu, Marius Buzea, Marius Andrei, Adrian Carcu, Giurgea Mihnea, Liviu Ciortea, Razvan Alecsandrescu, Igor Naverniouk si Csaba Patcas.

La prima vedere pare nerezolvabila, dar de fapt are o solutie destul de simpla. Ea se bazeaza pe faptul ca multimea ZxZ e numarabila. Putem verifica in fiecare secunda T cate o coordonata X0 + Y * T, parcurgand perechile (X0, Y) in spirala. Vom ajunge la un T1 pentru care teroristul este la locatia X0 + Y * T1. In acel moment am redus problema la una mai simpla in care nu il stim pe Y dar il stim pe X0, pentru problema simplificata acesta e X0 + Y * T1. Aceasta subproblema se poate rezolva usor.

Alta problema cu teroristi ce mie imi place foarte mult este Lesbulan , ca dovada am si propus-o la concursul Bursele Agora.

Probleme cu tema similara sunt si Soarecele si pisica , Tom & Jerry si tunnels

Comentarii