Fişierul intrare/ieşire:maestru.in, maestru.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorTeodor IonescuAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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, unde prin distanta intelegem xj-xi, oricare ar fi i si j cu i<j, 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

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 x1, x2, … xN.

Date de ieşire

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.

Restricţii

  • 1 ≤ T ≤ 4000
  • 3 ≤ N ≤ 5000
  • 3 ≤ P ≤ 109
  • 1 ≤ xi ≤ 109
  • atat pozitiile pietrelor in fisierul de intrare, cat si pozitiile oricaror noi pietre adaugate sunt obligatoriu distincte doua cate doua

Exemplu

maestru.inmaestru.out
3
3 7
1 6 12
3 4
2 4 6
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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?