Diákolimpiai válogató 2004


Vírus - 1. feladat (20 pont) /tesztadatok/
Biológusok egy különleges vírustörzset vizsgálnak. Egy kísérlet során minden egyedre feljegyezték annak keletkezési és pusztulási időpontját. Adott H értékre szeretnék kiszámítani, hogy melyik az a H hosszúságú időintervallum, amely alatt a legtöbb egyed volt megfigyelhető. A T kezdetű, H hosszú időintervallumban azok a K keletkezési és P pusztulási idejű egyedek voltak megfigyelhetők, amelyre az alábbi feltételek teljesülnek:
T<=K és K<T+H, vagy T<P és P<T+H, vagy K<T és P>=T+H

Feladat:

Írj programot (VIRUS.PAS, VIRUS.C, ...) amely kiszámítja annak a H hosszú időintervallumnak a kezdetét, amely alatt a legtöbb egyed volt életben!
Bemenet:
A VIRUS.BE szöveges állományban az első sor az egyedek N (1<=N<=300000) számát és az időintervallum H (1<H<=7000) értékét tartalmazza egy szóközzel elválasztva. A következő N sorban az egyes egyedek K keletkezési és P pusztulási ideje van, (1<=K<P<=7000) egy szóközzel elválasztva.
Kimenet:
A VIRUS.KI szöveges állomány első sorába két egész számot kell írni, az első a megfigyelhető vírusok maximális száma legyen, a második a T időpont, amelyre a T kezdetű és H hosszú időintervallumban a legtöbb egyed volt megfigyelhető (T+H<=7000). Több megoldás esetén a legkorábbi időpontot kell kiírni.
Példa:
 
VIRUS.BE VIRUS.KI
9 3
2 6
1 3
5 6
4 7
4 9
8 11
11 14
10 13
10 12
 4 2

Vasút - 2. feladat (40 pont) /tesztadatok/
Háromsor város vasútállomásán nagy gondot okoz a szerelvények rendezése. Az állomásról továbbítandó szerelvényeket úgy kell alakítani, hogy amikor az megérkezik a célállomásra, a szerelvény végéről mindig lekapcsolható legyen az oda továbbított kocsisor. Minden továbbítandó szerelvény négy állomást érint, ezért a rendezés előtt minden kocsit megjelölnek az 1, 2, 3 vagy 4 számokkal. A szerelvény kocsijait rendezzük át úgy, hogy a szerelvény elején legyenek az 1-essel, aztán a 2-essel, majd a 3-assal, végül a 4-essel megjelöltek. Kezdetben a kocsik az ábrán látható I-J pályaszakaszon vannak. A vasúti váltók működése csak a következő hat műveletet teszi lehetővé.
rajz a vasút feladathoz
Feladat:
Írj programot (VASUT.PAS, VASUT.C, ...) amely meghatároz egy olyan tolatási műveletsort, amelynek végrehajtása a bemeneti kocsisor rendezését eredményezi!
Bemenet:
A VASUT.BE szöveges állomány első sora a kocsik N számát tartalmazza (1<=N<=1000). A második sor pontosan N egész számot tartalmaz egy-egy szóközzel elválasztva, a rendezendő kocsik címkéit. Minden címke értéke 1, 2, 3 vagy 4.
Kimenet:
A VASUT.KI szöveges állomány egy olyan tolatási műveletsort tartalmazzon, amelynek végrehajtása a bemeneti kocsisor rendezését eredményezi. Minden sor egy-egy tolatási művelet jelét tartalmazza, ami a 'B1', 'B2', 'B3', 'K1', 'K2' vagy 'K3' string lehet. Ha nem lehet rendezni a bemeneti kocsisort, akkor az állomány első és egyetlen sorába a NEM szót kell írni!
Példa:
 
VASUT.BE VASUT.KI
5
2 3 1 4 3		 B1
B3
B2
K2
B1
K1
K3
B2
K2
K1

Találka - 3. feladat (40 pont) /tesztadatok/

Rómaó és Júlia a lehető legrövidebb időn belül találkozni szeretne. Jelenleg egymástól távol, különböző városban vannak. Repülővel akarnak utazni egy olyan városba, ahova a legrövidebb idő alatt mindketten megérkezhetnek. Az útvonal kiválasztásához ismerik az összes igénybe vehető repülőjáratot.

Feladat:

Készíts programot (TALALKA.PAS vagy TALALKA.C), amely a repülőjáratok, valamint Rómeó és Júlia tartózkodási helyének ismeretében megadja a legközelebbi találkozási pontot és azt a két útvonalat, amelyen közlekedniük kell ahhoz, hogy a lehető legkorábban találkozzanak!
Bemenet:
A TALALKA.BE szöveges állomány első sorában a városok (1<=N<=100) és a repülőjáratok (1<=M<10000) száma van, egyetlen szóközzel elválasztva. A városokat az 1, ..., N számokkal azonosítjuk. A második sorban a Rómeó és Júlia tartózkodási helyének sorszáma van (1<=A, B<=N). A következő M sor mindegyikében egy repülőjárat van (1<=K<>V<=N), egyetlen szóközzel elválasztva. Ez azt jelenti, hogy a K városból van közvetlen járat a V városba. Minden járat naponta csak egyszer közlekedik és reggel indul azonos időben.
Kimenet:
A TALALKA.KI állomány három sort tartalmazzon. Az első sorba két számot kell írni, az első a legközelebbi találkozás ideje, a második  a legközelebbi találkozási város sorszám legyen! Ha nincs ilyen, akkor az első sorba -1-et kell írni és ilyenkor a következő két sor legyen üres. A második sorba azt az útvonalat kell írni, amelyiken Rómeó eljut a találkozási városba, a harmadik pedig azt az útvonalat, amelyiken Júlia eljut a találkozási városba. Ha több megoldás is van, egy tetszőlegeset ki lehet írni.
Példa:
 
TALALKA.BE TALALKA.KI
10 15
1 8
1 2
2 1
1 4
3 2
4 3
2 5
3 6
3 7
4 7
5 10
6 9
7 6
8 7
8 9
9 10
 2 7
1 4 7
8 7

Pontok - 4. feladat (30pont) /tesztadatok/

Adot a síkon egy ponthalmaz. Azt mondjuk, hogy egyenesek egy halmaza lefedi a ponthalmazt, ha a ponthalmaz bármely pontja rajta van valamelyik egyenesen.

Feladat:

Írj olyan programot (PONTOK.PAS vagy PONTOK.C), amely eldönti, hogy adott ponthalmaz lefedhető-e legfeljebb három egyenessel! A program adjon is meg három ilyen egyenest, ha van lefedés.
Bemenet:
A PONTOK.BE szöveges állomány első sorában a pontok N (1<=N<=10000) száma van. A következő N sor mindegyikében két egész szám van egy szóközzel elválasztva: x y, egy pont x-koordinátája és y-koordinátája (-20000<= x, y<= 20000).
Kimenet:
A PONTOK.KI szöveges állomány első sorába négy 0 számot kell írni (egy-egy szóközzel elválasztva) ha a ponthalmaz nem fedhető le három egyenessel. Egyébként az állományba három sort kell írni, mindhárom sorba egy-egy lefedő egyenest megadó négy egész számot kell írni: x1; y1; x2; y2, ami az (x1, y1), és (x2, y2) pontokon átmenő egyenest jelenti. Ha a ponthalmaz lefedhető háromnál kevesebb egyenessel, akkor is három sort (egyenest) kell kiírni; a felesleges egyenesek tetszőlegesek.
Példa:
 
PONTOK.BE PONTOK.KI
8
2 3
4 2
6 4
2 5
8 5
6 6
4 7
2 8		 2 3 2 8
2 8 8 5
4 2 6 4

Sakk - 5. feladat (35pont) /tesztadatok/

Egy NxN-es sakktáblán bábukat helyezhetünk el, amelyek a helyükről nem mozdulnak el. Egyetlen futót mozgathatunk. Futó a sakktáblán mindig csak valamilyen átló irányában léphet, akárhányat, de bábut nem ugorhat át, és nem is léphet más bábu helyére. Az átló irányú, akármilyen hosszú mozgatást tekintjük egy lépésnek.

Feladat:

Készíts programot (SAKK.PAS vagy SAKK.C), amely egy adott sakktáblára és két pozícióra megadja, hogy 
Bemenet:
A SAKK.BE szöveges állomány első sorában a sakktábla mérete (1<=N<=100), valamint az elhelyezett bábuk száma (1<=K<10000) van, egyetlen szóközzel elválasztva. A második sorban 4 szám, a futó kezdő- és végpozíciója van (1<=KX, KY, VY, VY<=N), egy-egy szóközzel elválasztva. A következő K sorban egy-egy bábu koordinátái vannak (1<= X, Y <=N). Biztosan tudjuk, hogy a futó kezdőpozícióján (KX, KY) nem áll más bábu.
Kimenet:
A SAKK.KI állományba pontosan 2 sort kell írni, a két részfeladat esetén a minimális lépésszámot! Ha valamelyik feladat nem oldható meg, akkor abba sorba -1-et kell írni.
Példa:
 
SAKK.BE SAKK.KI
8 5
6 3 2 7
5 2
3 3
3 6
6 7
8 5
 3
2

Kredit - 6. feladat (35pont) /tesztadatok/

Az egyetemeken kreditrendszerű oktatás folyik, amiből az következik, hogy az egyes tantárgyakat a képzés bármely félévében lehet tanulni, ha az előfeltételüket (más tantárgyak elvégzése) a hallgatók már teljesítették..

Feladat:

Készíts programot (KREDIT.PAS vagy KREDIT.C), amely a tantárgyak előfeltételei ismeretében megadja, hogy az egyetem minimálisan hány félév alatt végezhető el, s ebbenaz esetben melyek azok a tárgyak, amelyek elvégzését nem lehet későbbre tolni (mert ettől nőne az egyetem elvégzési ideje)!
Bemenet:
A KREDIT.BE szöveges állomány első sorában a tantárgyak (1<=N<=150) és az előfeltételek száma (0<=M<=500) van. A következő N sor mindegyikében egy-egy tantárgy pontosan 6 karakteres azonosítója, az azt követő M sorban pedig az előfeltételek vannak. Minden előfeltétel két, pontosan 6 karakteres azonosítóból áll, közöttük egy szóközzel, amelynek jelentése: a sorban levő első tárgynak előfeltétele a sorban levő második tárgy elvégzése.
Kimenet:
A KREDIT.KI szöveges állomány első sorába azt a félévszámot kell írni, amennyi az előfeltételek betartásával minimálisan szükséges az egyetem elvégzéséhez. A második sorba azon tantárgyak K száma kerüljön, amelyeket a minimális elvégzési idő miatt csak egy adott félévben lehet elvégezni, a következő K sorban pedig ezen tantrgyak azonosítói legyenek (soronként 1)!
Példa:
 
KREDIT.BE KREDIT.KI
6 5
AAAAAA
BBBBBB
CCCCCC
DDDDDD
EEEEEE
FFFFFF
BBBBBB AAAAAA
CCCCCC AAAAAA
EEEEEE DDDDDD
FFFFFF CCCCCC
FFFFFF BBBBBB
 3
4
AAAAAA
BBBBBB
CCCCCC
FFFFFF

Licit - 7. feladat (50 pont) /tesztadatok/

Egy rendezvényt olyan teremben tartanak, ahol M darab ülőhely van. Az ülőhelyek 1-től M-ig sorszámozottak. A rendezvény szervezője megrendeléseket fogad. Minden megrendelésnek egy d h f számhármast tartalmaz, ami azt jelenti, hogy a megrendelő az első h ülőhelyek közül d darab egymás melletti ülőhelyet szeretne kapni, és ezért f forintot fizetne.

Feladat:

Készíts programot (LICIT.PAS vagy LICIT.C), amely kiszámítja, hogy mekkora az elérhető legnagyobb bevétel, s meg is ad egy olyan jegykiosztást, amely eléri a lehető legnagyobb bevételt!
Bemenet:
A LICIT.BE szöveges állomány első sorában két egész szám van, M és N. M a (1<=M<=100) az ülőhelyek száma, N (1<=N<=300) pedig a megrendelések száma. A következő N sorban az egyes megrendelések d h f leírása szerepel (1<=d<=h<=M), (1<=f<=200) egy szóközözzel elválasztva. Az állomány i+1-edik sora az i-edik megrendelést adja.
Kimenet:
A LICIT.KI szöveges állomány első sorába a legnagyobb bevételt és az azt eredményező megrendelés részhalmaz K elemszámát kell írni. A következő K sor tartalmazza a jegykiosztást a kiválasztott K megrendelés számára. Minden sor két egész számot tartalmazzon egy szóközzel elválasztva. Az első szám egy megrendelés sorszáma, a második pedig annak a legkisebb sorszámú ülőhelynek a sorszáma, amelyet a megrendelő kap.
Példa:
 
LICIT.BE DARABOL.KI
6 3
2 3 60
3 4 100
2 4 60
 120
2
1 1
3 3

Fa -8. feladat (50 pont) /tesztadatok/

Egy fán hangyák élnek. A fa bizonyos elágazásaihoz őrhangyákat állítanak, amelyek az adott ponttól felfele (a levelek felé) levő részen, legfeljebb K ág távolságnyira mászhatnak, azaz legfeljebb K ág távolságnyira képesek őrizni az összes ágat. Az őrhangya az őrhelyétől lefelé nem mászik.

Feladat:

Készíts programot (FA.PAS vagy FA.C), amely egy adott fára megadja, hogy minimálisan hány őrhangyára van szükség!
Bemenet:
A FA.BE szöveges állomány első sorában a fa csomópontjai (elágazások, illetve ágvégek) száma (1<=N<=10000), valamint az egy hangya által bejárható legnagyobb távolság (1<=K<=100) van, egyetlen szóközzel elválasztva. A következő N-1 sorban az egyes ágak "A B" leírása szerepel (1<= A, B <=N és A<>B) egy szóközzel elválasztva, melynek jelentése: az ág az A sorszámú csomópontnál kezdődik és a B sorszámúba vezet felfelé a levelek irányában.
Kimenet:
A FA.KI állományba pontosan egy sort kell írni, a fa őrzéséhez minimálisan szükséges hangyák számát.
Példa:
 
FA.BE FA.KI
12 2
1 2
2 3
2 4
4 5
4 7
7 6
7 8
1 9
9 10
10 11
7 12
 3

Hálózat - 9. feladat (50 pont) /tesztadatok/

Bergengóciában N város között kell kiépíteni a hálózatot. K héten keresztül kapunk egy-egy újabb árajaánlatot két város közötti közvetlen hálózati kapcsolat létesítésére.

Feladat:

Írj programot (HALOZAT.PAS vagy HALOZAT.C), amely minden hétre - ha lehetséges - megad az addig beérkezett javaslatok alapján egy tervet, hogy mely város-párok között építsenek ki közvetlen kapcsolatot, hogy bármely városból bármely másik elérhető legyen közvetlenül vagy más városokon keresztül, de úgy, hogy az építés összköltsége minimális legyen! A terv összekötendő város-párokból és a hálózat-kiépítés teljes költségéből áll.
Bemenet:
A HALOZAT.BE szöveges állomány első sorában a városok (1<=N<=100) és a hetek (1<=K<=10000) száma van. A következő K sor mindegyike egy hét árajánlatát tartalmazza: két város sorszámát és egy árat (1<=ÁR<=1000), egy-egy szóközzel elválasztva.
Kimenet:
A HALOZAT.KI szöveges állományba pontosan K+1 sort kell írni. Az első sorba annak a hétnek a sorszámát, ami után már nem csökken tovább a minimális kiépítési költség. Ha a hálózat soha nem építhető ki, akkor ebbe a sorba 0 kerüljön! Az (i+1)-edik sorba pedig, ha az i-edik héten még nem lehet olyan kapcsolatrendszert kiépíteni, hogy bármelyik város bárhonnan elérhető legyen, akkor 0 kerüljön, egyébként pedig az i-edik heti kiépítés minimális költsége!
Példa:
 
HALOZAT.BE HALOZAT.KI
3 5
1 3 100
2 3 50
1 3 60
1 2 40
1 3 120
 4
0
150
110
90
90

Dominó - 10. feladat(50 pont) /tesztadatok/ (interaktív feladat)

Tekintsük a dominó játéknak a következő kétszemélyes változatát. Először kiraknak egy sorban páros számú dominót, ez a választható dominósor, majd választanak egy kezdő dominót, amit külön helyre leraknak. A két játékos felváltva lép, az első játékos kezd. Minden lépésben az aktuális játékos választ egy dominót a választható dominósor valamelyik végéről és azt a kirakott dominósor valamelyik végéhez illeszti. Az illesztés azt jelenti, hogy a választott dominőnak egyik oldalán ugyanannyi pöttynek kell lennie, mint amihez illeszteni akarja. Ha nem tud illeszkedőt választani, akkor le kell vennie a választható dominósor valamelyik szélső dominóját, és félre kell raknia, de ekkor egy büntetőpontot kap. A játék akkor ér véget, ha elfogyott az összes választható dominó. A játékban az nyer, akinek kevesebb büntetőpontja van.

Feladat:

Írj programot (DOMINO.PAS vagy DOMINO.C), amely az első játékos játékát valósítja meg és nyer!
A bemenetekre teljesül, hogy az első játékosnak van nyerő stratégiája, azaz meg tudja verni a második játékost.

... A programunk egy unit segítségével játszik, ennek leírása elmarad.
Feltételek:
A dominók N száma: 2<=N<=16
A .dominók sorszámaira: 0<=i<=16. A kezdő dominó sorszáma: 0