Utolsó módosítás: 2008. november 5.
Az összes nyilvános példa bemenetet és kimenetet és a forráskódokat (a heti házi feladatokéval) egyben le lehet tölteni:
Ebben a feladatban olyan programot írunk, amely körlevelet ír egy sablon és a behelyettesítendő adatok alapján. A sablon egy egyszerű szöveg, amiben van néhány jelzés, ami a körlevél változó tartalmát helyettesíti. A bemenet tartalmaz még a levél minden példányához épp annyi behelyettesítendő szöveget, ahány ilyen jelzés van a sablonban. A program ez alapján elkészíti a körlevél több példányát.
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 @i két karakterből álló mező jelzés szerepel.
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 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ú,
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). Minden mezőt pontosan egyszer használunk föl, ugyanolyan sorrendben, ahogyan a rekordban is követik egymást. Az egyes levelek elválasztó nélkül követik egymást.
A feladathoz itt van egy bemenet és kimenet példának.
Nézzük most meg az s1f6.c programot, ami ezt a feladatot oldja meg.
#include#include #include
Először definiáltam egy segédfüggvényt, amelyet bizonyos hibák esetén fogunk meghívni.
void
die(char *msg) {
fprintf(stderr, "%s\n", msg);
exit(1);
}
A hibakezelés nem lesz teljes: bizonyos hibás bemeneteket elfogadunk, és bizonyos hibaüzenetek két–három különböző hibához tartoznak. Mindenesetre a hibák így is segíthetnek a hibás bemenetek diagnosztizáláshoz. (Gyakorlásként a kód többi részében számolja, hány sort olvastunk be, és módosítsa ezt a függvényt úgy, hogy kiírja, a bemenet hányadik sora hibás.)
Ez után következik a sablon beolvasása.
#define TEMPLATE_MAXLEN 10100 char template[TEMPLATE_MAXLEN];
A sablont és az elválasztót változatlanul, folyamatosan fogjuk beolvasni ebbe a tömbbe. A sablonról más információt (mint a sablon hossza vagy a jelölők pozíciói) nem tárolunk el külön, és a sablon végét is később csak az elválasztó eltárolt dollárjeléről fogjuk felismerni. A következő függvény olvassa be a sablont és az ezt követő elválasztót.
void
read_template(void) {
int stop = 0;
size_t pos = 0;
while (!stop) {
if (
TEMPLATE_MAXLEN - pos < 2 ||
!fgets(template + pos, TEMPLATE_MAXLEN - pos, stdin)
)
die("error reading template");
if ('$' == template[pos])
stop = 1;
else
pos += strlen(template + pos);
}
template[pos] = 0;
}
A sablont soronként olvassuk be az fgets függvénnyel.
Mivel a sablon utáni elválasztó újsor jelre végződik,
nem olvashatunk be véletlenül túl sokat a fájlból;
mivel pedig az elválasztó előtt a sablon utolsó karaktere is biztosan újsor jel,
az elválasztót elég a sor elején keresni.
Vegyük észre, hogy a sorok tartalmát folytonosan egymás után tároljuk,
ezért a következő fgets hívás mindig felülírja
az előző hívás által tárolt 0 karaktert.
Az fgets hívás előtt ellenőrizzük, van-e még elég hely a bufferben (legalább két karakter).
A következő függvény beolvassa a rekord elején lévő jelölő sort, vagy a rekordok utáni végső jelölőt. A függvény ez alapján a visszatérésével jelzi, hogy kell-e még olvasni valamit, vagy már nincs több rekord.
#define LINE_MAXLEN 4010
char
line[LINE_MAXLEN];
int
more_mail(void) {
if (!fgets(line, LINE_MAXLEN, stdin))
die("error reading record head");
if ('0' == line[0])
return 0;
if ('1' == line[0])
return 1;
die("error: record head has wrong format");
}
Ez után következik az érdekes rész: a következő függvény beolvassa a rekord mezőit (ha a rekordot kezdő jelölő már be van olvasva), miközben végigmegy a sablonon és kiírja a levelet.
void
process_mail(void) {
size_t pos;
size_t len;
for (pos = 0; '$' != template[pos]; pos++) {
if ('@' == template[pos]) {
if ('i' != template[++pos])
die("error: field marker has wrong format");
if (!fgets(line, LINE_MAXLEN, stdin))
die("error reading record body");
len = strlen(line);
line[len - 1] = 0;
fputs(line, stdout);
} else
putchar(template[pos]);
}
}
A ciklus az eltárolt sablonon megy végig. A ciklus akkor ér véget, ha eljutottunk a dollárjel karakterig. A kukactól különböző karaktereket egyenként kiírjuk.
Ha kukacot találunk, akkor beolvasunk egy mezőt a bemenetről, és kiírjuk.
A mező végén lévő újsor jelet egy nul karakterrel írjuk felül,
így az fputs függvény ott megáll a kiírással,
tehát az újsor jelet nem írjuk ki.
Ezen kívül a sablonban átugorjuk a kukac utáni i karaktert.
Vegyük észre, hogy a rekordnak egyszerre csak egy sorát tartjuk a memóriában.
Gyakorlásként írja át ezt a függvényt úgy,
hogy a sablon karakterein ne egyenként haladjon végig,
hanem a strchr vagy a strcspn könyvtári függvénnyel
keresse meg a következő mező jelölőt,
és a két jelölő közti részt (illetve az első jelölő előtti és az utolsó jelölő utáni részt)
egyszerre írja ki
az fwrite vagy fputs vagy printf függvénnyel.
Végül a main függvény következik:
ennek csak össze kell raknia az előző három függvényt.
int
main(void) {
read_template();
while (more_mail())
process_mail();
return 0;
}
Ezt a feladatot érdemes megérteni, mivel az első versenyen előfordulhat olyan feladat, ami ezen alapul.
Ebben a feladatban a bemenet két lista lesz, amik angol szavakból állnak, és meg kell határoznunk a két lista különbségét, vagyis azon szavakat a második listából, amik az első listában nincsenek benne.
A bemenet 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 kimenetére azokat a szavakat kell kiírni, 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. Minden sorba egy szót kell írni.
A bemenetben mindkét részben külön-külön legfeljebb 12000 szó lehet. 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.
Nézzünk néhány példát.
Nézzük meg a következő mintamegoldást.
Letöltés: s1f7.c.
Ahhoz, hogy ezt a feladatot hatékonyan megoldjuk, legalább az egyik listát úgy kell eltárolnunk, hogy hatékonyan kereshessünk benne. Így aztán a megoldás ábécé sorrendbe rendezi az első halmazt.
Először beolvassuk az első lista szavait. A szavakat egy kétdimenziós tömbbe (mátrixba) olvassuk be, vagyis minden szóra ugyanakkora helyet foglalunk. Mivel a szavak hosszára rövid korlát van, ez itt nem túl nagy pazarlás. (Ha ezt nem akarnánk, akkor egyszerűen egy egy dimenziós karakter tömbbe folyamatosan olvasnánk be a szavakat, és később a sorindexek helyett a szavak első betűinek az indexét használnánk. Gyakorlásként próbálja meg átírni ilyen módon a programot.)
Vegyük még észre, hogy a sorok utáni újsor jelet a szavak után meghagyjuk: ez nem befolyásolja a szavak összehasonlítását, és a szavakat amúgy is újsor jellel fogjuk kiírni.
#include#include #include #define WORD_BUFLEN 20 #define SET_MAXNUM 12000 char words_a[SET_MAXNUM][WORD_BUFLEN]; int size_a; void readset_a(void) { size_a = 0; while ( fgets(words_a[size_a], WORD_BUFLEN, stdin) && 1 < strlen(words_a[size_a]) ) { size_a++; if (SET_MAXNUM <= size_a) exit(1); } }
Ezután rendezzük a szavakat. Az egyszerűség kedvéért nem magukat a szavakat (a mátrix sorait) mozgatjuk, csak egy másik tömbben az indexeket.
Az order_a tömböt tehát először feltöltjük a szavak sorindexeivel
a words_a tömbbe,
majd ezeket az indexeket rendezzük úgy, hogy a velük indexelt szavakat használjuk kulcsként.
A rendezés itt használt algoritmusa a közvetlen összefésülő rendezés. Ez úgy működik, hogy rendezzük a tömb első felét, majd a tömb második felét, ez után pedig a két rövidebb rendezett tömböt összefésüljük úgy, hogy az egész nagyság szerint legyen rendezve.
int
order_a[SET_MAXNUM];
int
merge_buf[SET_MAXNUM];
void
merge(int start, int mid, int end) {
int p = start, q = mid, r = 0, k;
while (p < mid && q < end)
if (strcmp(words_a[order_a[p]], words_a[order_a[q]]) < 0)
merge_buf[r++] = order_a[p++];
else
merge_buf[r++] = order_a[q++];
if (p < mid)
for (k = mid - 1; p <= k; k--)
order_a[end - mid + k] = order_a[k];
for (k = 0; k < r; k++)
order_a[start + k] = merge_buf[k];
}
void
sort_part(int start, int end) {
if (end <= start + 1)
return;
int mid = start + (end - start)/2;
sort_part(start, mid);
sort_part(mid, end);
merge(start, mid, end);
}
void
sort(void) {
int i;
for (i = 0; i < size_a; i++)
order_a[i] = i;
sort_part(0, size_a);
}
Most következzen az a függvény,
ami bináris kereséssel megkeres egy szót ebben a rendezett tömbben.
A függvény felteszi,
hogy a szó a word_b tömbbe van tárolva (az újsor jellel együtt),
és visszatérési értékével jelzi, megtalálta-e a szót.
A bináris keresés úgy működik, hogy a keresett szót a rendezett tömb középső szavával hasonlítjuk össze. Ha a keresett szó a középső szónál kisebb ábécé sorrend szerint, akkor a tömbben csak az előtt az elem előtt, tehát az első felében lehet, ha pedig nagyobb, akkor csak a második felében. A következő lépésben már csak a tömb fele akkora méretű részében kell keresnünk. Mivel minden lépésben fele akkora lesz a tömb vizsgálandó része, nagyon hamar eljutunk a keresés végéig.
char
word_b[WORD_BUFLEN];
int
search(void) {
int start = 0, end = size_a, mid;
int cmp;
while (start < end) {
mid = start + (end - start)/2;
cmp = strcmp(word_b, words_a[order_a[mid]]);
if (cmp < 0)
end = mid;
else if (0 < cmp)
start = mid + 1;
else
return 1;
}
return 0;
}
Végül jöjjön a main függvény. Ez először beolvassa az első listát (és az utána következő üres sort is), majd végrehajtja a rendezést, majd a második lista minden szavát is beolvassa, azonnal megkeresi az első tömbben, és amelyik szót nem találja meg, azt kiírja.
int
main(void) {
readset_a();
sort();
while (fgets(word_b, WORD_BUFLEN, stdin))
if (!search())
fputs(word_b, stdout);
return 0;
}
Ebben a mintában azt a játékot kell szimulálni, amiben a játékos egy hosszú kígyóval fel-alá mászkál egy pályán, és megpróbálja elkerülni, hogy a kígyó a pálya szélébe vagy a saját farkába ütközzön. A program bemenete megadja a játékos által kiadott parancsokat, a program pedig kiszámítja, mikor ér véget a játék.
A játék egy 10 mező magas és 20 mező széles sakktáblán zajlik. A mezőket koordináapárok azonosítják, ezeken az első koordináta (0-tól 9-ig) a sort, a második (0-tól 19-ig) az oszlopot jelöli. A bal felső mező koordinátája (0, 0), a jobb alsóé (9, 19).
A pályán található egy kígyó, ami 9 részből áll, minden rész egy mezőt fed le teljesen. A részek sorrendje is számít: a kígyónak az egyik vége a feje, a másik a farka. A kígyó bármelyik része mindig az előző és következő részekkel szomszédos mezőn található. Kezdetben a kígyó részei rendre az (5, 0), (5, 1), … (5, 7), (5, 8) mezőkön találhatók, a kígyó farka az (5, 0), feje az (5, 8) mezőn. A kígyó úgy mozog, hogy a farki végéről az utolsó rész elhal, a feji végén pedig egy új rész nő ki a régi fejjel szomszédos egyik mezőn. Ha tehát a kígyó a kezdeti pozíciójából fölfele lép egyet, akkor ezután a részei a farkától a fejéig az (5, 1), (5, 2), … (5, 7), (5, 8), (4, 8) mezőkön lesznek.
A kígyó négy irányba tud mozogni, jobbra, föl, balra, és le, ekkor az új fejet úgy kapjuk meg, hogy az előző fej mezőjét rendre (0, 1), (-1, 0), (0, -1), (1, 0) vektorral eltoljuk. A kígyónak mozgásának mindig van egy iránya is, ez az utolsó lépés iránya, vagy ekvivalens módon az az irány, amerre a fejtől nézve a második részből a fej látszik. A kezdeti állapotban az első lépés előtt ez az irány a jobbra. A játékos úgy irányítja a kígyót, hogy minden lépésben megmondja, a kígyó az előző mozgás irányához képest merre fordul: mehet ugyanarra (ezt a 0 szám jelöli), fordulhat az óramutató járásával ellenkező irányban (ezt az 1 szám jelöli), vagy megegyező irányban (amit a -1 szám jelöl). Ha például a játékos a kígyót az óramutató járásával ellenkező irányban forgatja el, és ez előző lépésben a kígyó jobbra mozgott, akkor a következő lépésben fölfele fog lépni. (Nem engedjük meg, hogy a kígyó egy lépésben megforduljon, mert ekkor mindig összeütközne magával.)
A program bemenete egy sorból áll, ami 200 számot tartalmaz, ezek mindegyike -1, 0, vagy 1, ezek a játékos választását adja meg az egyes lépésekben. Ha például a sorban az első szám -1, akkor a kígyó az első lépésben az óramutató járásával megegyező irányba fordul, mivel pedig a kezdőhelyzetben jobbra mozgott, most lefele fog mozogni, így tehát a feje a (6, 8) mezőre kerül.
Ha a kígyó feje egy lépés után a táblán kívülre kerül, vagy ugyanarra a mezőre, amit egyszerre a kígyó egy másik része is elfoglal, akkor a játék véget ér. Ilyenkor a játékos későbbi választásait nem kell figyelembe venni. Minden lépésben tehát a programnak el kell törölnie a kígyó farokrészét, meg kell változtatnia a kígyó mozgásának az irányát a játékos választásának megfelelően, lerakni egy új részt a fejétől az új mozgás irányába, majd ellenőriznie, szabad mezőn van-e ez a fej.
A program kimenete egy sorban egyetlen egész szám, ami megadja a lépések számát a játék vége előtt. Azt az utolsó lépést, amiben a kígyó feje (a tábla szélének vagy a saját farkának) ütközik, még bele kell számolni a számításba. (A szám után újsor jelnek kell következnie.) Felteheti, hogy a játék még a bemenetben megadott lépéseken belül véget ér.
Ha például a kígyó az első három lépés mindegyikében az óramutató járásával megegyezően fordul, akkor a harmadik lépésben a feje az előző fejtől fölfelé, az (5, 7) mezőre kerül, itt viszont még a kígyó fejétől számított negyedik rész van, ezért a játék három lépés után véget ér, a kimenet tehát 3. Ezt a példát mutatja az alábbi 0. sorszámú példa bemenet. Lássuk tehát az összes példa bemenetet.
Itt tölthető le a mintamegoldás (de az archívumban is benne van): s1f8.c.
Ezt a kódot nem kommentálom részletesen, remélem, hogy anélkül is elég világos. Annyit jegyeznék csak meg, hogy a kígyó részeinek elhelyezkedése mellett tárolok egy olyan táblázatot is, ami a sakktábla minden mezőjére megmondja, van-e ott a kígyóból. Ez egyszerűsíti az ütközés ellenőrzését, mert nem kell a kígyó minden korábbi részét megnézni.