spiralmatrix

Cum gândim problema

Întâi limpezim ce căutăm. Cele două subșiruri sunt disjuncte, de lungime egală și cât mai lungi. Primul conține $1$ și e format din numere consecutive, deci e $1, 2, \dots, L$. Al doilea conține $n^2$ și e tot consecutiv, deci e $n^2 - L + 1, \dots, n^2$. Ca să nu se suprapună și să fie maxime, $L = \lfloor n^2 / 2 \rfloor$ (dacă $n^2$ e impar, exact un element din mijloc rămâne neacoperit).

Așadar nu ne interesează tot subșirul, ci doar două numere: $v_1 = L$ (capătul primului) și $v_2 = n^2 - L + 1$ (începutul celui de-al doilea). Toată problema se reduce la o singură întrebare: unde se află valoarea $k$ în spirală?

Naiv, am construi matricea și am căuta. Dar pentru $n$ aproape de $10^9$ ea ar avea până la $10^{18}$ celule — exclus. Trucul e că spirala are o structură foarte regulată: e formată din inele concentrice, iar fiecare inel ocupă un interval contiguu de valori.