Utolsó módosítás: 2008. november 19.
A feladatokat november 5-n tűztem ki. Az öt feladatból kettőt mindenkinek kötelező beadni legkésőbb november 20. csütörtökig (mivel 19. tanítási szünet). Több feladatot is be lehet adni november 26. szerdáig, ezek az érdemjegybe beleszámítanak. A feladatokat és a megfelelő mintákat azonban még korábban is érdemes legalább elolvasni, mivel a versenyen ezekhez nagyon hasonló feladatokat is fel fogok adni.
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 s1/s1f2be0 fájl lett.
Most tegyük fel, hogy erre a feldatatra ír egy megoldást,
amit a s1f2.c C nyelvű forrásfájl alkot,
és ezt lefordította a
gcc -std=c99 -W -Wall -pedantic-errors -O -lm -o s1f2 s1f2.c
paranccsal.
Ha a fordítás sikeres, a 0. teszt bemenetet átirányíthatja a program
standard bemenetére a ./s1f2 < s0/s1f2be0 paranccsal,
és ekkor ugyanazt kell kapnia,
mint ami az s1/s1f2ki0 kimenetben áll.
Rögtön is ellenőrizheti az egyezést a
./s1f2 < s1/s1f2be0 | diff -q - s1f2ki0 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 s1/s1f2be*; do ./s1f2 < "$x" | diff -q - ${x/be/ki}; done .
A 0. mintafeladatsor 9. feladatában előállítottuk egy szám prímfelbontását. Ebben a feladatban ugyanezt kell tenni, csak a kimenet formája tér el. Kiindulhat a mintafeladat kódjából, vagy írhat teljesen új kódot is.
Változtatás: a mintapéldában megadott forráskódban volt egy hiba, egy fölösleges sor, amitől a forráskód nem is fordult le. Ezt november 19-én kijavítottam.
A kimenet formája abban különbözik, hogy a prímosztókat növő helyett csökkenő sorrendben írjuk ki, a számot magasabb hatványon osztó prímosztókat többször írjuk ki (nem pedig kitevővel), és csak szóközzel választjuk el a prímosztókat.
A program bemenete, amelyet a standard bemenetről olvas be, egyetlen egész szám 2 és 100000000 között (decimális formában), amelyet egy újsor karakter követ.
A program kimenete a bemenet (pozitív) prímosztóit sorolja fel csökkenő sorrendben. Mindegyik prímosztó pontosan annyiszor van megismételve a kimenetben, hogy a kimenetben szereplő számok szorzata a bemenet legyen.
A kimenetben a számok decimális formában szerepelnek (fölösleges nullák és előjelek nélkül), két szomszédos számot egyetlen szóköz választ el, a sort egy újsor karakter zárja le, amely előtt nincs szóköz. A kimenetet a standard kimenetre kell írni.
Íme néhány példabemenet és kimenet. 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.
A lights out egyszemélyes táblás játék egy változatát fogjuk megoldani.
A lights out játék egy négyzetrácsos táblából áll. Minden mezőn egy világítós nyomógomb van. A gombnak két állapota van: vagy világít, vagy nem.
Ha megnyomunk egy gombot, akkor az a gomb és a négy élszomszédos mező állapota megváltozik, tehát mind az öt gombra az igaz, hogy ha korábban világított, akkor most elalszik, ha nem világított, akkor felgyullad.
A tábla azonban véges, így egyes mezőknek öt helyett csak négy vagy három élszomszédja van.
A játék célja egy bizonyos állapotból elérni, hogy minden lámpa elaludjon.
Esetünkben a tábla alapja egy csonka téglalap. Pontosabban a tábla majdnem egy R sor magas és C oszlop széles téglalap, csakhogy az utolsó sorban az utolsó M mező hiányzik. A hiányzó (táblán kívüli) mezőkön sem gomb, sem lámpa sincs, tehát megnyomni sem szabad, de az állapotuk sem lényeges.
Például ha R = 6, C = 5, M = 2, akkor a tábla így néz ki.
X X X X X X X X X X X X X X X X X X X X X X X X X X X X
Nyilvánvalóan mindegy, hogy a gombokat milyen sorrendben nyomjuk meg, és minden gombot legfeljebb egyszer érdemes megnyomni. Így aztán egy megoldást úgy adunk meg, hogy minden mezőhöz megadunk egy 0 vagy 1 számot; a 0 azt jelenti, hogy a gombot nem nyomjuk meg, az 1 pedig azt, hogy megnyomjuk.
Például tekintsük a következő nyomogatást.
1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
Ha ezt végrehajtjuk, akkor az alábbi táblázatban csillaggal jelölt mezőkön változik meg a lámpa értéke.
* * * . . * * * * . . . * * . . . * * . . . . . * . . .
Ebben a feladatban abból az állapotból indulunk ki, amikor minden lámpa ég, és azt kell elérni, hogy egyik lámpa se égjen. Olyan megoldást kell tehát adni, ami a táblán minden lámpa állapotát megváltoztatja. Csak olyan (R, C, M) hármasokat fogunk vizsgálni, amire ilyen megoldás van és egyértelmű.
Kap azonban egy segítséget. A bemenetben megadom a megoldás első sorát, tehát az első sor minden gombjáról megmondom, hogy meg kell-e nyomni. Ebből aztán a többi sort már nagyon könnyű kiszámolni.
A program bemenete két sorból áll. Az első sor három természetes számot tartalmaz szóközzel elválasztva, ezek R, C, M. Feltehetjük, hogy 3 <= R <= 14; 3 <= C <= 14; és 0 <= M <= C - 2. A második sorban C természetes szám áll, mindegyik nulla vagy egy, ez megadja az egyértelmű megoldásból a tábla felső sorára vonatkozó részt.
A kimenet R sorból áll, az utolsó sorban C - M szám, a többiben C szám áll szóközzel elválasztva. Mindegyik szám nulla vagy egy. A kimenet a lights out probléma megoldását adja meg a megfelelő alakú táblára a fentebb leírt formában. Ha tehát az egyessel jelölt gombokat megnyomjuk egy ilyen játékon, akkor az összes lámpa állapota megváltozik. A kimenet első sora tehát megegyezik a bemenet második sorával.
A program a bemenetét a standard bementről olvassa be, a kimenetet a standard kimenetre írja. A bemenetben és a kimenetben is minden sor végén egy újsor karakter áll (az utolsó sor végén is tehát). Az egy soron belüli számokat egy szóköz választja el, de az első szám előtt és az utolsó szám után nincs szóköz. A számok decimális formában vannak.
Itt van néhány bemenet és kimenet példának. (Minden bemenethez csak egy helyes kimenet tartozik, ha két kimenet bármiben különbözik, akkor az egyik hibás.)
Az 1. mintafeladatsor 6. feladatában egy egyszerű körlevél író programot készítettünk. Észrevehetjük azonban, hogy az ott bemutatott példa körlevélben néhány változó mező (a név és a dátum) többször szerepel, ezeket így a bemenetbe többször is be kell írni. Ebben a feladatban ezért úgy kell módosítania a programot, hogy egy mezőt automatikusan be tudjon másolni a levél több részére.
Ehhez a bemenet formáját úgy módosítjuk,
hogy a sablonban a közönséges @i jelző mellett megengedünk
visszautaló jelzőket is, mint @0, @1, ….
Ezekhez a jelzőkhöz a rekordban nem tartozik újabb mező,
hanem ugyanabból a rekordból egy korábbi közönséges mező értékét ismétlik meg.
A pontos szabályok a következők.
A program bemenete a következő részekből áll:
először a sablon,
majd a sablont lezáró elválasztó jelzés,
majd egy vagy több behelyettesítendő adatsor (rekord),
majd egy, az adatsorokat lezáró jel következik.
A sablon egy vagy több sorból álló szöveg,
amelyben néhány helyen a @ karakterből és még egy karakterből álló
mező jelzés szerepel.
Egy mező jelzés lehet közönséges, ennek a formája @i,
vagy visszautaló, ennek a formája a @ jel és egy számjegy
(0-tól 9-ig).
A sablon utolsó karaktere egy újsor jel, ami a sablonhoz hozzátartozik.
A sablont lezáró jelzés a $ karakter, majd egy újsor jel,
ezek nem tartoznak a sablonhoz.
Minden rekord, ami egy levelet határoz meg, egy megnyitó jelzéssel kezdődik,
ami egy 1-es számból majd egy újsor jelből áll.
Ezt követően a rekordnak még annyi sora van,
ahány közönséges mező jelző a sablonban található,
mindegyik sor egy mezőt határoz meg.
Minden ilyen mező tehát pontosan egy sorból áll, amelyet újsor karakter zár le,
azonban az újsor karakter a mező értékéhez nem tartozik hozzá.
Végül az utolsó rekord után a fájlban egy lezáró jelzés következik:
egy 0-ás szám és egy újsor jel.
A sablon legfeljebb (beleértve a mező jelzéseket is) 10000 karakter hosszú,
összesen legalább egy de legfeljebb 50 mező jelzés található benne.
A rekordokban minden sor legfeljebb 4000 karakter hosszú (a lezáró újsort is beleszámítva).
A sablonban és a rekordokban nem szerepel a $ karakter, nul karakter;
és a @ karakter is csak a sablonban és csak mező jelölő részeként fordul elő.
A bemenetet a standard bemenetről olvass a program,
a kimenetet a standard kimenetre írja.
A program kimenete levelekből áll: minden rekordhoz egy levél tartozik,
a rekordokkal megegyező sorrendben.
Egy levelet úgy kapunk,
hogy a sablonban a rekord jelölőket eltávolítjuk,
és a helyükre beillesztjük a megfelelő mező értékét (a mezőket lezáró újsor jel nélkül).
A közönséges mező jelölőkhöz minden mezőt pontosan egyszer használunk föl,
ugyanolyan sorrendben, ahogyan a rekordban is követik egymást.
A visszautaló mezőjelző helyére újra beszúrjuk azt a sorszámú mezőt (nullától kezdve),
ahányas számjegy a jelölőben szerepel;
ennek a mezőnek megfelelő közönséges mezőjelölő mindenképpen
a visszautaló jelölő előtt szerepel a sablonban.
Noha lehet tíznél több mező, csak az első tízre lehet tehát visszautalással is hivatkozni:
@0 az elsőre hivatkozik, @1 a másodikra, sít.
@9 a tizedkire;
de ebbe a tízbe a visszautalással megismételt mezők nem számítanak bele,
csak a korábbi közönséges mezőjelölők által beszúrt mezők.
Az egyes levelek elválasztó nélkül követik egymást.
Íme néhány bemenet és kimenet példának.
Figyelem! A korábbi kimenetek hibásak voltak. Most már remélhetőleg helyesek itt is és a SIO rendszeren is. (november 12.)
A feladat megoldásához érdemes az s1f6 feladatot megoldó s1f6.c programból kiindulni, de akár írhat teljesen új programot is. Ha nem is oldja meg ezt a feladatot, legalább megnézni mindenképpen érdemes, mert a versenyen is fel fogok adni egy olyan feladatot, amiben a körlevél író program egy másféle módosítását kell megírni.
Ez a feladat az 1. mintafeladatsor 7. feladatának egyszerű módosítása. Természetesen az ahhoz tartozó mintamegoldásból érdemes kiindulni. Abban a feladatban egy listából kikeressük azokat a szavakat, amik egy másik listában nincsenek benne. Ebben a feladatban ki kell írni ezen kívül a két lista közös szavait is, és azokat a szavakat is, amik az első listában vannak benne, de a másodikban nem.
A bemenet (amit a program a standard bemenetről olvas be) két részből, és köztük egy üres sorból áll. Mindkét részben minden sorban egy angol szó szerepel, minden szó legfeljebb 15 betű hosszú, és csak az angol ábécé kisbetűiből áll. (A szavak után újsor jel áll, ez a 15 betűbe nem számít bele.)
A program kimenete (amit a standard kimenetre ír) három részből áll, ezeket egy-egy üres sor választja el. Mindhárom részben szintén soronként egy szó szerepel, amiket a bemenetből pontosan kell átmásolni. Az első rész azokból a szavakból áll, amik a bemenet második részében szerepelnek, de az első részében nem. A szavaknak olyan sorrendben kell szerepelnie, ahogyan a második listában szerepel. A második rész azokból a szavakból áll, amik mindkét listában szerepelnek. Ezeket szintén olyan sorrendben kell kiírni, ahogyan a második listában szerepelnek (az első lista sorrendjétől függetlenül). Végül a harmadik rész azokból a szavakból áll, amik az első listában vannak benne, de a másodikban nem. Ezeket olyan sorrendben kell kiírni, ahogyan az első listában szerepelnek.
A bemenetben mindkét részben külön-külön legfeljebb 12000 szó lehet. Egy részen belül egy szó nem szerepel kétszer. A szereplő szavaknak körülbelül egy harmada mindkét listában benne van, harmada csak az első, harmada csak a második listában. Mindkét lista összevissza sorrendben van.
Íme néhány példa.
Ez a feladat az 1. mintafeladatsor 8. feladatának kissé bonyolultabb változata. Ebben egy helyett két kígyó mozog egy pályán, és a játék véget ér, ha a kígyók a pálya szélébe, saját magukba, vagy egymásba ütköznek bele.
A feladat megoldásához érdemes a mintafeladatnál megadott s1f8.c mintamegoldásból kiindulni. A feladat kiírását itt nem is ismétlem meg teljesen, csak a változásokat ismertetem.
A játék ugyanakkora táblán zajlik, mint a mintafeladatban, ezúttal azonban a pályán két kígyó van. A kígyók kezdőhelyzete a következő: az első kígyó a 3 indexűből sorból indul, a második kígyó a 6 indexűből (ne felejtsük el, hogy a sorokat nullától kezdve számozzuk). Mindkét kígyó 9 hosszú, és a kezdőhelyzetben ennek a sornak a 0 indexű oszlopától a 8 indexű oszlopáig ér, a feje a 8 indexű oszlopban van, tehát az első lépés előtt jobbra mozognak.
A kígyók felváltva lépnek: az első lépésben csak az első kígyó lép, a következőben a második kígyó, aztán megint az első, stb. A bemeneten minden lépéshez tartozik egy szám (-1, 0, vagy 1, mint a 8. mintában), ez csak arra a kígyóra vonatkozik, amelyik a megfelelő lépésben lép. A bemenet most nem 200, hanem 400 lépést ad meg.
A játék egy lépésben véget ér, ha annak a kígyónak a feje, amelyik az adott lépésben mozgott, a táblán kívülre kerül, olyan mezőre, amit ugyanennek a kígyónak egy másik része foglal el, vagy amit a másik kígyónak bármelyik része elfoglal.
Íme néhány bemenet és kimenet.