Feladat: S.78 Korcsoport: - Nehézségi fok: -
Füzet: 2013/február, 108. oldal  PDF  |  MathML 

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Bergengóciában a tudósok egy új növényfélét szeretnének vizsgálatoknak alávetni. Mivel a növénynek igen speciális igényei vannak, így a tudósok mindenképp egy összefüggő területen (tehát szomszédos parcellákon) szeretnék termeszteni. Ehhez rendelkezésükre áll N egymást követő parcella: 1N5000000. Bergengóciában nagyok a szintkülönbségek az egyes parcellák között. Ismert minden parcellának a tengerszint feletti magassága: ai pozitív egész (1ai2000000000). Ráadásul a növényt csak olyan parcellákon lehet termeszteni, ahol bármely két parcella szintkülönbsége nem halad meg egy T korlátot: 0T2000000000. A tudósok a növényt a rendelkezésre álló parcellák közül minél több parcellán szeretnének termeszteni. Adjuk meg a maximális elérhető parcellaszámot.
A program olvassa be a standard input első sorából N-et és T-t, majd a következő sorból az ai szóközzel elválasztott egészeket, és írja a standard output első és egyetlen sorába a maximális parcellaszámot.

 
Példa bemenet:Példa kimenet:9 347 3 5 7 10 8 8 11 12   
 

Magyarázat: a 7, 10, 8, 8 magasságú parcellák megfelelőek, de akár a 10, 8, 8, 11 is helyes 4 hosszú parcellasorozat; 5 hosszú nincsen.
Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani a 2,5 mp futásidőkorláton belül. Mivel a bemeneti állomány nagy, ezért érdemes beleszámolni, hogy a legnagyobb tesztesetek beolvasása önmagában 2 mp időbe telhet. Kapható részpontszám a 9 pontból, ha a program csak kisebb tesztesetekre tud lefutni időben. Az alábbi korlátok érvényesek az egyes részmegoldásokra:

2 pontért: 0<N3000;
további 3 pontért: 3000<N200000;
további 4 pontért: 200000<N5000000.

Beküldendő egy tömörített s78.zip állományban a program forráskódja (s78.pas, s78.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s78.txt, s78.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.