 |
Az S. 84. feladat (2013. november) |
S. 84. Péter az öccsével a következő játékot játssza: megkéri őt, hogy találjon ki egy N különböző pozitív egészből álló számsorozatot. Ezután ezt az öcsi úgy kódolja, hogy az i-edik helyen álló szám helyére a c számot írja, amennyiben az eredeti sorozat i-edik számával végződő leghosszabb szigorúan monoton növekvő (nem feltétlenül összefüggő) részsorozata c számból áll. Például a kigondolt, eredeti sorozat lehet a 3 1 2 4 8 20 10 sorozat. Ehhez a kódolt változat a következő: 1 1 2 3 4 5 5. Ezt a kódolt sorozatot kapja vissza Péter az öccsétől. Péternek az a feladata, hogy találjon egy olyan sorozatot, aminek a kódolt változata megegyezik az öccsétől kapott kódolt sorozattal. Készítsünk programot, amely segít Péternek játszani.
A program olvassa be a standard input első sorából N-et (), majd a következő sorból a kódolt sorozat elemeit, melyek szóközzel elválasztott egészek, és írjon a standard output első és egyetlen sorába egy olyan N db pozitív egészből álló sorozatot, melyet ha kódolunk, akkor pont a bemenetet kapjuk. Mivel több megoldás lehet, így mindegy, melyiket adjuk meg. A bemeneti számok egyike sem nagyobb 10000000-nál, a kimenet se legyen ennél nagyobb. A kimenet különböző számokból kell, hogy álljon.
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. A megoldásért részpontszámok kaphatók, ha a program N
5-re, illetve N500-ra megoldást ad.
Beküldendő egy tömörített s84.zip állományban a program forráskódja (s84.pas, s84.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 (s84.txt, s84.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. december 10-én LEJÁRT.
Mintamegoldásnak Molnár-Sáska Zoltán megoldását tesszük közzé. s84.zip
Statisztika:
25 dolgozat érkezett. 10 pontot kapott: Alexy Marcell, Farkas Domonkos, Fonyó Viktória, Jákli Aida Karolina, Juhász 326 Dániel, Kiss 666 Péter, Makk László, Manz Günter, Molnár-Sáska Zoltán, Németh 123 Balázs, Somogyvári Kristóf, Uzonyi 000 Ákos, Weisz Ambrus, Zalavári Márton. 9 pontot kapott: Halmosi Bence, Kókai Kristóf, Kovács-Deák Máté, Olexó Gergely. 8 pontot kapott: 2 versenyző. 4 pontot kapott: 2 versenyző. 1 pontot kapott: 2 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2013. novemberi informatika feladatai