furnica

Intuiție / reformulare

Nu te lăsa speriat de poveste: tot traseul este o succesiune simplă de segmente, în ordine fixă. Dacă reconstruiesc lista lor, toate cele trei cerințe se rezolvă parcurgând-o o singură dată.

Cum arată traseul, de la stânga la dreapta:

1. urcarea inițială pe marginea stângă a primei foi (înălțimea ei);
2. pentru fiecare foaie, vârful ei — un segment orizontal de lungimea laturii orizontale;
3. între două foi vecine, o treaptă verticală: dacă foaia următoare e mai înaltă, furnica urcă diferența; dacă e mai joasă, coboară diferența;
4. coborârea finală pe marginea dreaptă a ultimei foi (înălțimea ei).

Ideea cheie

Fiecare segment are un tip (urcare, coborâre, orizontal) și o lungime în cm. Tipul dă costul în timp: urcare $5$ s/cm, coborâre $2$ s/cm, orizontal $3$ s/cm. Treptele dintre foi se decid din diferența de înălțime: $v_{i+1} - v_i$ pozitiv → urcare, negativ → coborâre, zero → nimic.