Rączy jelonek
Limit pamięci: 64 MB
Rączy jelonek zmierza długimi susami na polanę.
Rozpiera go energia, więc każdy jego skok może być nawet dwa razy dłuższy od poprzedniego.
Formalnie rzecz ujmując, w każdym momencie energia jelonka jest na określonym poziomie .
Jelonek ma dwie możliwości ruchu:
- skok o metrów w przód lub w tył, powodujący automatyczne przełączenie na poziom energii ,
- skok wzwyż, który nie powoduje przemieszczenia na drodze do polany oraz skutkuje przełączeniem na poziom .
Początkowo, jelonek ma energię równą .
W momencie, gdy jego energia jest równa i jelonek skoczy wzwyż, zatrzymuje się.
Poniżej przedstawiono przykładową podróż rączego jelonka, która rozpoczęła się w punkcie po lewej stronie drogi.
Numery nad strzałkami oznaczają poziom energii jelonka po danym skoku. Wartość oznacza, że jelonek się zatrzymał.
Droga prowadząca do polany jest nieskończona w obydwóch kierunkach.
Oznacza to, że jelonek w trakcie podróży może znaleźć się za polaną lub przed punktem, z którego wyrusza.
Jelonka od celu dzieli początkowo metrów.
Oblicz, jaka jest najmniejsza liczba skoków, która pozwoli mu dotrzeć do polany i zatrzymać się tam.
Wejście
Pierwsza linia wejścia, zawiera jedną liczbę całkowitą () oznaczająca odległość pomiędzy jelonkiem a polaną.
Dodatkowo, w testach wartych sumarycznie punktów, .
Wyjście
Wypisz jedną liczbę całkowitą równą minimalnej liczbie skoków, które musi wykonać jelonek, aby dotrzeć do polany i zatrzymać się.
Przykład
Dla danych wejściowych:
6
poprawną odpowiedzią jest:
9