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, Adrian Sandor, 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. Inca nu am rezolvat problema, pentru ca pot exista mai multe perechi de numere pentru care teroristul sa fie la locatia X0 + Y * T1 in momentul T1. Prin faptul ca am gasit pozitia teroristului la un moment fixat T1, am redus problema la una noua determinata de parametrii X0', Y' in care in care nu il stim pe Y dar X0' = 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 (medie ca dificultate, de pe Lista lu' Francu), Tom & Jerry (grea, nu a facut-o nimeni din cate stiu eu cand a propus-o Mugurel la lot) si tunnels (foarte grea, nu a facut-o nici o echipa in finala ACM ICPC 2006), smuggler (de pe rec.puzzles.org cu solutie). Daca sunteti curiosi de rezolvari, putem sa le discutam pe forum.