Egy megyén belül a településeket régiókba szeretnék csoportosítani. Ismerjük az egyes települések koordinátáit. Két település távolságán a koordináta-különbségeik abszolút-értékének összegét értjük, azaz TÁVOLSÁG( (x,y), (a,b) ) = |x-a|+|y-b|.
Két települést azonos régióba teszünk, ha egyikből a másikba el lehet jutni a régió településein keresztül úgy, hogy az egymást követő települések távolsága legfeljebb T kilométer.
Feladat:
Írj programot, (REGIO.PAS, REGIO.C, ...), amelyBemenet:A. megadja, hogy a települések hány régiót alkotnak
B. és mely települések tartoznak egy régióba!A REGIO.BE szöveges állomány első sorában a városok N száma (2<=N<=100) és a régióba kerülés határát jelentő T távolság (1<=T<=100) van. A következő N sor mindegyikében egy-egy számpár van, az adott város x- és y-koordinátája (0 és 1000 közötti egész számok), egy-egy szóközzel elválasztva.Kimenet:A REGIO.KI szöveges állomány első sorába a legkisebb K számot kell írni, ahány régióba lehet besorolni a településeket. A következő K sorba az egyes régiókat kell írni, tetszőleges sorrendben. Egy sorba a régióba tartozó települések sorszámát kell írni, egy-egy szóközzel elválasztva, növekvő sorrendben.Példa:
REGIO.BE REGIO.KI 6 50
100 100
100 220
100 120
300 100
120 140
310 90
3
1 3 5
2
4 6
Egy repülőtársaság N város között üzemeltet járatokat. A városokat a természetes számokkal azonosítják 1-től N-ig. A társaság jelentős kedvezményt ad, ha az utas olyan útvonalat választ, hogy az utazás során mindig nagyobb sorszámú városba megy. Az 1. városból szeretnénk eljutni az N. városba kedvezményes útvonalon.Feladat:
Írj programot (REPUT.PAS, REPUT.C, ...), amely megadja azokat a városokat, amelyeken mindenképpen át kell haladnunk, valamint azokat a város-párokat, amelyek közötti járatot mindenképpen igénybe kell venni bármely kedvezményes útvonalon akarunk az 1. városból az N. városba jutni!Bemenet:A REPUT.BE szöveges állomány első sorában a városok N száma (1<=N<=100) és a járatok M száma (1<=M<=1000) van. A következő M sor mindegyikében egy-egy P Q számpár (1<=P<Q<=N) van, egy szóközzel elválasztva. Ez azt jelenti, hogy van járat a P és a Q város között. Az 1. városból bárely másik városba el lehet jutni és báemely városból el lehet jutni az N. városba alkalmas járatokkal.Kimenet:A REPUT.KI szöveges állomány első sorába a kikerülhetetlen városok K számát kell írni, majd ettől egy-egy szóközzel elválasztva a kikerülhetetlen városok sorszámát növekvő sorrendben. A második sorba a kikerülhetetlen járatok M számát kell írni. A következő M sor mindegyikébe egy-egy elkerülhetetlen járatot kell írni, a két város sorszámát egy szóközzel elválasztva.Példa:
REPUT.BE REPUT.KI 10 12
1 2
1 3
2 4
3 4
4 5
5 6
5 7
6 8
7 8
8 9
9 10
8 10
3 4 5 8
1
4 5
Egy titkos társaság hierarchikusan épül fel, minden tagja csak a felettesét és a hozzá közvetlenül beosztott legfelebb két tagot ismeri. A társaságnak pontosan egy olyan tagja van, akinek nincs főnöke. Bármelyik tag küldhet levelet bármelyik tagnak. Azonban minden levél csak úgy juthat el a feladótól a címzetthez, hogy egy lépésben vagy a közvetlen főkökhöz, vagy közvetlen beosztotthoz továbbítódik.Feladat:
Írj programot (TARSASAG.PAS, TARSASAG.C ...), amely adott két, X és Y tagra kiszámítja az alábbi kérdésekre adandő választ!Bemenet:
- Hány beosztottja - nem csak közvetlen - van az X és Y tagnak?
- Hány lépéssel továbbítódik egy levél, ha X küld levelet Y-nak?
- Mennyi a legkevesebb lépésszám, ami alatt biztosan odaér a levél bárki legyen is a feladó, illetve a címzett?
A TARSASAG.BE szöveges állomány első sorába a társaság tagjainak N száma (1<=N<=1000), valamint két tag X és Y sorszáma (1<=X, Y<=N) van. A társaság tagjai olyan sorszámot kaptak 1 és N között, hogy mindenkinek nagyobb a sorszáma, mint közvetlen főnökéé. A második sor pontosan N darab 0 és N közötti egész számot tartalmaz egy-egy szóközzel elválasztva. Az i-edik szám a társaság i-sorszámú tagjának közvetlen főnökét adja. A sorban az első szám 0, mivel pontosan 1 tagnak, az 1 sorszámúnak nincs főnöke. Minden tag legfeljebb két másik tagnak lehet a közvetlen főnöke.Kimenet:
A TARSASAG.KI szöveges állomány első sorába az A, második sorába a B, harmadik sorába a C kérdésre adott választ kell írni. Az első sorba két szám kerül, az X és Y beosztottjainak száma. A második sorba egyetlen számot kell írni, azt a lépésszámot, amely alatt egy levél eljut az X tagtól az Y taghoz. A harmadik sorba egyetlen számot kell írni, ami a legkevesebb lépésszám, ami alatt biztosan odaér egy levél, bárki is legyen a feladó, illetve a címzett.Példa:
TARSASAG.BE TARSASAG.KI 7 2 5
0 1 1 3 3 5 50 2
3
4
Egy autópálya mentén N város helyezkedik el. Bizonyos városokban autópálya rendőrök tartózkodnak, némelyikben több, némelyikben egy sem. Összesen N rendőr van. Azt szeretnénk elérni, hogy a lehető legtöbb városban legyen rendőr, ezért át kell csoportosítani. Az átcsoportosítást a lehető legkisebb összköltséggel kell végrehajtani. Egy rendőr i. városból a j.-be történő átmozgatásának költsége a városszámok különbségének abszolút értéke: |i-j|
Feladat:
Írj programot (RENDOR.PAS, RENDOR.C, ...), amely kiszámítja az átcsoportosítás lehető legkisebb összköltségét és megadja azt, hogy az átcsoportosítás után mely városokban lesz rendőr.Bemenet:
A RENDOR.BE szöveges állomány első sorában a városok N száma (1<=N<=100) van. A második sorban pontosan N szám van egy-egy szóközzel elválasztva. Az i-edik szám azt adja meg, hogy az i-edik városban kezdetben hány rendőr tartózkodik. Összesen legfeljebb N rendőr van a városokban.Kimenet:
A RENDOR.KI szöveges állomány első sorába azt a legkisebb összköltséget kell írni, amellyel elérhető, hogy a legtöbb városban legyen rendőr. A második sorba pontosan N számot kell írni, az i-edik szám 1-es legyen, ha az i-edik városban lesz rendőr az átmozgatás után, egyébként 0. (Ha több megoldás is van, akkor egy tetszőlegeset ki lehet írni.)Példa:
RENDOR.BE RENDOR.KI 7
0 1 0 3 2 0 05
1 1 1 1 1 1 0
Minden számítógépes hálózat úgy épül fel, hogy csomópontokat kétirányú adatátvitelt biztosító vonal köt össze közvetlenül. Az általunk vizsgált hálózat olyan, hogy minden csomópont legfeljebb három másik csomóponttal van közvetlenül összekötve. A hálózatot úgy alakították ki, hogy megbízható legyen abban az értelemben, hogy bármely két P és Q csomópontja között legyen két olyan útvonal, amelyeknek nincs közös pontja, csak P és Q
Feladat:
Írj programot (HALOZAT.PAS, HALOZAT.C, ...), amely két adott csomópontra meghatároz két olyan útvonalat, amelyeknek a végpontok kivételével nincs közös pontjuk!Bemenet:
A HALOZAT.BE szöveges állomány első sorában négy egész szám, N M P Q van egy-egy szóközzel elválasztva. N (3<=N<=1000) a csomópontok száma, N (3<=M<=3000) a csomópontok közötti közvetlen kapcsolatok száma, P és Q a két kérdéses csomópont sorszáma. A következő M sor mindegyikében egy-egy X Y számpár (1<=X,Y<=N) (X<>Y) van, egy szóközzel elválasztva. Ez azt jelenti, hogy az X és Y csomópontokat kétirányú átvitelt biztosító közvetlen kapcsolat köti össze.Kimenet:
A HALOZAT.KI szöveges állomány két sort tartalmazzon, a megadott P és Q csomópontot összekötő két különböző, közös belső pont nélküli útvonalat. Mind P, mind Q szerepeljen az útvonalban. (Ha több megoldás is van, akkor egy tetszőlegeset ki lehet írni.)Példa:
HALOZAT.BE HALOZAT.KI 7 8 1 5
7 1
4 7
1 2
4 5
3 4
5 6
6 2
3 7
1 7 4 5
1 2 6 5