Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | maestru.in, maestru.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 16 |
| Autor | Teodor Ionescu | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Maestru
Legenda spune ca maestrul Su Elf-chi a capatat insasi de la zei tainele unei licori magice cu puteri formidabile menite sa “bucure sufletul”. Singurul legamant pe care acesta il avea de asumat era acela de a nu depasi anumite concentratii de consum ale acesteia pentru a nu dezlantui haosul in univers. Secole de-a randul omenirea a trait in pace si prosperitate. Acest lucru avea insa sa se schimbe odata cu aparitia cazanelor de arama. Licoarea s-a dezlantuit si a inceput sa capete forme malefice zapacind mintile oamenilor si osandindu-i la chinuri vesnice. Singura sansa de salvare a omenirii a fost ca maestrul sa faca hatarul zeilor si sa duca la bun sfarsit incercarile acestora.
Se facea ca prima incercare era aceea de a traversa un rau cu totul si cu totul din apa. Zeii au plasat pe acest rau un numar de pietre N pe care maestrul sa poata sari o singura data inainte ca acestea sa se scufunde. Pozitiile pietrelor sunt date sub forma unui sir sortat de numere intregi x1 x2 … xN, unde x1 si xN reprezinta marginile din stanga si din dreapta ale raului.
Tocmai iesit fiind din meditatia transcedentala, maestrul poate sari de pe o piatra pe alta doar daca distanta dintre ele este cel mult o valoare P data, scopul sau fiind de a ajunge de pe malul stang notat cu x1 pe cel drept notat cu xN si inapoi la x1.
Noi stim ca numarul de pietre este insuficient ca maestrul sa indeplineasca aceasta sarcina, insa vedeniile provocate de licoarea melefica i-au intunecat ratiunea. Este de datoria voastra sa interveniti si sa adaugati un numar minim de pietre si sa il salvati pe maestru de la osanda atingerii apei.
Date de intrare
Fişierul de intrare maestru.in ...
Date de ieşire
În fişierul de ieşire maestru.out ...
Restricţii
- 3 ≤ N ≤ 5000
- 3 ≤ P ≤ 109
- 1 ≤ xi ≤ 109
Exemplu
| maestru.in | maestru.out |
|---|---|
| 3 3 7 1 6 12 3 4 1 3 5 4 4 1 5 10 11 | 1 0 3 |
Explicaţie
In primul test maestrul nu poate sari direct de pe un mal pe celalalt, avand nevoie de piatra de pe pozitia 6, iar pentru a se putea intoarce ne gandim sa adaugam o piatra la pozitia 5.
Pentru al doilea test, in mod ciudat, maestrul nu are nevoie de nicio alta piatra pentru a se deplasa intre cele doua maluri.
Pentru cel de-al treilea test, ne gandim sa adaugam pietrele 3,6 si 9. Un drum posibil ar fi atunci 1 -> 5 -> 9 -> 11 -> 10 -> 6 -> 3 -> 1
