|
Titlul: 1204 ChatNoir Scris de: Andrei Grigorean din Noiembrie 20, 2011, 21:24:39 Aici puteţi discuta despre problema ChatNoir (http://infoarena.ro/problema/chatnoir).
Titlul: Răspuns: 1204 ChatNoir Scris de: FMI Romila Remus Arthur din Decembrie 06, 2011, 16:37:44 Imi poate explica cineva rationamentul in urma carui s-a ajuns la concluzia ca pisica poate scapa doar daca se afla la o distanta de cel mult 4 casute de margine?
Titlul: Răspuns: 1204 ChatNoir Scris de: Simoiu Robert din Decembrie 06, 2011, 17:12:06 Rationamentul este urmatorul : sa spunem ca suntem pe patratelul de coordonate (i, j) si vrem sa "scapam" cu pisica, si sa zicem ca o luam spre directia cea mai putin costisitoare, sa presupunem ca este in stanga. Acuma, mergand spre stanga, Felix, ca sa fie "destept" trebuie sa incerce sa acopere cele 2 colturi spre care se indreapta pisica (stanga sus si stanga jos, adica 1, 1 si N, 1). Acuma, coltul avand doua iesiri, avem o problema : daca Felix nu reuseste sa acopere cele 4 colturi pana ca pisica sa ajunga la margine, atunci ea scapa fugand pe langa margine. In figura urmatoare prezint cazul cel mai defavorabil pisicii, dar pentru care totusi ea scapa, si anume cazul in care ea ajunge din exact 4 pasi in cea mai apropiata margine (apasa pe imagine pentru marire).
(http://img31.imageshack.us/img31/3278/capturedlr.th.png) (http://imageshack.us/photo/my-images/31/capturedlr.png/) |