Diákolimpiai válogató 1996

Telefonvonalakon küldött számítógépes üzenetek gyakran sérülhetnek, emiatt szükség lehet hibafelismerő kódokra (olyan kódolásra, amelynél a vevő felismeri, sőt ki is javíthatja a hibásan megérkezett karaktereket). Egy hiba felismerésére és javítására a következő kódolást használjuk.

Az N karakterből álló szöveget bontsuk K karakterből álló csoportokra. Minden karaktert egészítsünk ki paritásbittel (a legmagasabb helyiértékű karaktert úgy állítsuk 1-re vagy 0-ra, hogy a byte 1-es bitjei száma páros legyen). A csoport K darab karaktere kódjából kizáró vagy művelettel állítsunk elő egy K+1. karaktert (az ellenőrző összeget). Ha egy bit megsérül egy K+1 elemből álló csoportban, akkor a hibás bíte paritásbitje elromlik, így a hibás byte felfedezhető. Ezzel együtt elromlik a K+1. byte kizáró vagy művelettel kiszámolt értékében is 1 bit, amiről megállapítható a hibás byte-on belül megsérült bit helye, s az a jóra kijavítható.

Feladat:

Készíts programot, amely a KOD.INP állományban tárolt, paritásbittel és ellenőrző összeggel ellátott szöveget visszaalakítja 7 bites kódúvá, s a hibás karaktereket kijavítja, majd az egészet kiírja a képernyőre és a KOD.OUT állományba!

Bemenet:

A KOD.INP minden sora a szöveg K darab karakterét és az ellenőrző összeget tartalmazza.

Kimenet:

A KOD.OUT állományba soronként a K darab visszaalakított karaktert kell írni. K értéke az állomány első sora hossza alapján állapítható meg.

Példa:

 

KOD.INP	KOD.OUT
{pótlandó}	I need an easy friend, I do with an ear to le nd, I do think you fit this shoe, I do but yo u have a clue. (K.C.)

(futási idő és hatékonyság is számított)

Készíts programot, amely előállítja N-ig (N<10000000) az erősen összetett számokat! Az erősen összetett számok olyan természetes számok, amelyek osztói száma nagyobb, mint bármely más nála kisebb természetes szám osztói száma.

Példa:

 

Bemenet	Kimenet
100	1, 2, 4, 6, 12, 24, 36, 48, 60

Határőrség  - 3. feladat (16 pont)

Bergengóciában nincs két egyforma nevű lakos. Az ország K(<=5) darab határátkelőhellyel rendelkezik, amelyek mindegyikében feljegyzik a BERGi.INP (i=1...5) állományba a ki- vagy belépő állampolgárok nevét. .

Feladat:

Készíts programot, amely kiírja egy adott dátumra az éppen külföldön tartózkodó állampolgárok nevét (a KULFOLD.OUT állományba és a képernyőre), valamint azokat, akik eddig a dátumig valamilyen határsértést követtek el (kétszer egymás után szerepelnek kilépőként, illetve belépőként) (a HATAR.OUT állományba és a képernyőre)! A megadott napon átlépőket már nem szabad figyelembe venni.

Bemenet:

A BERGi.INP állományok minden sora a KI vagy a BE szóval kezdődik, amelyet egy szóközzel elválasztva a határátkelőn átlépés dátuma (napsorszám), majd a lakos neve követ. Az állományok név, és azon belül dátum szerint növekvő sorrendbe rendezettek, tartalmuk nem biztos, hogy elfér a memóriában

Kimenet:

 

Példa:

 

BERG1.INP	KI 1 Egyszerkilepo Lajos BE 2 Mindenutt Eva BE 5 Többhelyen Krisztina
BERG2.INP	KI 1 Csakitt Jozsef BE 2 Csakitt Jozsef KI 1 Masholnem Istvan BE 2 Masholnem Istvan KI 3 Masholnem Istvan KI 1 Mindenutt Eva KI 1 Tobbhelyen Krisztina BE 2 Tobbhelyen Krisztina KI 3 Tobbhelyen Krisztina BE 1 Ugyanott Ede BE 2 Ugyanott Ede
BERG3.INP	KI 3 Mindenutt Eva BE 2 Tobbhelyen Adam KI 3 Tobbhelyenki Kolos KI 1 Ugyanottki Bela KI 6 Ugyanottki Bela
BERG4.INP	BE 4 Mindenutt Eva KI 2 Tobbhelyenki Kolos
BERG5.INP	KI 5 Mindenutt Eva BE 1 Tobbhelyen Adam KI 3 Tobbhelyen Adam KI 1 Tobbhelyenki Kolos

Futó a sakktáblán  - 4. feladat (18 pont)

Egy sakktáblán elhelyezünk világos és sötét bábukat, valamint adott helyre egy világos futót.

Feladat:

Készíts programot, amely megadja azt a minimális számú lépéssorozatot, amellyel a futó egy adott másik helyre eljuthat úgy, hogy más bábut nem léphet át, nem is üthet le.

Bemenet:

A FUTO.INP állomány első sorában a futó kezdeti helye található, egy betűvel (A..H) és egy számjeggyel (1..8) kódolva, a következő sorokban a többi bábu helyzetét adjuk meg (mindegyikben egyet), s az utolsó sor tartalmazza a célhelyet.

Kimenet:

A FUTO.OUT állományba és a képernyőre a futó lépései utáni helykoordinátákat kell írni, soronként egyet.

Egy könyvtár kulcsszavakat tárol, amelyek megkönnyítik a keresést. A kulcsszavak a KULCS.INP állományban találhatók, az állomány I. sorában az I. könyv kulcsszavai szerepelnek szóközökkel elválasztva.

Feladat:

Készíts programot, amely beolvas egy kulcsszó-kifejezést, majd kiírja a képernyőre és a KULCS.OUT állományba azon könyvek sorszámát (1-től kezdődően, egy sorba 1 sorszámot) amelyek a kifejezésnek megfelelnek.

A kulcsszókifejezés vagy egyetlen kulcsszó; vagy &-jellel (ÉS kapcsolat) összekapcsolt kulcsszavak (pl. alma&körte&barack), melyek mindegyikének szerepelnie kell az adott könyv kulcsszavai között; vagy az előbbiek + jellel (VAGY kapcsolat) összekapcsolva (pl. fa&bokor+fű), s a + jelekkel összekapcsolt kulcsszócsoportok közül valamelyiknek kell szerepelnie az adott könyv kulcsszavai között.

Bemenet:

A kulcsszavak a KULCS.INP állományban találhatók, az állomány I. sorában az I. könyv kulcsszavai szerepelnek szóközökkel elválasztva.

Kimenet:

A KULCS.OUT állományba azon könyvek sorszáma kerüljön (1-től kezd?dően, egy sorba 1 sorszám) amelyek a kulcskifejezésnek megfelelnek.

Példa:

 

KULCS.INP	KULCS.OUT
internet netscape java halozat internet java hobby internet golf sport gyumolcstermesztes sport spor java jatek halozat

Akárhogyan prímek  - 6. feladat (13 pont)

(a megoldó algoritmus gyorsasága is számít)

Feladat:

Készíts olyan programot, amely előállítja az összes olyan N jegyű prímszámot, amelynek számjegyei bármilyen sorrendben felírva is N jegyú prímszámot adnak ki! Ki is kell írni az ilyen számokat, valamint az összes lehetséges számjegypermutációjukat is! Azokat a számokat nem szabad kiírni, amelyek valamilyen szám számjegyei permutációjaként már előfordultak.

Bemenet:

Egy N szám, amely meghatározza, hogy hány jegyű számok között vizsgálódunk.

Kimenet:

A feltételnek megfelelő permutációkat a képernyőre kell írni.

Példa:

 

BEMENET	KIMENET
N=1	2, 3, 5, 7
N=2	11, 13, 17, 37 79 és permutációik
N=3	113, 199, 337 és permutációik

Határsáv  - 7. feladat (16 pont)

Magyarország térképét egy N*M-es mátrixban adtuk meg úgy, hogy minden határon kívüli pont értéke -1, minden határpont értéke +1, s minden országon belüli pont értéke 0.

Feladat:

Készíts programot, amely átírja a határsávba eső pontok 0-s értékét 2-re! Határsávba az a pont esik, amelynek 2 sugarú (négyzet alakú) környezetében van határpont.

Bemenet:

A HATAR.INP állományban található a térkép mátrixa, melynek első sor N és M értékét tartalmazza egy szóközzel elválasztva, a következő N sor pedig M darab számot egy-egy szóközzel elválasztva.

Kimenet:

A keletkezett mátrixot a képernyőre és a HATAR.OUT állományba kell írni. Formátuma a bemeneti állomány formátumával egyezzen meg!

Példa:

 

HATAR.INP

12 16 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  1 -1 -1 -1 -1 -1 -1  1  1  1  1  1  1 -1 -1  1  0  1 -1 -1 -1 -1  1  0  0  0  0  0  1 -1 -1  1  0  1 -1 -1 -1  1  0  0  0  0  0  0  1 -1 -1  1  0  1  1  1  1  0  0  0  0  0  0  0  0  1 -1  1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1 -1  1  0  0  0  0  0  0  0  0  0  0  0  0  1 -1 -1 -1  1  0  0  0  0  1  1  1  0  0  0  1 -1 -1 -1  1  0  0  0  0  1 -1 -1 -1  1  0  0  1 -1 -1 -1  1  0  0  0  0  1 -1 -1 -1  1  0  0  0  1 -1 -1 -1  1  1  1  1  1 -1 -1 -1 -1  1  0  0  0  1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  1  1  1 -1 -1

HATAR.OUT

12 16 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  1 -1 -1 -1 -1 -1 -1  1  1  1  1  1  1 -1 -1  1  2  1 -1 -1 -1 -1  1  2  2  2  2  2  1 -1 -1  1  2  1 -1 -1 -1  1  2  2  2  2  2  2  1 -1 -1  1  2  1  1  1  1  2  2  2  2  0  2  2  2  1 -1  1  2  2  2  2  2  2  2  2  2  2  2  2  1 -1 -1  1  2  2  2  2  2  2  2  2  2  2  2  2  1 -1 -1 -1  1  2  2  2  2  1  1  1  2  2  2  1 -1 -1 -1  1  2  2  2  2  1 -1 -1 -1  1  2  2  1 -1 -1 -1  1  2  2  2  2  1 -1 -1 -1  1  2  2  2  1 -1 -1 -1  1  1  1  1  1 -1 -1 -1 -1  1  2  2  2  1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  1  1  1 -1 -1

Minimális hálózat  - 8. feladat (14 pont)

{a megoldó algoritmus gyorsasága is számít}

Baranya megye városait és falvait gázszállításra alkalmas csővezetékkel szeretnék összekötni. Bármely két helység között építhetünk gázvezetéket, melynek hossza a két helység távolságával egyenlő (egyenes vezeték építhető).

Feladat:

Készíts programot, amely kiírja a képernyőre és a CSO.OUT állományba azt a minimális hosszúságú gázvezetéket, amellyel a megye helységei egyetlen összefüggő gázhálózatba köthetők.

Bemenet:

A CSO.INP állomány tartalmazza a helységek koordinátáit, soronként egy számpárt, a számokat szóköz választja el egymástól.

Kimenet:

A CSO.OUT állományban soronként szerepelnek azok a helységsorszám párok, amelyeket közvetlen gázvezeték köt össze.

Példa:

 

CSO.INP	CSO.OUT
1 1 100 100	1 2
1 1 1 100 10 80	1 3 2 3
10 30 20 10 30 50 40 20 30 40 50 10	1 2 2 4 3 5 4 5 4 6

Útkeresés hegyvidéken  - 9. feladat (16 pont)

Egy N*M-es mátrixban tároljuk egy terület domborzati térképét. Minden egyes mátrixelem az adott pont tengerszint feletti magasságát tartalmazza. A területen két adott pont között utat kell építeni, amely vízszintes vagy függőleges irányokban haladhat (átlósan nem), s az emelkedés szöve nem lehet több ALFA foknál.

Feladat:

Készíts programot, amely beolvassa a TERKEP.INP állományból a térképet, majd megkérdezi az út két végpontjának koordinátáit, majd megadja a közöttük vezető legrövidett, a feltételeknek eleget tevő út közbülső pontjainak koordinátáit.

Bemenet:

A TERKEP.INP állomány első sora N és M értékét tartalmazza egy szóközzel elválasztva, a következő N sor mindegyike M darab magasságértéket tartalmaz egy-egy szóközzel elválasztva.

Kimenet:

Az eredményt a képernyőre és a TERKEP.OUT állományba kell írni, melynek minden sorábam az út egy pontjának koordinátái találhatók egy szóközzel elválasztva.

Példa:

 

TERKEP.INP	TERKEP.OUT
9 6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 9 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 9 9 9 9 5 5 5 5 5 5	???

Blokk-fa  - 10. feladat (16 pont)

Egy blokk-fa az alábbi szerkezetű blokkok sorozata:

• elemek száma (N),
• elemeket nagyság szerint rendezve tartalmazó tömb (maximum MAXN elemű, az első N eleme van kitöltve),
• blokksorszámokat tartalmazó tömb (0-tól MAXN-ig indexelt tömb, 0-tól N-ig van kitöltve).

A 0-ás indexű blokksorszám olyan blokk sorszáma, amelyben levő értékek kisebbek a blokk 1. elemének értékénél; az 1-es indexű blokksorszám pedig olyané, amelynek elemei nagyobbak a blokk első eleménél, de nem nagyobbak a másodiknál; ... A blokksorszám 0, ha nincs az adott értékek közé eső elem.

Feladat:

Készíts programot, amely beolvas a BFA.INP állományból egy blokk-fát, majd kiírja a blokk-fa elemei számát, valamint magasságát.

Bemenet:

A BFA.INP áálomány számhármasokat tartalmaz. Mindegyik első sora az adott blokkban levő elemek számát tartalmazza, a második magukat az elemeket egy-egy szóközzel elválasztva. a harmadik pedig a következő blokkok sorszámait. (Az i. blokk az állomány i. sorhármasában található.)

Kimenet:

A BFA.OUT állomány első sora a blokk-fa elemszámát tartalmazza, a második sora pedig a blokkfa magasságát adja meg.

Példa:

 

BFA.INP	BFA.OUT
3 100 200 300 2 3 4 5 3 10 20 30 6 0 0 0 2 110 120 130 140 0 0 0 0 0 4 210 220 0 0 0 1 310 0 0 2 1 2 0 0	15 3

Összevissza színezett sakktábla  - 11. feladat (14 pont)

Egy sakktáblán nem szabályosan színezték be a mezőket sötétre és világosra, hanem véletlenszerűen. .

Feladat:

Készíts programot, amely elhelyez a sakktáblára 8 vezért úgy, hogy a vezérek nem üthetik egymást, s mindegyik csak világos mezőn állhat. Ha nem sikerül mind elhelyezni, akkor megadja a lehető legtöbbet, amit el lehet helyezni

Bemenet:

A SAKK.INP állomány tartalmazza a sakktábla sötét mezőinek pozícióit. Minden pozíciót egy betű (A..H) és egy számjegy (1..8) azonosít, a pozíciók egymás után egyetlen sorban vannak leírva, elválasztójel nincs közöttük.

Kimenet:

 Az eredményt a képernyőre és a SAKK.OUT állományba kell kiírni, amely legfeljebb 8 vezérpozíciót tartalmaz, a bemenő állománnyal azonos formában.

Példa:

 

SAKK.INP	SAKK.OUT
???	???

Csillaghalmazok  - 12. feladat (14 pont)

A budapesti tudományegyetem csillagászati tanszékén elhatározták, hogy a csillagokról számítógépes nyilvántartást fognak vezetni, minden csillagot azonosítják 3 térbeli koordinátájával (fényévekben megadva). A csillagok egy része úgynevezett csillaghalmazokba tömörül. A csillaghalmazok legalább K csillagból állnak, s bármelyik két csillaguk között vezet olyan út, amely a csillaghalmaz csillagain keresztül halad, s legfeljebb F fényéves lépésekből áll.

Feladat:

Készíts programot, amely beolvassa a csillagkoordinátákat, majd meghatározza a csillaghalmazok számát és az egyes csillaghalmazokba tartozó csillagok sorszámát!

Bemenet:

A CSILLAG.INP állományban tároljuk a csillagkoordinátákat, amelynek első sorában a K és F értéke szerepel egy szóközzel elválasztva, majd  soronként három egész szám szerepel egy-egy szóközzel elválasztva. Minden számhármas egy-egy csillagot határoz meg.

Kimenet:

A CSILLAG.OUT állomány első sorában a csillaghalmazok száma szerepel, azt követően szerepelnek az egyes csillaghalmazokba tartozó csillagok (soronként egy, három koordinátájával azonosítottan). Az egyes csillaghalmazokat egymástól egy üres sor választja el.

Példa:

 

CSILLAG.INP	CSILLAG.OUT

Állatkereskedés  - 13. feladat (14 pont)

Egy állatkereskedő a győri piacon állatokat szeretne vásárolni, s összesen FT forintja van. A piacon N féle állatot lehet vásárolni, az i. fajtából maximum Di(>0) darabot. Az i. fajta állat ára Fi(>0) forint. A felvásárol állatokat a bécsi piacra viszi, ahol az i. fajta állatot Ai(>0) forintért tudja eladni.

Feladat:

Készíts programot, amely megadja, hogy a kereskedő melyik állatból hány darabot vegyen, ha a maximális hasznot szeretné elérni!

Bemenet:

Az adatokat az ALLAT.INP állományból olvassa be, amelynek első sora N és FT értékét tartalmazza egy szóközzel elválasztva, a 2. sor a Di, a 3. sor az Fi, a 4. sor pedig az Ai értékeket tartalmazza egy-egy szóközzel elválasztva.

Kimenet:

Az ALLAT.OUT állomány az Mi értékeket tartalmazza, mely szerint az i. állatból hány darabot kell vásárolni a maximális haszon eléréséhez.

Példa:

 

ALLAT.INP	ALLAT.OUT
10 1000 1 2 10 5 6 2 1 3 4 7 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 11	1 2 10 5 6 2 1 3 4 7
10 1000 1 2 10 5 6 2 1 3 4 7 1 2 3 4 5 6 7 8 9 10 2 2 4 3 6 7 8 9 10 1	1 2 10 0 6 2 1 3 4 0
6 19 3 3 3 3 3 3 2 2 2 7 2 8 1 2 3 21 5 22	0 0 0 2 2 0
5 19 3 3 3 3 1 2 2 2 7 2 1 2 3 21 5	0 0 1 2 1
5 19 3 3 3 3 1 2 2 2 72 1 2 3 21 5	0 0 1 2 1