notwen

Algoritmul, pas cu pas

Pare un joc geometric complicat — un măr care sare, se ciocnește, dă înapoi — dar dacă urmărești cu câți centimetri se apropie, totul se așază frumos în binar. Într-o oscilație, după $k$ ciocniri cu înclinata, super-mărul s-a apropiat cu $1 + 2 + 4 + \dots + 2^{k-1} = 2^k - 1$ cm. Aceste sume $2^k - 1$ sunt exact numerele cu biți de $1$ peste tot — semnul că răspunsul se citește pe biți, nu pe centimetri.

Fie $L$ lungimea binară a distanței curente $d$ (adică $2^{L-1} \le d < 2^L$). O oscilație completă, cu reculul de la final, face mereu același lucru: adaugă $L$ ciocniri înclinate, $1$ ciocnire verticală, apoi transformă distanța.