Diákolimpiai válogató 2000


Örökösök  - 1. feladat(40 pont) /tesztadatok/
Az öreg király N vármegyére osztotta országát. Hosszú uralkodása alatt K fia született, s a vármegyéket fel szeretné osztani közöttük.
Két feltételt szeretne betartani: Feladat:
Készíts programot (OROKOS.PAS vagy OROKOS.C), amely kiszámolja, hogy a fenti feltételeknek megfelelően (darabszám szerint) hányféleképpen oszthatja el a király a vármegyéket a fiai között!
Bemenet:
Az OROKOS.BE állomány egyetlen sorában a vármegyék száma (1<=N<=100) és a király fiai száma (1<=K<=10) van, egyetlen szóközzel elválasztva.
Kimenet:
Az OROKOS.KI állomány első sorába a lehetséges vármegye-elosztásokszámát kell írni.
Példa:
 
OROKOS.BE OROKOS.KI
10 3 8
Megjegyzés:
10 = 8+1+1 = 7+2+1 = 6+3+1 = 6+2+2 = 5+4+1 = 5+3+2 = 4+4+2= 4+3+3, azaz összesen 8-féle felosztás van.

Láda  - 2. feladat (30 pont) /tesztadatok/
Adott ládáknak egy sorozata. Minden láda kocka alakú és egyik oldala nyitott. A ládákat egy robotnak kell összepakolni úgy, hogy egy ládát belerakhat egy másik ládába, ha az utóbbinak a mérete kisebb. Azonbana robot csak sorban balról-jobbra haladva tudja a pakolást elvégezni, teháta soron következő ládát vagy belerakja egy másik, már összepakolt ládába,vagy külön hagyja. Az a cél, hogy a lehető legkevesebb összerakott láda keletkezzen.

Feladat:

Írj programot (LADA.PAS vagy LADA.C) amely megmondja, hogy minimálisan hány ládába lehet a ládasorozatot összepakolni, továbbá megadja, hogy mely ládák lesznek egybepakolva.
Bemenet:
A LADA.BE állomány első sorában a ládák N száma (0<=N<=10000) van. A második sorban N db pozitív egész szám van, a ládák méretei. Mindenszám értéke 1 és 30000 közötti.
Kimenet:
A LADA.KI állomány első sorába az összepakoláshoz minimálisan szükséges ládák M számát kell írni. A következő M sor mindegyike egy összepakolást ad meg, azaz azon ládák sorszámai szerepelnek egy sorban, amelyeket egybe kell pakolnia a robotnak a kiírás sorrendjében.
Példa:
 
LADA.BE LADA.KI
10
4 1 5 10 7 9 2 8 3 2		 4
1 2
3 7
4 5 9 10
6 8

Barátok  - 3. feladat(30 pont) /tesztadatok/

Barátok között előfordul, hogy kölcsönadnak egymásnak kisebb-nagyobb pénzösszeget. Ösztöndíj-fizetéskor azonban kiegyenlítik a tartozásokat. Ezért pontosan feljegyzik, hogy ki kitől, mekkora összeget vett kölcsön. Szeretnék optimalizálni a tartozások kiegyenlítését, azaz a legkevesebb pénzmozgással megoldani.

Feladat:

Írj programot (BARATOK.PAS vagy BARATOK.C), amely
Bemenet:
A BARATOK.BE szöveges állomány első sora a barátok N (N<N<=10000) számát tartalmazza. A barátokat a sorszámukkal azonosítjuk 1-től N-ig.A második sorban a tranzakciók K száma áll (0<=K<=30000). A következő K sor mindegyike három egész számot; X Y P, (1<=X, Y<=N, X<>Y, 0<P<=30000) tartalmaz egy-egy szóközzel elválasztva, ami egy tranzakciót ír le, az X személy az Y személytől P összeget vett kölcsön a hónap során valamikor.
Kimenet:
A BARATOK.KI szöveges állomány első sorába azt a minimális pénzösszeget kell írni, amennyi a tartozások optimális kiegyenlítése során átutalásra kerül. A következő sorokban meg kell adni egy, kiegyenlítést eredményező optimális átutalási sozotatot. Minden sorban három szám szerepeljen egy-egy szóközzel elválasztva, X Y P, ami azt jelenti, hogy az X személy Y személynek P összeget utal át a kiegyenlítés során. (Nem kikötés, hogy X kölcsönért Y-tól, és előfordulhat, hogy egy személy több másiknak is átutal a megoldásban.)
Példa:
 
BARATOK.BE BARATOK.KI
3
7
1 2 250
1 3 15
1 2 100
3 1 50
2 1 35
2 3 10
1 2 15		 320
3 2 25
1 2 295

Síelő  - 4. feladat (30pont) /tesztadatok/

Egy síelőközpontban többféle lesiklópályát lehet kijelölni. Az egyes kijelölhető pályák csak kezdőpontból indulhatnak és csak végpontban végződhetnek. A kezdőpontokba nem vezet be út, a végpontokból pedig nemvezet ki út.

Feladat:

Készíts programot (SIELO.PAS vagy SIELO.C), amely kiszámoljaa legrövidebb és a leghosszabb kijelölhető lesiklópálya helyét!
Bemenet:
A SIELO.BE állomány első soránban a pályák csomópontjainak száma (1<=N<=100) és a közöttük vezető utak száma (1<=M<=1000) van, egyetlen szóközzel elválasztva. A következő M sor mindegyike egy-egy út két végpontjának sorszámát és a köztük levő távolságot (A B H, az út A-ból B-be vezet, hossza H, A<B, H>0) tartalmazza, egyetlen szóközzel elválasztva.

Kimenet:
A SIELO.KI állomány első sorába a legrövidebb, a másodikba pedig a leghosszabb út hosszát, valamint a kezdő- és végcsomópontjának sorszámát kell írni, egy-egy szóközzel elválasztva.
Példa:
SIELO.BE SIELO.KI
5 4
1 3 10
2 3 5
3 4 8
3 5 2		 7 2 5
18 1 4

Net  - 5. feladat (40pont) /tesztadatok/

Olyan számítógép-hálózat kiépítése a feladat, amelynek topológiája nagyon speciális. Minden gépet, kivéve a központi szervert egy megadott másik géphez kell kapcsolni. A hálózat kialakítása során a gépek hálózatba kötését párhuzamosan lehet végezni. Pontosabban, az A<--B és C<--D kapcsolat kialakítása egyidőben történhet, ha A<>C és az A, valamint a C gépeket már bekötöttük a hálózatba. Minden gép bekötéséhez ugyanannyi idő, 1 perc szükséges. Az a cél, hogy a legrövidebb idő alatt minden gép be legyen kötve a hálózatba. Kezdetben csak a központi gépből áll a kialakítandó hálózat.

Feladat:

Írj programot (NET.PAS vagy NET.C), amely
Bemenet:
A NET.BE szöveges állomány első sora a gépek (0<N<=1000) számát tartalmazza. A gépeket a sorszámukkal azonosítjuk 1-től N-ig, a központi szerver sorszáma 1. A második sorban a kialakítandó topológia leírása található, N darab egész szám, egy-egy szóközzel elválasztva. Az első szám 0 (mert a központi szervert nem kell másik géphez kapcsolni), az i-edik (i>1) szám annak a gépnek a j sorszáma (j<i) amelyik géphez az i-edik gépet kapcsolni kell.
Kimenet:
A NET.KI szöveges állomány első sorába azt a legkisebb időt kell írni, amennyi idő alatt a kívánt topológia kialakítható. A második sorba a gépek egy optimális bekötésének ütemezését megadó N számot kellírni. Az első szám 0, az i-edik (i>1) szám pedig az i-edik gép bekötésének időpontja legyen.
Példa:
NET.BE NET.KI
8
0 1 1 1 2 2 6 3		 3
0 1 2 3 3 2 3 3

Pálya  - 6. feladat (30pont) /tesztadatok/

Tájékozódási futóversenyt rendeznek egy olyan pályán, ami N ellenőrző pontot tartalmaz. Térkép tartalmazza, hogy mely pontok között vezet egyirányú ösvény. Adott továbbá a Start és a Cél pont.

Feladat:

Írj programot (PALYA.PAS vagy PALYA.C), amely meghatározza az összes olyan ellenőrző pontot, amely nem kerülhető ki, tehát amelyen minden Start-ból Cél-ba vezető út keresztülmegy!
Bemenet:
A PALYA.BE szöveges állomány első sora az ellenőrző pontokN (0<N<=200) számát tartalmazza. Az ellenőrző pontokat a sorszámukkal azonosítjuk 1-től N-ig. A második sorban van a Start és a Cél állomás sorszáma. A harmadik sorban az ösvények K száma áll. (0<=K<=30000). A következőK sor mindegyike két egész számot; X Y, (1<=X, Y<=N, X<>Y) tartalmaz egy szóközzel elválasztva, ami azt jelenti, hogy az X pontból vezet (egyirányú) ösvény az Y pontba.
Kimenet:
A PALYA.KI szöveges állomány két sort tartalmazzon. Az első sorábaa -1 értéket kell írni, ha nincs út a Start és a Cél között. Egyébként az első sor azon pontok M számát tartalmazza, amelyek nem kerülhetők ki (M=0, ha nincs ilyen pont). A második sor az M darab nem kikerülhető pontot tartalmazza egy-egy szóközzel elválasztva.
Példa:
PALYA.BE PALYA.KI
6
1 6
7
1 2
1 3
2 4
3 4
4 5
5 2
5 6		 4
1 4 5 6

Zanza  - 7. feladat (30pont) /tesztadatok/

Tekintsük az alábbi szójátékot. Adott N darab, azonos hosszúságú szó és egy M szám. A játék célja kialakítani olyan, pontosan M betűt tartalmazó, úgynevezett zanzaszót, amelyben a megadott szavak előfordulási száma a lehető legnagyobb. Az előforduló szavak átfedhetik egymást és egy szó többször is előfordulhat a zanzaszóban.

Feladat:

Írj programot (ZANZA.PAS vagy ZANZA.C), amely
Bemenet:
A ZANZA.Be szöveges állomány első sorában három szám van, N, L és M. N a felhasználható szavak száma, (0<N<=100), L (0<L<=255) a szavak hossza, M (0<M<=255) pedig a kialakítandó zanzaszó hossza. A következő N sorban egy-egy L betűből álló szó található.
Kimenet:
A ZANZA.KI szöveges állomány két sort tartalmazzon. A második sorba egy olyan M betűből álló zanzaszót kell írni, amelyben a bemenetben megadott szavak előfordulási száma a lehető legnagyobb (K). Az előfordulások számát az első sorba kell írni.
Példa:
ZANZA.BE ZANZA.KI
7 4 16
vele
elve
fele
kefe
elem
emel
leve		 8
velemelvelemelve

Domborzati térkép  -8. feladat (40 pont) /tesztadatok/

Egy csupa nemnegatív egészekből álló mátrix egy rácsnégyzetekreosztott sziget domborzati adatait tartalmazza: egy-egy érték a neki megfeleltetettrácsnégyzet fölötti, egészekre kerekített, átlagos tengerszint felettimagasságot jelenti. A domborzat viszonlag egyenletes: nem fordul elő az,hogy egy 2x2-es rész egyik átlójában lévő két érték kisebb a másik kétértéknél. Adott koordinátájú rácsnégyzeten egy kiapadhatatlan forrás törtfel.

Feladat:

Írj egy programot (TERKEP.PAS vagy TERKEP.C), amely megadja,hogy mekkora mennyiségű vizet képesek a szigeten a keletkező tavak megtartani, illetve a tavaknak hány különböző szintje alakul ki!
Bemenet:
A TERKEP.BE állomány első sorában a térkép sorai (1<=N<=100)és oszlopai (1<=M<=100) száma van, egyetlen szóközzel elválasztva.A következő N sor mindegyike pontosan M számot tartalmaz, az egyes pontokbanmért tengerszint feletti magasságot, szóközökkel elválasztva. Az utolsósorban a forrás helyének sor- (1<=K<=N) és oszlopindexe (1<=L<=M)van, egyetlen szóközzel elválasztva.
Kimenet:
A TERKEP.KI állomány első sorába a megtartott víz mennyiségét,a másodikba pedig a tavak különböző szintjei számát kell írni.
Példa:
 

TERKEP.BE TERKEP.KI
7 7
0  0  0  0  0  0  0
0 20 29 29  6 53  0
0 25 25 30 16 16  0
0 41 18 36 50 21  0
0 46  9 37 60 13  0
0 33 33 33 33 33  0
0  0  0  0  0  0  0
3 3		 23
1
Megyjegyzés:
A 18 és a 9 értékű elem helyére kerül 25 az elárasztás során.

Robot  - 9. feladat (30pont) /tesztadatok/

Egy 2x2-es (KxK-as) robotot helyezünk el szobába, megjelölve a kezdő- és a célpozícióját. A robotot el kell vezetni a célig, feltéve,hogy minden lépés 1 időegységbe kerül (csak vízszintesen vagy függőlegesen mozdulhat el 1 egységnyit), valamint, hogy úgy kell mozgatni, hogy bizonyostárgyakat (1x1-es méretűeket) felemelhet és maga mögé tehet. Egy útbanálló tárgy elmozdítása szintén 1 időegységbe kerül.

Feladat:

Készíts programot (ROBOT.PAS vagy ROBOT.C), amely megadja,hogy minimum mennyi idő múlva érhet a robot a kezdőpozícióból a célpozícióba!
Bemenet:
A ROBOT.BE állomány első sorában a négyzetrács magassága ésszélessége (1<=N, M<=100) van. A következő N sor mindegyike pontosanM karaktert tartalmaz, az üres helyeken '.'-ot, a foglalt helyeken '*'-ot,az elmozdítható tárgyak helyén '+' jelet, a robot kezdőpozícióján négydarab 'K' betűt, célpozícióján pedig négy darab 'C' betűt.
Kimenet:
A ROBOT.KI állomány egyetlen sorába azt a minimális időtartamotkell írni, ami alatt a robot a kezdőhelyzetből a célpozícióba érhet.
Példa:
 

ROBOT.BE ROBOT.KI
6 10
..........
.KK.......
.KK.......
.+.******.
......CC..
......CC..		 9

Csővezeték  - 10. feladat(28 pont) /tesztadatok/

Egy országban K helyen építettek olajfinomítót, ahol kőoljabólbenzint készítenek. N helyen van benzinkút, ahova a benzint el kell juttatnicsővezetéken valamelyik olajfinomítóból. Úgy kell megtervezni a csővezetéket,hogy minimális hosszúságú csövet kelljen lefektetni. Csővezeték csak benzinkútnál vagy finomítónál ágazhat el, a térképen csak vízszintesen vagy függőlegesenvezethető, a vezetékek keresztezhetik egymást, de csatlakozás csak finomítónál vagy benzinkútnál lehet. A finomítókat 1-től K-ig, a benzinkutakat pedig(K+1)-től (K+N)-ig sorszámozzuk.

Feladat:

Készíts programot (CSO.PAS vagy CSO.C), amely meghatarozza, hogy mely csomópontok (olajfinomító vagy benzinkút) között kell kiépítenia csővezetéket úgy, hogy a csővezeték hossza minimális legyen.
Bemenet:
A CSO.BE állomány első sorában az olajfinomítók (1<=K<=10)és a benzinkutak (1<=N<=1000) száma van egy szóközzel elválasztva.A következő K sor az egyes olajfinomítók, az ezt követő N sor pedig a benzinkutak koordinátáit tartalmazza. Minden sorban egy sor- és egy oszlopindex szerepel(-1000 és 1000 közötti egész számok), egymástól egy szóközzel elválasztva.
Kimenet:
A CSO.KI állomány első sorába a minimális hosszúságú csőhálózathosszát kell írni, a további sorokba pedig azon helyek indexeit, amelyekközött csövet kell fektetni a minimális hosszúságú csőhálózat kiépítéséhez.Minden sorban egy összeköttetés két végének sorszáma szerepeljen!
Példa:
 

CSO.BE CSO.KI
2 4
100 100
0 100
-100 100
100 0
40 40
150 -50		 400
2 3
1 4
2 5
4 6

Robotváros  - 11. feladat(42 pont) /tesztadatok/

Robot város úthálózata olyan, hogy minden kereszteződésben pontosan 3 út találkozik. Azt mondjuk, hogy az A-B úttól C jobbra, D pedigbalra van, ha az óramutató járásával szemben haladva az ABC szög kisebb,mint az ABD szög. Egy robotot kell irányítanunk a labirintusban a J ésa B betűk, mint parancsok segítségével, amelyek azt jelentik, hogy az adottkereszteződésben a robotnak jobbra vagy balra kell fordulnia.

Feladat:

Készíts programot (VAROS.PAS vagy VAROS.C), amely egy parancssorozattal megadja azt az utat, amely a legkevesebb / legtöbb kereszteződést érintvevezet az A kereszteződésből a V kereszteződésbe úgy, hogy a robot mindenkereszteződésen és minden úton legfeljebb egyszer halad át!
Bemenet:
A VAROS.BE állomány első sorában a kereszteződések száma (1<=N<=100)van. A második sorban a robot tartózkodási helye (1<=A<=N) és annaka kereszteződésnek a sorszáma van, ahova először lép (1<=B<=N). Aharmadik sor a robot által elérendő kereszteződés sorszámát (1<=V<=N)tartalmazza. A következő N sor az egyes kereszteződések X és Y koordinátáját,valamint a vele szomszédos három kereszteződés sorszámát tartalmazza, egy-egy szóközzel elválasztva.
Kimenet:
A VAROS.KI állományba két sort kell írni. Az elsőbe azt a parancssorozatot,amely a robotot az A-ból a B felé indulva a V kereszteződésbe viszi a lehetőlegkisebb, a másodikba pedig azt, ami a lehető legnagyobb lépésszámú olyanúton, ami a fenti szabályoknak megfelel.
Példa:
 

VAROS.BE VAROS.KI
8
1 2
5
0 0 2 3 7
10 0 1 4 8
3 3 1 4 5
7 3 2 3 6
3 7 3 6 7
7 7 4 5 8
0 10 1 5 8
10 10 2 6 7		 JJB
BJJBB

Strucctojás  - 12. feladat(30 pont) /tesztadatok/

Van néhány teljesen egyforma strucctojásunk, és egy sokemeletespanelház. El szeretnénk dönteni, hogy a ház hányadik emeletéről lehet mégkidobni egy tojást úgy, hogy ne törjön össze. A tojások "jól viselkednek",azaz ha valahányadikról egyszer kidobtunk egyet anélkül, hogy összetörtvolna, akkor minden annál nem nagyobb sorszámú emeletről kidobva egy tojást,az épen marad. Egy tojás, ha nem tört össze egy kísérlet során, akkor mindenfajtakárosodás nélkül élte túl azt, azaz akár a legmagasabban fekvő, - a tojások számára még elviselhető - emeletről kidobva is épen marad. (Azaz nem "gyűjti"a részleges sérüléseket.) Ezért nem is tartjuk számon, hogy mikor melyiktojással próbálkozunk - nem is tudnánk megkülönböztetni, hiszen olyan egyformák,mint két tojás -, csak azt, hogy hány még épen maradt tojásunk van. Korlátozott számú tojásunk van; ha az mind összetört, akkor már választ kell adnunk.A cél az, hogy minél kevesebb próbálkozással választ adjunk.

A rendelkezésre álló tojások száma 1<=K<=8, a ház emeleteinekszáma 1<=N<=1'900'000'000 (legfeljebb 1,9 milliárd). Minden tesztesetolyan, hogy bármely megoldás kitalálható legfeljebb 700 dobással.

A kísérleteket egy tárgykódban rendelkezésre álló modul segítségévelvégezhetik a programok. Ennek neve Pascal esetén strhaz.tpu, C változata strhaz.obj, illetve strhaz.h. Ezeket az állományokat a floppylemezek gyökérkönyvtárábanhelyeztük el.

A program (STRUCC.PAS vagy STRUCC.C) az N, K bemeneti adatokat is amodultól kapja, semmilyen fájlt nem olvashat és nem is írhat.

A következő függvényeket/eljárásokat lehet használni:

 
Function EmeletekSzama:LongInt;
extern long EmeleketSzama();
 
Function TojasokSzama:byte;
extern unsigned char TojasokSzama();
 
Funcion Dob(emelet:LongInt):boolean;
extern int Dob(long emelet);
Az egyetlen paraméterel az emelet sorszámát kell megadni, ahonnan kidobjuka tojást. Az emeleteket 1-től N-ig sorszámozzuk. A Pascalban true, a C-ben1 visszaadott érték esetén a tojás összetört; Pascalban false, C-ben 0visszatérési érték esetén a tojás megmaradt.
 
Procedure Valasz(emelet:LongInt);
extern void Valasz(long emelet);
Ennek az eljárásnak a meghívásával kell a megoldást közölni. Az egyetlenparaméter annak az emeletnek a sorszámát tartalmazza, amelyről még ki lehet dobni a tojást anélkül, hogy összetörne. Ha már az elsőről kidobva is összetörika tojás, akkor a válasz 0 legyen. Az eljárás nem tér vissza, hanem a kimenetifájl megírása után megszakítja a program futását.

Modul használata Pascalban:

A lemezen adott strhaz.tpu-t az aktuális könyvtárba kell másolni,és a főprogram elejére a uses strhaz; parancsot kell beírni a következőképpen:
 
Program Strucc;
  Uses StrHaz;
Majd használhatjuk a feljebb deklarált eljárásokat úgy, mintha magunk írtukvolna meg őket.
Modul használata C-ben:
A lemezen található strhaz.obj és strhaz.h nevű fájlokat azaktuális könyvtárba kell másolni. A főprogram elejére be kell írni a következősort:
 
#include strhaz.obj
Majd a Project / Open project menüponttal meg kell nyitni egy projektet és a Project / Add file menüponttal hozzá kell adni a strucc.c és a strucc.objfájlokat. A strucc.c programszöveg ablakából nem lehet közvetlenül kiadnia Build vagy Make parancsot, mert linkelési hibával leáll. Ehelyett ha.EXE állománnyá akarjuk fordítani a programot, akkor ezt a parancsot aProject ablakban kell kiadni.

Megjegyzés: Erősen ajánljuk a C nyelv használatát a C++ helyett. Akimégis az utóbbival szeretne dolgozni, használja a floppylemez \STRHCPPalkönyvtárában található strhaz.obj fájlt.

Tesztelés:
A verseny ideje alatt a STRUCC.BE bemeneti fájlok készítésével és az aktuális könyvtárba helyezésével lehet tesztelni a programot. Eza fájl egyetlen sorában három T, N, K egész számot tartalmaz egyetlen szóközzel elválasztva: a rendelkezésre álló tojások számát, a ház magasságát és amegoldást, azaz a legmagasabban fekvő olyan emelet sorszámát, melyről mégki lehet dobni a tojást anélkül, hogy összetörne.

Helyes futás esetén a modul készít egy STRUCC.KI nevű kimeneti fájlt,amely három számot tartalmaz szóközzel elválasztva: az első szám mindig0, a második meghívott Valasz eljárásnak megadott paraméter, a harmadikpedig az elvégzett kísétletek száma.