Utolsó módosítás: 2008. december 12.
Ez a feladatsor a pótverseny egyetlen, december 12. péntek délutáni turnusához tartozik.
Le lehet tölteni az összes példa be- és kimenetet és példa forráskódot egyben: z6p.tgz vagy z6p.zip.
A feladatok nem feltétlenül nehézségi sorrendben vannak.
Ebben a feladatban egyszerűen ki kell törölni egy szóból egy betű összes előfordulását.
A bemenet két sorból áll. Az első sorban egyetlen nagybetű áll. A második sorban egy (hosszú és általában értelmetlen) szó áll, ami csupa nagybetűkkel van írva.
A kimenet egyetlen sorába ugyanazt a szót kell kiírni, mint ami a második sorban szerepel, csak el kell belőle hagyni annak a betűnek az összes előfordulását, amit az első sor megad. A sor után újsor jelet kell írni. (Lehetséges, hogy a betű egyáltalán nem szerepel a szóban, ilyenkor persze a szót változatlanul kell kiírni. A bemenetben a szó legfeljebb 1200 betűt tartalmaz.)
Egy példát nézzünk. A bemenet ez.
A HATAKAMATAPATRATACSINBUMM
A kimenet
HTKMTPTRTCSINBUMM
Több példa letölthető.
Elővettem egy doboz kefirt a hűtőszekrényből, és el szeretném dönteni, lejárt-e vagy sem.
A dobozon van szavatossági dátum, de ez az évet nem tünteti fel, csak a hónapot és a napot. Szerencsére ez is elég, mert annyira régi kefir nincs a hűtőszekrényemben, hogy az év is kérdéses legyen.
A program bemenetként megkapja a mai nap dátumát (tehát azt a napot, amikor a kefirt meg szeretném enni), és a lejárati dátumot a csomagolásról. Úgy tekintjük, hogy a kefir akkor romlott meg, ha a lejárati dátuma korábbi, mint a mai dátum. Ha a lejárati dátum megegyezik a mai dátummal, vagy későbbi, akkor a kefir még jó. Felteheti, hogy ha a kefir még jó, akkor a mainál legfeljebb 31 nappal későbbi dátum van rajta, míg ha lejárt, akkor a mainál legfeljebb 61 nappal korábbi.
A bemenet első sora a tesztesetek számát tartalmazza (legfeljebb 1000).
Az ez utáni összes sor mind egy-egy tesztesetet tartalmaz,
mégpedig előbb a mai dátumot, majd a szavatossági dátumot.
Mindkét dátum úgy van megadva, hogy először a hónap áll két számjeggyel,
aztán egy minusz jel (-), majd a nap két számjeggyel.
Például 12-04 december negyedikét jelent.
A két dátum között egy szóköz áll, a sor végén pedig egy újsor jel.
A kimenetben minden tesztesethez egy sort kell írni, amiben egy szám áll. A szám 1 ha a kefir még friss, 0 ha már lejárt.
Nézzünk egy példát. A bemenet ez.
10 09-14 09-14 07-10 08-01 04-11 04-18 04-10 03-19 09-12 08-28 08-31 09-27 07-08 05-27 01-28 12-02 12-24 01-06 02-16 03-14
A kimenet pedig a következő.
1 1 1 0 0 1 0 0 1 1
Hátulról a második sorban a januári lejárati dátum későbbi, mint a decemberi aktuális dátum, ezért a kefir friss. Ezzel ellentétben hátulról a harmadik sorban januárban bontunk fel egy decemberi kefirt, így ez már lejárt.
Itt van a hosszabb bemenet is.
Adott számok egy listája, a programnak ezeket kettes csoportonként külön veszi, a párok első tagjából kivonja a másodikat, és minden párhoz kiír egy nullát, ha a különbség negatív, vagy a különbséget, ha az nemnegatív.
A program bemenete egyetlen soros, ebben pontosan hatvan (60) nemnegatív egész szám áll (mindegyik legfeljebb 100), legyenek ezek a0, a1, … a59. A program kimenete harminc darab egész szám, mégpedig az max(0, a0 - a1), max(0, a2 - a3), … max(0, a58 - a59) sorozat.
A be- és a kimenetben is a számokat szóköz választja el, a sor végén nincs szóköz, de újsor karakter van. A kettes csoportokat átfedés nélkül, de kihagyás nélkül kell képezni az egymás utáni számokból.
Például ha a bemenet a következő hosszú sor
69 7 8 28 18 92 61 41 24 9 72 56 64 70 22 78 88 100 36 49 53 70 53 85 35 87 18 72 99 74 30 99 19 72 10 100 59 9 99 80 27 56 42 71 94 51 64 47 12 23 9 30 13 91 71 61 18 5 4 60
akkor a kimenet
62 0 0 20 15 16 0 0 0 0 0 0 0 0 25 0 0 0 50 19 0 0 43 17 0 0 0 10 13 0
mivel az első pár különbsége 69 - 7 pozitív, míg a második különbség 8 - 28 negatív lenne.
Még pár példa.
Ebben a feladatban össze kell nyomnia egy szót, amiben sok helyen áll sok egyforma betű egymás után.
A program bemenete egy sorból áll, amiben egy csupa nagybetűkből álló (általában értelmetlen) szó szerepel. Ebben a szóban gyakran előfordul, hogy egy betű egymás után sokszor ismétlődik.
A kimenetben olyan leírását kell adnia a szónak, amiben az ismétlődő betűk csak egyszer szerepelnek, de közvetlenül előtte számmal megadja az ismétlődés számát. A számot minden betű előtt használni kell, tehát ha egy betű nem ismétlődik, akkor is egy 1-est kell elé írni. Az ismétlések számát tizes számrendszerben, a lehető legkevesebb számjeggyel kell leírni.
A kimenetben tehát felváltva szerepelnek számok és betűk, de a számok néha egynél több számjegyből is állhatnak. A kimenetben egy betű nem szerepelhet kétszer egymás után (köztük számmal), mert akkor a két csoportot össze lehetne vonni, de egymástól távolabb szerepelhet ugyanaz a betű. Természetesen a 0 szám nem szerepelhet sehol. Az egyes csoportok közé nem kell semmilyen elválasztót írni, de a kimenet végére egy újsor jel kell. A bemenet legfeljebb 1200 betű hosszú.
Például a BOOKKEEPER szót úgy rövidítenénk, hogy 1B2O2K2E1P1E1R. Egy kicsit hosszabb bemenet a következő.
NRRTYYYYYOAAAANQQCCCCCCCF
Ehhez a következő kimenet tartozik.
1N2R1T5Y1O4A1N2Q7C1F
A fenti példa nem mutatja azt az esetet, amikor egy számot több számjeggyel kell leírni – kétjegyű számra a ki3, ki4, ki5 kimenetek adnak példát, háromjegyűre a ki5 példa. Ezeket itt lehet letölteni.
Ebben a feladatban szavak egy listájából ki kell írni minden szónak az első előfordulásőt.
A program bemenete sok (legalább 1, legfeljebb 16000) sorból áll, minden sorban egy legfeljebb 15 betűs angol szó (és egy újsor jel) áll.
A kimenetben is soronként egy szó szerepel, mégpedig csak olyan szavak, amik a bemenetben is szerepelnek. Minden szó pontosan egyszer kell, hogy bekerüljön a kimenetre, akkor is, ha a bemenetben több példányban szerepel (akár egymás után, akár egymástól messze). A szavakat olyan sorrendben kell kiírni, ahogy a bemenetben először előfordulnak.
Figyelem, a legnagyobb bemenet nagy: 16000 soros. A megoldásnak a nagy bemenetre is le kell futnia ahhoz, hogy helyesnek számítson.
A programot ruby nyelven érdemes megírni. A bemenet sorain egyesével menjen végig, és mindegyiket rögtön írja is ki, de csak akkor, ha korábban már nem szerepelt. Azt, hogy mely szavak szerepeltek már, egy asszociatív tömbbe (Hash) jegyezze fel, ahol a kulcsok a szavak, az értékek tetszőlegesek. (Ha nem emlékszik, hogy működnek az asszociatív tömbök, az s2f6 mintafeladatnál van egy rövid magyarázat.)
Nézzünk egy példa bemenetet.
ebb ebb ebb type fast ebb fast type deflector ebb
Ekkor a kimenet a következő.
ebb type fast deflector
Érdemes nagyobb példákon is tesztelni a programot, úgyhogy itt van néhány.
Ebben a feladatban egy háziállatot kell a lehető legolcsóbban felhízlalni.
Különféle takarmányok kaphatók a piacon, és a programnak ki kell választani a legolcsóbb kombinációt, ami az állatnak helyes táplálkozást biztosít. A takarmányok egységcsomagban kaphatóak, mindegyikből csak egész számút lehet venni. Összesen pontosan három csomagot kell választania, de ezek között lehetnek egyformák is. Minden fajta csomagnak négy paramétere van: az ára, a szénhidrát tartalma, a fehérje tartalma, és a zsírtartalma. (Minden csomagból elég sok van raktáron, tehát bármelyiket lehet háromszor is kiválasztani.) Az állat pontosan akkor lesz egészséges, ha legalább 400 egységnyi szénhidrátot, 100 egységnyi fehérjét, és 100 egységnyi zsírt fogyaszt el.
A program bemenetében az első sor a boltban rendelkezésre álló takarmányfajták száma: 1 ≤ N ≤ 40. Az összes többi sor egy fajta takarmányt ír le, ez négy számból áll, mindegyik 0 és 20000 közti egész, az első szám a takarmány ára, a második a szénhidrát-tartalom, a harmadik a fehérje-tartalom, a negyedik a zsírtartalom.
A program kimenete egy sorban álló három számból áll, amelyek a kiválasztandó áruk azonosítóját adja meg. Az azonosítók a bemenet sorrendjében tartoznak a takramány-csomagokhoz, az első sorhoz tartozó csomag azonosítója 0, stb, az utolsóé N-1. A három számot növekvő sorrendben kell felsorolni. (Mindegyik bemenethez egyértelmű megoldás tartozik.)
Íme egy példa. Ha a bemenet a következő
5 100 310 0 0 50 210 0 0 100 50 100 0 450 160 110 0 100 50 0 110
Akkor a kimenet a következő.
0 2 4
Az 50 forintba kerülő 1 sorszámú takarmányt nem választhatjuk ki, mert e mellé a drága 3 sorszámú csomagot is meg kéne venni, hogy az állat jól táplált legyen.
Itt van még pár példa, ezek mutatják, hogy gyakran érdemes ugyanabból a termékből venni kettőt vagy akár hármat is.