ACM

SZTE csapatverseny
1998



Repülés (airlines)
A World Wide Airlines (WWA) repülőgépeket üzemeltet. Minden gép a központi reptérről indul, először az A, majd a B repteret érinti és visszatér a központi reptérre. A járathálózatot úgy kell megtervezni, hogy a WWA minden repülőtere elérhető legyen a központi reptérről induló járatok valamelyikével. A járathálózat jellemzője, hogy nincs két olyan járat, amelynek első megállója ugyanaz lenne.

Feladat:

A WWA igazgatója csökkenteni akarja a járatszámot, megtartva az összes reptér elérhetőségét. Meg akarja tudni, mennyi az a minimális járatszám, amellyel a feladat megoldható.

Írj programot, amely meghatározza ezt a számot.

Bemenet:
A bemenet első sora egy N (3<=N<=500) egész számot tartalmaz, amely megadja a repterek számát. (A reptereket az 1..N számokkal azonosítjuk.) A központi repteret az 1-es szám jelöli. A következő sor által megadott M szám (1<=M<N) a járatok számát adja meg. Az ezt követő M sorban két különböző egész szám, X és Y van egyetlen szóközzel elválasztva. A számok egy járatot adnak meg, amely útja során először az X, majd az Y repteret érinti. Minden repteret érint legalább egy járat.
Kimenet:
A programnak egyetlen egész számot kell írnia a kimenet első sorába, a minimális járatszámot, amely szükséges a repterek összekötéséhez.
Példa:
 
airlines.in airlines.out
10
8
2 3
3 4
4 5
5 3
6 7
7 4
8 4
9 10
5


Festés (paint)
Az egyik vállalatnál automatikusan festik a szállítószalagon érkező dobozokat. Minden dobozt a négy különböző színből a megfelelőre kell festeni. A festőgépbe csak két különböző színű tartályt lehet felszerelni egyidejűleg. Ha nem az aktuális dobozhoz tartozó színű tartály van a gépben, a tartályt a kívánt színűre kell cserélni. A színcsere művelete időigényes, ezért minimalizálni kell a cserék számát. A színcsere elvégzése az egyik felcsatolt szín leválasztása, majd a kívánt szín felkapcsolása. A tartályok fel és lekapcsolása eltérő időbe telik.

Feladat:

Írjon programot, amely meghatározza a cserékhez szükséges minimális teljes időt a megadott inputhoz.
Bemenet:
A négy használt színt az A, B, C, D betűk jelölik.

A bemenet első sorában négy 100-nál nem nagyobb egész található, amely megfelelő színű tartályok felkapcsolásához szükséges időt jelzi. A második sorban négy 100-nál nem nagyobb egész található, amely megfelelő színű tartályok lekapcsolásához szükséges időt mutatja meg. A színek sorrendje mindkét esetben A, B, C, D. A harmadik sor az N (1<=N<=10000) egész számot tartalmazza, amely a befestendő dobozok számát jelenti. Az utolsó sorban N karakter van, melyek mindegyike az A, B, C, D karakterek egyike. Munkakezdéskor az A és a B tartályok vannak felcsatolva.

Kimenet:
A kimeneti állomány első sorába egyetlen egész szám kerüljön, amely a cserékhez szükséges összidőt adja meg.
Példa:
 
paint.in paint.out
1 2 7 1
4 1 3 2
12
ACDCBBACCDBC
28