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ó.Bemenet:Írj programot, amely meghatározza ezt a számot.
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 105
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.Kimenet: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.
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
ACDCBBACCDBC28