avion

Algoritmul, pas cu pas

Gândește-te concret la drumul unui pasager: intră pe o scară, merge pe culoar până în dreptul rândului lui, apoi se strecoară de la culoar la scaun. Problema pare să ceară comparații complicate, dar de fapt toate pasajerii cu același rând fac aceeași alegere — și nici nu depinde de scaun. Tot ce contează e cât de aproape e rândul de fața avionului față de spate.

Drumul oricărui pasager are trei bucăți:

$\text{drum} = \underbrace{3}_{\text{intrare}} + \underbrace{(\text{rânduri pe culoar})}_{\text{depinde de scară}} + \underbrace{(\text{culoar} \to \text{scaun})}_{1,\,2 \text{ sau } 3}$

Distanța de la culoar la scaun (notată $d_s$) este aceeași indiferent de scară:

Singura diferență între cele două scări este cât merge pe culoar:

• scara 1 (față, lângă rândul $1$): până la rândul $R$ sunt $R$ metri;
• scara 2 (spate, lângă rândul $NR$): până la rândul $R$ sunt $NR - R + 1$ metri.

Deci cele două drumuri sunt: $d_1 = 3 + R + d_s, \qquad d_2 = 3 + (NR - R + 1) + d_s$