Concurs MI UB 2022 - Furnica in spirala

Se considera o suprafata $matrice$ infinita in jos si in dreapta, cu liniile numerotate de sus in jos si coloanele de la stanga la dreapta, incepand de la 1. O furnica exploreaza aceasta suprafata pornind din coltul stanga-sus (1,1), la pasul 1.

Deoarece furnica vrea sa ramana mereu aproape de zona deja explorata, ea extinde succesiv patratul deja parcurs din coltul stanga-sus: la inceput coboara in celula (2,1), apoi merge la dreapta in (2,2), apoi urca in (1,2), completand un patrat 2x2. Pe acesta il extinde mergand la dreapta in (1,3), apoi coborand in (2,3) si (3,3), dupa care se deplaseaza spre stanga in (3,2) si (3,1), completand un patrat 3x3, si tot asa.

Se observa ca la finalul explorarii unui patrat k x k, furnica se afla exact la pasul k^2: daca k este par, ea se afla in coltul (1,k); daca k este impar, se afla in coltul (k,1). Din acel colt, ea extinde patratul catre (k+1)x(k+1) mergand mai intai cu un pas perpendicular pe latura scurta, apoi parcurgand restul marginii noului patrat.

Se da un numar intreg t. Pe ce linie si pe ce coloana se va afla furnica la pasul t?

1

1 1

9

3 1