Diákolimpiai válogató 1995


1. feladat (? pont)
Egy szöveget csak az angol 7 bites ASCII karakterekkel írtak, s egy zajos kommunikációs csatornán szeretnék továbbítani. A hibák felismerése érdekében a karaktert tartalmazó bíte 8. bitjét úgy állítják 0-ra vagy 1-re, hogy a byte-ban az 1-es bitesk száma páros legyen (ez az úgynevezett paritásbit).

Feladat:

Írj programot, amely előkészíti, azaz egy tetszőleges szöveget átalakít paritásbittel ellátott szöveggé.
Bemenet:
A bemenetet az F1.INP textfájl tartalmazza.
Kimenet:
A kimenetet az F1.OUT állományba kell írni.

2. feladat (? pont)
A Minimal programozási nyelv egyetlenegy utasítást tartalmaz, az értékadást, s egyetlen műveletet, a szorzást (egy értékadásban ebből is csak egy alkalmazható). Szerencsére a nyelv tartalmaz beolvasó és kiíró eljárást.

Feladat:

Készíts programot, amely beolvas egy természetes számot (b), majd generálja azt a Minimal nyelvű programot, amely egy a érték beolvasása után kiszámítja ab-t a lehető legkevesebb művelettel!
Példa:
 
bemenet kimenet
b=13 Be: X1
X2:=X1*X1
X3:=X2*X2
X4:=X3*X1
X5:=X3*X3
X6:=X5*X4
Ki: X6

3. feladat (? pont)

A számítógép memóriájának szabad területeit egy N elemű sorozatként tartjuk nyilván, memóriacím szerint növekvő sorrendben (N a szabad területek száma). Minden sorozatelem kettős: kezdőcím, hossz. A memória aktuális állapota megtalálható az F2A.INP állományban. Memóriafelszabadítás esetén újabb szabad területek keletkezhetnek, amelyeket be kell venni ebbe a sorozatba a kezdőcím szerinti helyére, kivéve, ha összeérne valamelyik korábbi szabad területtel (ekkor össze kell olvasztani őket egyetlen, nagyobb szabad területté).

Feladat:

Végezd el a felszabadításokat, s az F2.OUT állományba írd ki az eredményt!
Bemenet:
Az F2A.INP állomány első sora az N értékét, következő N sora a sorozatelemeket tartalmazza egy szóközzel elválasztva.
Az F2B.INP állományban soronként egy-egy szóközzel elválasztott számpár írja le a felszabadítandó területek kezdőcímét és hosszát.
Kimenet:
Az F2.OUT állományba minden felszabadítás után írd ki az szabad helyek leírását tartalmazó sorozatot!
Példa:
 
F2A.INP F2B.INP F2.OUT
3
1000 1000
3000 500
5000 2500		 2500 100
4000 1000		 4
1000 1000
2500 100
3000 500
5000 2500
4
1000 1000
2500 100
3000 500
4000 3500

4. feladat (? pont)

Egy modern nagyváros úthálózata egy négyzetráccsal írható le, ahol N jelöli a négyzetrács sorainak számát (azaz a kelet-nyugati irányú utak számát), M pedig az oszlopokét (azaz az észak-déli utakét). Az egyes kereszteződések (csomópontok) előtt a haladási irányt befolyásoló jelzőtáblák lehetnek, amelyeket a következő kódokkal látunk el:
 
BT Balra fordulni tilos
JT Jobbra fordulni tilos
BK Balra haladni kötelező
JK Jobbra haladni kötelező

Feladat:

Írj programot, amely beolvassa két csomópont koordinátáit, majd a táblák figyelembevételével kiírja azon csomópontok koordinátáit, amelyeken áthaladva eljuthatunk az indulási helyről a célba.
Bemenet:
Az F4.INP állomány első sorában a táblák száma, majd soronként egy-egy tábla leírása található. A táblaleírás formája: kód sor oszlop irány, ahol a sor és az oszlop a csomópont koordinátáit adja meg, az irány pedig a csomópontba beérkező útszakasz irányát (É, K, D, NY).
Kimenet:
Az eredmény az F4.OUT állományba kerül, amelyben soronként egy-egy csomópont koordinátái olvashatók.

5. feladat (? pont)

Gyógyszerek nevét úgy kell meghatározni, hogy - az orvos nehezen olvasható írása ellenére is - egyértelműen olvasható legyen, azaz ne lehessen összetéveszteni más gyógyszerek nevével. Négy tipikus eset fordul elő:


Feladat:

Készíts programot, amely egy gyógyszer tervezett neve és az F5.INP állományban tárolt gyógyszernevek alapján eldönti, hogy legfeljebb 2 tévesztéssel azonossá tehető-e valamelyikkel (ekkor ugyanis ezt a nevet nem adhatjuk neki).
Bemenet:
Az F5.INP állományban a már létező gyógyszernevek szerepelnek, soronként egy-egy darab.
Kimenet:
Az eredményt a képernyőre kell írni. "A NÉV JÓ" szöveg jelenjen meg, ha a bevitt név megfelelő, "A NÉV ROSSZ" szöveg kerüljön a képernyőre, ha a név nem jó, s ez esetben írd ki azt is, milyen tévesztésekkel tehető azonossá!

6. feladat (? pont)

Egy szénhidrogén szerkezetét mátrixszal írjuk le, melyben A(I,J) értéke 1, ha az I. és a J. atom között van kötés, illetve 0, ha nincs. A szénhidrogénben lehetnek gyűrűk, gyűrűket összekötő láncok, valamint gyűrűkből "lelógó" láncok.

Feladat:

Írj programot, amely beolvassa az F6.INP állományból a szénhidrogén mátrixának elemeit, elhagyja a "lelógó" láncokat, majd a bemeneti állományal azonos formátumban az eredményt az F6.OUT állományba írja.
Bemenet:
Az F6.INP állomány első sorában az N szám szerepel, majd az azt követő N darab sorban soronként N darab szám.
Kimenet:
Az F6.OUT állomány szerkezetileg megegyezik az F6.INP állománnyal.

7. feladat (? pont)

{az elvileg eltérő módszerek száma számít}
A binomiális együtthatókat a következő képlettel számolhatjuk:

Feladat:

Készíts programot, amely adott n-re k=0-tól n-ig kiszámítja a binomiális együtthatók értékeit, minél többféle módszerrel!

Ha valaki birtokában van a többi feladatnak, kérem, segítsen!

  - . feladat (? pont)

 

Feladat:

 
Bemenet:
 
Kimenet:
 
Példa: