 |
Az S. 85. feladat (2013. december) |
S. 85. Adott egy darab pozitív egészből álló sorozat:
. Ennek a sorozatnak keressük az értékes részsorozatait. Egy részsorozat akkor értékes, ha összefüggő és a centrális eleme nem kisebb egy adott C (
) korlátnál. Egy részsorozat centrális elemét a következőképp definiálhatjuk: ha páratlan elemszámú, akkor nagyság szerinti sorrendben a középső elem, ha páros elemszámú a sorozat, akkor a középső két elem közül a nem kisebb. Például a {9,2,1,6} sorozatnak a 6, és a {4,9,5} sorozatnak az 5 a fent definiált rendezés utáni középső eleme. Mivel egy sorozathoz általában nagyon sok értékes részsorozat tartozhat, így csak ezek számára vagyunk kíváncsiak.
A program olvassa be a standard input első sorából N-et és C-t, majd a következő sorból a sorozat elemeit, és írja a standard output első és egyetlen sorába az értékes részsorozatok számát.
Magyarázat: a következő sorozatok értékesek: {10}, {6}, {10,5}, {5,6}, {6,2}, {10,5,6}, {10,5,6,2}.
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 az 1 mp futásidőkorláton belül.
Részpontszámok a következőkre kaphatóak:
- a program N
200-ra megoldást ad;
- program N2000-re megoldást ad.
Beküldendő egy tömörített s85.zip állományban a program forráskódja (s85.pas, s85.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 (s85.txt, s85.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ő 2014. január 10-én LEJÁRT.
Mintamegoldásnak Jákli Aida Karolina megoldását tesszük közzé. S85.zip
Illetve megjegyzem, hogy érdemes utánanézni az úgynevezett intervallumfának, vagy segment tree-nek. Közzéteszem Weisz Ambrus megoldását, illetve egy oktató anyagot a témáról. main.cpp Az anyag:
Statisztika:
20 dolgozat érkezett. 10 pontot kapott: Jákli Aida Karolina, Kiss 666 Péter, Makk László, Németh 123 Balázs, Somogyvári Kristóf, Weisz Ambrus. 9 pontot kapott: Zalavári Márton. 8 pontot kapott: 1 versenyző. 7 pontot kapott: 1 versenyző. 6 pontot kapott: 4 versenyző. 4 pontot kapott: 1 versenyző. 2 pontot kapott: 2 versenyző. 1 pontot kapott: 4 versenyző.
A KöMaL 2013. decemberi informatika feladatai