Az S. 78. feladat (2013. február)

S. 78. 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: . 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: a_i pozitív egész (). 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: . 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 a_i szóközzel elválasztott egészeket, és írja a standard output első és egyetlen sorába a maximális parcellaszámot.

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: ;

további 3 pontért: ;

további 4 pontért: .

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ó.

(10 pont)

A beküldési határidő 2013. március 11-én LEJÁRT.

Megoldás

Négyzetes futásidejű megoldás: Minden kezdőparcellára megkeressük a leghosszabb parcellasorozatot, amely megfelel a feladat feltételeinek.

nlogn-es megoldás: Intervallumfával megoldható, hogy minden intervallumra meg tudjuk határozni a minimális és a maximális elemet logn időben. Ezt most nem részletezem, de bármilyen intervallumfa megoldja ezt. Ennek segítségével a következőképp oldjuk meg a feladatot. FIGYELEM, ez egy általánosan hasznos módszer: Felveszünk két változót, i-t, j-t, i=1, j=1 kezdetben. Az algoritmus egy általános lépése: ha az (i,j) intervallum megfelel a feladat feltételeinek, akkor j-i egy lehetséges megoldás, j-t növeljük; ellenkező esetben i-t. Egy ilyen ellenőtzés logn idejű, mert megkeressük a minimális és a maximális elemet, a különbségüket vesszük, utána meg könnyen eldönthető, hogy ez kisebbegyenlő, vagy nagyobb, mint a megengedett határ. Már csak azt kellene látnunk, hogy így a legnagyobb intervallumot valóban megkapjuk, az meg teljesülni fog, hiszen i előbb utóbb a legjobb intervallum kezdőpontjára áll, és akkor j-vel megkapjuk a végét.

Viszont nem ez a legjobb megoldás! Van lineáris idejű is! Erre egy mintamegoldást töltök fel, ami erősen kihasználja a double ended queue-t, azaz egy olyan sorszerű adatszerkezetet, melynek az elejére és a végére is beszúrhatunk elemet, és törölhetünk is konstans időben. Az alapötlet a következő: végigmegyünk egy index-szel 1-től n-ig, és tároljuk az összes legkisebb és legnagyobb elemet. Amíg a legeslegkisebb és a legeslegnagyobb elem közt nincs T-nél nagyobb távolság, addig jó, utána meg töröljük a sorrendben legkorábbi extrém elemet. Azért használható a double ended queue, mert mindig monoton lesz a szóba jöhető legkisebb és legnagyobb elem.

A mintamegoldás: S78.cpp

Statisztika:

5 dolgozat érkezett.
9 pontot kapott:	Vályi András.
8 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2013. februári informatika feladatai