Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_02_06 - Podróżowanie ze stylem

Bajteusz znudził się pisaniem wszystkich tych programów, rozwiązywaniem zadań, wymyślaniem i optymalizowaniem algorytmów, itd. Miał już tego wszystkiego dosyć, całej tej cywilizacji. Wybrał zatem wszystkie oszczędności z banku, kupił bilet lotniczy i poleciał do Konga, gdzie w gęstej dżungli ciężko znaleźć jakąkolwiek technologię.

Bajteusz szybko zaznajomił się ze zwyczajami panującymi w dżungli oraz z trybem życia, jaki się tam prowadzi. Jednym z problemów, którym Bajteusz musiał stawić czoła jest umiejątność szybkiego poruszania się. Każdy, kto chce szybko przemieścić się z jednego miejsca w drugie, musi skorzystać z systemu lian. Na każdym z n drzew znajduje się jedna liana o długości xi. Z i-tego drzewa można przemieścić się na xi+i-te lub -xi+i-te drzewo. Innymi słowy można poruszać się o xi drzew w przód lub w tył. Każdy kto skakał po lianach wie, że nawet jeśli liana jest dłuższa niż odległość między drzewami, nie da się między nimi przemieścić.

Mając tak ogromne doświadczenie w znajdywaniu optymalnych rozwiązań, Bajteusz automatycznie wybiera najkrótszą trasę, którą musi przebyć, żeby dostać się z drzewa A na drzewo B. Postanowiłeś/aś nie być gorszy/a od Bajteusza i napisać program, który obliczy to, co nasz bohater instynktownie wie.

Wejście

Wejście składa się z nieokreślonej ilości testów. Każdy z nich zawiera 2 linie. W pierwszej znajdują się 3 liczby: n, a i (n≤103, 0<a,b≤n) oznaczające odpowiednio ilość drzew z lianami oraz numery drzewa początkowego i końcowego. W drugiej natomiast jest n liczb z przedziału 0..105, oznaczających długości lian na kolejnych drzewach (licząc od 1).

Wyjście

Dla każdego testu należy wypisać jedną liczbę, oznaczającą minimalną ilość drzew, które musi odwiedzić Bajteusz, aby dostać się z drzewa A na drzewo B. Jeżeli jest to awykonalne, należy wypisać -1.

Przykład

Wejście:
6 1 6
1 2 1 1 1 9
6 2 6
1 2 1 1 1 9

Wyjście:
4
3

Dodane przez:Piotr Kąkol
Data dodania:2012-09-29
Limit czasu wykonania programu:0.100s-1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2012-11-03 19:36:26 Piotr KÄ…kol
Bajteusz nie korzysta z lian gdy chce pozostać na tym samym drzewie. ;-)
2012-11-03 19:26:06 Marcin Kasprowicz
Co w przypadku, gdy chcemy wykonać ruch
1 1 1
0
Musi być zerowa lina, czy wystarczy, że jesteśmy na tym drzewie, bo nie wiem już gdzie szukać błędu :(
2012-11-03 14:38:38 Adam B±k
Też czasem mam taką ochotę :-)
2012-11-03 14:30:09 Przemek Komosa
Chyba podążę śladem Bajteusza :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.