| 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, 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.in | maestru.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
