Egy térképet egy NxM-es mátrixban ábrázolunk. A városokat a mátrixban a 2-es számjegy, az utakat pedig az 1-es számjegy jelzi. A többi ponthoz tartozó érték 0. Az utak minden pontból a 4 szomszédos pont irányában folytatódhatnak, azaz átlósan lépni nem lehet. Egy város több 2-es értékű pontból is állhat, de két város sehol sem érintkezhet egymással, azaz nincs két szomszédos pontjuk.Feladat:
Készíts programot, amely két város esetén megadja a városok területét (hány 2-es értékű pontból áll), valamint két a közöttük vezető legrövidebb út hosszát az alábbi háromféle módon:Bemenet:
- a legrövidebb az az út, ami a legkevesebb várost érinti a kiindulásin kívül;
- a legrövidebb út az az út, ami legkevesebb, egyik városhoz sem tartozó (1-es értékű) közbülső ponton halad át;
- a legrövidebb út az az út, amin a leggyorsabban el lehet érni a másik városba, feltételezve, hogy városban feleakkora a sebesség, mint a városok közötti utakon, azaz az 1-essel jelölt pontot 1, a 2-essel jelölt pontot pedig 2 időegység alatt lehet elhagyni.
A TERKEP.BE állomány első sorában N és M értéke van (1<=N, M<=100), egy-egy szóközzel elválasztva. A további N sor mindegyike pontosan M számjegyet tartalmaz (csak 0, 1 vagy 2 lehet) szóközök nélkül, a térkép egyes sorai leírását. Az állomány utolsó sora két város indexeit ((X,Y) és (U,V)), azaz négy számot tartalmaz (1<=X, U<=M, 1<=Y, V<=N), s a feladat az (X,Y)-ból (U,V)-be vezető legrövidebb út megtalálása. Az első sor első (bal oldali) elemének koordinátái (1,1), az N. sor M. elemének pedig (N,M).Kimenet:A TERKEP.KI állományba négy sort kell írni. Az első sorban (X,Y), illetve az (U,V) pontot tartalmazó város területét kell írni, egy szóközzel elválasztva. A következő három sorban egyetlen szám szerepeljen: a feladatban szereplő három megfogalmazásbeli legrövidebb út hossza. Ha nincs út a két város között, akkor -1-et kell írni mindhárom sorba.Példa:
TERKEP.BE TERKEP.KI 9 10
2200000000
0200000000
0110000000
0010000000
0011200000
0001220000
0000211122
0000000122
0000000112
1 1 9 103 5
2
8
22
Egy sivatagban N város található, melyek között az év egy időszakában naponta indulnak karavánok. Ezen időszakon kívül azonban egyetlen sem indul.Feladat:
Készíts programot, amely meghatározza két adott, A B városra és H határidőre a következőket:Bemenet:
- Legkorábban mikorra érhetünk az A városból a B városba;
- Legalább hány nap kell ahhoz, hogy az A városból a B városba érjünk, ha nincs megkötés sem az indulási, sem az érkezési időre;
- Legkésőbb melyik napon kell elindulni az A városból, hogy legkésőbb a megadott H határidőig a B városba érjünk.
A KARAVAN.BE állomány első sorában a városok száma (1<=N<=100) és a karavánkapcsolatok száma (1<=M<=5000) van. A következő M sor mindegyikében két város-sorszám (X,Y) és két napsorszám (P,Q) van egy-egy szóközzel elválasztva, ami azt jelenti, hogy az X. városból az Y városba az év P. és Q. napja között (P-t és Q-t is beleértve) indulnak karavánok. Az állomány utolsó sorában az indulási (A) és az érkezési (B) hely sorszáma van, valamint annak a napnak az éven belüli H sorszáma, amikor legkésőbb meg kell érkezni a B. városba, egy-egy szóközzel elválasztva. A karavánokmindig reggel indulnak és még aznap este megérkeznek a célállomásra.Kimenet:A KARAVAN.KI állományba három sort kell írni. Minden sorban egyetlen szám szerepeljen: a részfeladat megoldásának értéke. Ha egy részfeladatnak nem létezik megoldása, akkor a -1 számot kell kiírni.Példa:
KARAVAN.BE KARAVAN.KI 5 7
1 2 2 7
1 5 2 4
2 3 1 2
2 5 8 9
3 4 6 7
5 4 3 9
4 2 1 2
1 4 103
2
7
Dominóval sokféle játékot lehet játszami. Mohó Marci kedvenc dominós játéka a következő. Először véletlenszerűen sorba rakja a felhasználható dominókat. A játék célja az, hogy a lehető leghosszabb illeszkedő sorozatot képezzen a felhasználható dominókból. A játékszabály szerint minden lépésben csak a felhasználható dominósor első (bal oldali) elemét veheti és vagy elveti (félrerakja, de később nem veheti), vagy a már illeszkedő sorozat bal vagy jobb végéhez teszi, feltéve, hogy az adott oldalával illeszkedik (megegyezik a pöttyök száma a két dominó érintkező oldalán). Az aktuális dominót mindkét oldalával próbálja illeszteni. A játék úgy kezdődik, hogy az első dominót ki kell raknia.Feladat:
Készíts programot, amely meghatározza a kirakható leghosszabb illeszkedő dominósor hosszát.Bemenet:A DOMINO.BE állomány első sorában a felhasználható dominók száma (1<=N<=100000) van. A következő N sor mindegyikében egy dominó leírása, azaz két szám, X Y (0<=X, Y<=9) van egy szóközzel elválasztva. Bármely dominó (számpár) többször is szerepelhet az állományban, és az állomány nem feltétlenül tartalmaz minden lehetséges dominót.Kimenet:A DOMINO.KI állományba egyetlen számot kell írni, a kirakható leghosszabb illeszkedő dominósor hosszát.Példa:
DOMINO.BE DOMINO.KI 6
1 2
1 6
2 3
1 4
2 3
4 35