Utolsó módosítás: 2008. október 9.
A hat feladatot szeptember 26-án, pénteken tűztem ki. Ehhez három hétre, október 10-én, péntekig minden hallgatónak be kell adnia helyes megoldást a hatból legalább 2 azaz két feladatra. (Pénteken még egész nap be lehet adni.) Még egy héttel későbbig, október 17-ig be lehet adni több feladatot is a feladatsorból mindegyik helyes megoldás egy pontot ér, és ezek a pontok hozzáadódnak a versenyek pontszámához, így könnyebben lehet jobb jegyet szerezni.
Az összes nyilvános példa bemenetet és kimenetet (a heti mintafeladatokéval) egyben le lehet tölteni:
Tegyük például fel, hogy ezt az archívumot letöltötte és kicsomagolta,
ekkor a 2. feladat 0. teszt bemenete a s0/s0f2be0 fájl lett.
Most tegyük fel, hogy erre a feldatatra ír egy megoldást,
amit a s0f2.c C nyelvű forrásfájl alkot,
és ezt lefordította a
gcc -std=c99 -W -Wall -pedantic-errors -O -lm -o s0f2 s0f2.c
paranccsal.
Ha a fordítás sikeres, a 0. teszt bemenetet átirányíthatja a program
standard bemenetére a ./s0f2 < s0/s0f2be0 paranccsal,
és ekkor ugyanazt kell kapnia,
mint ami az s0/s0f2ki0 kimenetben áll.
Rögtön is ellenőrizheti az egyezést a
./s0f2 < s0/s0f2be0 | diff -q - s0f2ki0 paranccsal,
ez szólni fog, ha eltérést talál.
Minden példára egyszerre is megteheti ugyanezt,
például for x in s0/s0f2be*; do ./s0f2 < "$x" | diff -q - ${x/be/ki}; done .
Ebben a feladatban egy számsorozatban fogja megkeresni a szomszédos tagok közötti legnagyobb távolságot.
A program bemenete két sorból áll. Az első sor egyetlen N egész számot tartalmaz (2<=N<=100). A második sor N darab egész számot tartalmaz szóközzel elválasztva: ezek A_0, …, A_{N-1}. (Mindegyik egész -100 és 100 közé esik.)
Számoljuk ki a szomszédos számok különbségének abszolutértékét: |A_1 - A_0|, |A_2 - A_1|, …, |A_{N-1} - A_{N-2}|. Ezen abszolutértékek közül a legnagyobbat kell előállítani.
A kimenet egyetlen nemnegatív egész számból áll, ez a kapott legnagyobb különbség abszolutértéke.
(A program a bemenetet a standard bemenetről olvassa be, a kimenetet a standard kimenetre írja. A bemenetnek és a kimenetnek is minden sorát egy újsor karakter zárja le, a sorokon belül az egyes számok decimális formában vannak kiírva fölösleges nullák nélkül és fölösleges előjelek nélkül, a sorokon belüli számokat egy szóköz választja el, az első szám előtt és az utolsó szám után azonban nem áll szóköz.)
Például az alább letölthető első példában N = 10, a legnagyobb abszolut különbség pedig az A_1 = 7 és A_0 = 29 számokból jön, így a kimenet 22.
Példa bemenetek és kimenetek. (Bármely szabályos bemenethez a kimenet egyértelmű, vagyis ha két program eredménye eltér, akkor az egyik hibás.)
A feladat megoldásához segít a 6. mintafeladat. Ezt a feladatot az ott található program módosításával, vagy teljesen új program írásával is meg lehet oldani.
Ebben a feladatban olyan programot fog írni, amely egy szövegben megkeresi az összes olyan egymás utáni bizonyos tulajdonságú sorokból álló nem bővíthető sorozatot, amely pontosan hat sorból áll.
A program bemenetként egy szövegfájlt kap a standard bemeneten. Ennek a fájlnak minden sora legfeljebb 1023 karakterből áll, mégpedig egy lezáró sorvége jelen kívül csak az angol ábécé kis- és nagybetűiből és számjegyekből.
Nevezzünk egy sort érdekesnek, ha az első karaktere a kis p betű.
(A nagy P betűvel kezdődő sorok nem számítanak érdekesnek.)
Tekintsük az egymás utáni érdekes sorokból álló nem bővíthető sorozatokat. Egy ilyen sorozat tehát egy vagy több olyan érdekes sorból áll úgy, hogy köztük nincsen nem érdekes sor; az első sor vagy a fájl első sora, vagy közvetlenül egy nem érdekes sor előzi meg; és az utolsó sor vagy a fájl utolsó sora, vagy közvetlenül egy nem érdekes sor követi.
A program az ilyen nem bővíthető érdekes sorokból álló sorozatokból keresi meg a pontosan hat eleműeket. A program kimenete ezekből a pontosan hat elemű nem bővíthető sorozatokból áll, és a sorozatok között egy-egy üres sorból.
Minden sorozatnak mind a hat sorát ki kell írni, mégpedig olyan sorrendben, ahogy a fájlban eredetileg szerepelnek. (A hat sor között esetleg lehet egy vagy több egyforma tartalmú is.) Minden hat érdekes sorból álló nem bővíthető sorozatot meg kell találni és kiírni, ugyanolyan sorrendben, ahogyan a fájlban előfordulnak.. Ha legalább két megfelelő sorozat van, akkor minden két sorozat közé egy-egy üres sort kell írni, de egy sorozat sorai közé ne írjon más sort, és a kimenet elejére vagy végére se írjon üres sort. Ha egyáltalán nincs megfelelő sorozat, akkor semmit ne írjon ki. A kimenetet a standard kimenetre kell írni. Minden sor egy újsor karakterrel zárul, épp úgy, ahogy a bemenetben is.
A program megírásához érdemes lehet kiindulni a minták közül a 6. minta forrásából, ezt lemásolni, és módosítani. Természetesen teljesen új programot is szabad írni.
Íme néhány bemenet és a megfelelő kimenetek. Minden bemenethez egyértelmű a kimenet, ha más kimenetet kapott, akkor az egyikünk programja hibás.
Ez a feladat nagyon egyszerű: kavicsokból álló kupacokat fogunk rakosgatni.
Tekintsük a következő egyszemélyes játékot. Adott néhány kupac, mindegyikben egy vagy több kavics van. A játék minden lépése abból áll, hogy miden kupacból elveszünk egy kavicsot, és ezekből a kavicsokból létrehozunk egy új kupacot. Azok a kupacok, amelyekben egy kavics sincsen, megszűnnek.
(Ez a játék matematikai problémának is érdekes: próbálja meg például bebizonyítani, hogy ha tíz kavicsból indulunk ki bármilyen elrendezésben, akkor előbb vagy utóbb mindig előáll az a helyzet, amikor négy kupacban rendre négy, három, kettő és egy kavics van.)
A feladat célja olyan programot írni, ami ezt a játékot játssza.
A program bemenete két sorból áll. Az első sor két természetes számot tartalmaz: ezek legyenek L, K. Az egyik szám 1<=L<=100 adja meg a lejátszandó lépések számát, a második 1<=K<5000 a kupacok számát a kezdőhelyzetben. A második sor pontosan K darab egész számot tartalmaz csökkenő sorrendben: ezek a számok adják meg a kezdőhelyzetben az egyes kupacok elemszámát. Ha tehát a második sorban szereplő számok A_0, …, A_{K-1}, akkor A_{K-1} <= A_{K-2} <= … <= A_0 <= 1, a kezdőhelyzet K darab kupacból áll, és ezekben rendre A_0, … A_{K-1} kavics van.
A program kimenete L sorból áll. Az első sorban a játék állása szerepel a kezdőhelyzet után egy lépéssel, a második sorban a kezdőhelyzet után két lépéssel, és így tovább, az utolsó sor azt az állást írja le, ami a kezdőhelyzetből L lépés végrehajtása után áll elő. Mindegyik sorban néhány pozitív egész szám áll csökkenő sorrendben, amelyek a bemenet második sorához hasonlóan leírják a játék egy állását a kupacok elemszámával.
Fontos, hogy a kimenetben is minden sorban csökkenő sorba legyenek rendezve a számok. Ehhez érdemes felhasználni, hogy a kezdőhelyzetben is rendezve vannak a számok, így el lehet kerülni, hogy teljesen rendezni kelljen a kupacokat. Ezen kívül figyeljünk arra, hogy a kimenetben ne legyenek nullák, hiszen az üres kupacok a játék szabályai szerint eltűnnek.
Például tekintsük a következő bemenetet.
8 9
7 2 1 1 1 1 1 1 1
Ekkor az első lépésben a kilenc kupacból hét eltűnik, mert az utolsó kupacot kiszedjük belőle, az első két kupacban csak 6 és 1 elem marad, és az eltávolított kupacokból keletkezik egy új, 9 elemű kupac. Így a kimenet első sora
9 6 1
A második lépésben az egyik kupac megint eltűnik, és lesz egy új, 3 kavicsos kupacunk, így a kimenet második sora
8 5 3
A harmadik sor hasonlóan
7 4 3 2
és így tovább. Vegyük észre, hogy az új kupacot az első sorban a sor elejére, a második sorban a végére, a harmadikban a közepére kellett beszúrnunk.
(A program a bemenetet a standard bemenetről olvassa be, a kimenetet a standard kimenetre írja. A bemenetnek és a kimenetnek is minden sorát egy újsor karakter zárja le, a sorokon belül az egyes számok decimális formában vannak kiírva fölösleges nullák nélkül, a sorokon belüli számokat egy szóköz választja el, az első szám előtt és az utolsó szám után azonban nem áll szóköz.)
Példa bemenetek és kimenetek.
A megírandó program bemenetként egy sakktáblán elhelyezkedő ponthalmazt kap, kimenetként meg kell keresnie a ponthalmaz összefüggő komponenseit, és megadnia, a halmaz melyik pontja hányadik komponenshez tartozik.
A program a bemenetet a standard bemenetről olvassa be, a kimenetet a standard kimenetre írja. A bemenetnek és a kimenetnek is minden sorát egy újsor karakter zárja le, a sorokon belül az egyes számok decimális formában vannak kiírva fölösleges nullák nélkül, a sorokon belüli számokat egy szóköz választja el, az első szám előtt és az utolsó szám után azonban nem áll szóköz.
A bemeneti fájl első sora két egész számot tartalmaz: az első szám N, a második M, ahol 1 <= N, M <= 300. A fájl ezen kívül még pontosan N sorból áll, amelyek mindegyikében M darab egész szám található, és ezen számok mindegyike 0 vagy 1.
A bemenet az N sorból és M oszlopból álló sakktábla mezőinek egy halmazát adja meg: az (x, y) eleme ennek a halmaznak akkor és csak akkor, ha az (első sort leszámítva) x-edik sorban az y-edik szám 1. Két mező szomszédos, ha élszomszédosak, azaz az egyik koordinátájuk megegyezik, a másik koordinátájuk eggyel tér el. (Az egyes mezőknek tehát legfeljebb négy szomszédja van.) A halmaz egy összefüggő komponense egy olyan nem bővíthető részhalmaza, amelyben bármelyik mezőről bármelyik másikra el lehet jutni a halmazban lévő élszomszédos mezőkön keresztül.
A bemenetként kapott halmaz összefüggő komponenseit sorszámozzuk 1-től kezdve folyamatosan növő egészekkel. Az a komponens kapja az 1-es sorszámot, amelyben a halmaz legkisebb indexű sorának a lehető legkisebb indexű oszlopában álló eleme szerepel (azaz a kisebb sor elsőbbséget élvez). Általánosan ha már sorszámot kapott az 1, 2, ..., i komponens, akkor az a komponens kapja az i + 1 sorszámot, amelyben az összes maradék komponens mezői közül a legkisebb sorszámhoz, döntetlen esetén ezek közül a legkisebb oszlopszámhoz tartozó szerepel. (Magyarul a mezők olyan rendezésével, ahogyan a bemeneti fájlban szerepel, az egyes komponensek első eleme szerint vannak rendezve a komponensek).
A kimeneti fájlnak N sora van, mindegyikben M egyész szám szerepel. Az egyes számok megfelelnek a sakktábla összes mezőjének a bemenettel megegyező sorrendben. Egy mezőhöz tartozó szám nulla, ha a mező nem eleme a bemeneti halmaznak, és i, ha eleme az i sorszámot kapott összefüggő komponensnek.
A feladathoz érdemes lehet megnézni a minta feladatok közül a 8. sorszámú feladatot.
Példa bemenetek és kimenetek (a kimenet a bemenethez egyértelműen meghatározott, ha egy program más kimenetet ad, akkor hibás vagy az, vagy az én programom).
Ebben a két feladatban egy permutációból elő kell állítanunk ennek a ciklusfelbontását standard formában, és viszont.
Minden permutáció előáll diszjunkt ciklusok kompozíciójaként. Vegyük például a 0 .. 7 számok következő permutációját:
3 1 7 2 6 0 4 5
Ebben permutációban 0-ás helyen a 3 áll, a 3-as helyen a 2, a 2-es helyen a 7, a 7-es indexű helyen az 5, az 5-ös helyen pedig a 0 áll. Ezért ennek a diszjunkt ciklusfelbontása a következő három ciklusból áll. A permutáció az 1-et helybenhagyja; a 6-ot felcseréli a 4-gyel.
(0 3 2 7 5) (1) (6 4)
A diszjunkt ciklusfelbontást ekvivalens módon felírhatjuk az egyértelmű standard alakban is, amikor is minden ciklus a benne szereplő legnagyobb elemmel kezdődik, és a ciklusok ezek szerint az első elemek szerint növekvő sorrendben állnak. Így tehát a fenti permutáció ciklusfelbontása standard alakban a következő.
(1) (6 4) (7 5 0 3 2)
Valóban, a hosszú ciklus legnagyobb eleme a 7, a csere legnagyobb eleme a 6, a helybenhagyásé az 1, így ezek állnak elől, és ezek szerinti csökkenő sorrendbe raktuk a három ciklust.
A standard alaknak érdekes tulajdonsága, hogy akkor is egyértelmű, ha a zárójeleket elhagyjuk belőle, például így.
1 6 4 7 5 0 3 2
Ebből az egybeöntött alakból meg lehet keresni az egyes ciklusok határát, és elő lehet állítani az eredeti permutációt.
A 4. és 5. feladatban olyan programot kell írnia, amely a ciklusfelbontás standard alakjából előállítja a permutációt, illetve fordítva, a permutációból előállítja a ciklusfelbontás standard alakját.
A programok a bemenetet a standard bemenetről olvassák be, a kimenetet a standard kimenetre írják ki. A program bemenete két (újsor jelre végződő) sorból áll. Az első sorban egyetlen egész szám áll, 1<=N<=30000. A második sorban szóközzel elválasztva N darab szám áll, mégpedig a 0, 1, ..., N-1 számok valamilyen sorrendben. A kimenet egy sorból áll, ebben szóközzel elválasztva N egész szám áll, szintén a 0, 1, ..., N-1 számok valamilyen sorrendben. (Az utolsó szám után nincsen szóköz; a számok fölösleges nullák nélkül vannak kiírva. Egy újsor karakter az egyetlen kimenet sor végén is van.)
A 4. feladatban a bemenetet egy diszjunkt ciklusfelbontás zárójelek nélküli standard alakjának kell tekinteni. Ki kell számítani a permutációt, amit ez a ciklusfelbontás meghatároz, és a kapott permutációt kiírni a kimenetre.
Hasonlóan az 5. feladatban a bemenet egy permutációnak tekintendő, ennek határozzuk meg a diszjunkt ciklusfelbontását, és írjuk ki ezt standard alakban zárójelek nélkül.
Bármely szabályos bemenethez a kimenet mindkét feladatban egyértelmű, vagyis ha két program eredménye eltér, akkor az egyik hibás.
Példa bemenetek és kimenetek a 4. feladathoz.
Az 5. feladathoz.