== include(page="template/taskheader" task_id="maestru") ==
Poveste şi cerinţă...
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 $x[~1~], x[~2~], … x[~N~]$ , unde $x[~1~]$ si $x[~N~]$ 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, unde prin distanta intelegem $x[~j~]-x[~i~]$, oricare ar fi $i$ si $j$ cu $i<j$, scopul sau fiind de a ajunge de pe malul stang notat cu $x[~1~]$ pe cel drept notat cu $x[~N~]$ si inapoi la $x[~1~]$.
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.
h2. Date de intrare
Fişierul de intrare $maestru.in$ ...
Pe prima linie a fisierului de intrare se gaseste $T$, numarul de teste. Pe prima linie a fiecarui test se afla numerele $N$ si $P$, urmand ca pe linia imediat urmatoare sa fie descris sirul sortat $x[~1~], x[~2~], … x[~N~]$.
h2. Date de ieşire
În fişierul de ieşire $maestru.out$ ...
In fisierul de iesire se vor afisa $T$ linii, pe fiecare dintre acestea un intreg reprezetand numarul minim de pietre ce trebuiesc adaugate. Daca exista o configuratie prin care se pot adauga numarul minim de pietre indicat in asa fel incat maestrul sa-si poate realiza drumul, solutia se considera corecta.
h2. Restricţii
* $1 ≤ T ≤ 4000$
* $3 ≤ N ≤ 5000$
* $3 ≤ P ≤ 10^9^$
* $1 ≤ x[~i~] ≤ 10^9^$
* atat pozitiile pietrelor in fisierul de intrare, cat si pozitiile oricaror noi pietre adaugate sunt obligatoriu distincte doua cate doua
h2. Exemplu
table(example). |_. maestru.in |_. maestru.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
3 7
1 6 12
3 4
2 4 6
4 4
1 5 10 11
| 1
0
3
|
h3. 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
== include(page="template/taskfooter" task_id="maestru") ==
