hibrid

Algoritmul, pas cu pas

Mașina merge de la o bornă la următoarea în linie dreaptă. La fiecare astfel de pas plătește pentru fiecare porțiune taxabilă peste care trece complet. Întrebarea „de câte ori e traversată porțiunea $i$?" pare să ne oblige să comparăm fiecare mutare cu fiecare porțiune — dar enunțul ne oferă un cadou ascuns.

Când e traversată o porțiune

O mutare de la $a$ la $b$ acoperă intervalul $[\min(a,b), \max(a,b)]$. O porțiune $[st, dr]$ e traversată dacă e cuprinsă complet în acest interval. Aici intervine cadoul: nicio bornă nu e în interiorul sau la capetele unei porțiuni. Capetele mutării ($a$ și $b$) sunt deci mereu în afara porțiunii, așa că „a cuprinde complet porțiunea" se reduce la „a trece peste un singur punct din interiorul ei" — de exemplu gaura dintre $st$ și $st+1$.