Az I. 355. feladat (2014. október)

I. 355. Egy városban \(\displaystyle M\) metróvonal és \(\displaystyle V\) villamosvonal található. Minden metróvonal és villamosvonal megállók rendezett sorozatából áll, ezek mentén lehet mindkét irányban közlekedni. Két vonal között akkor lehet átszállni, ha van azonos nevű megállójuk. Válaszoljunk a következő kérdésekre:

\(\displaystyle a)\) Adjuk meg, hány állomás van a városban.

\(\displaystyle b)\) Adjuk meg, hány megállóból áll a leghosszabb metró- és a leghosszabb villamosvonal.

\(\displaystyle c)\) Adjuk meg azokat a megállókat, melyek nem érhetőek el csak metró használatával.

\(\displaystyle d)\) Adjunk meg két állomást, amelyek a legtávolabb vannak egymástól, és adjuk meg, hogy mekkora ez a távolság. A távolságot most úgy értjük, hogy hány megállót kell megtenni a két állomás közötti legrövidebb úton.

\(\displaystyle e)\) Ha a lehető legkevesebb átszállással akarunk eljutni egy tetszőleges állomásról egy tetszőleges másikra, akkor mennyi az a legkevesebb átszállás, amit legrosszabb esetben mindenképp meg kell tennünk? Adjuk meg az átszállások számát és két olyan állomást, melyek közül az egyikből a másikba ennyi átszállásnál kevesebből nem lehet eljutni.

A program a standard bemenet első sorából olvassa be az \(\displaystyle M\) és \(\displaystyle V\) számokat (\(\displaystyle 1\le M,V\le 100\)), és a következő \(\displaystyle M\) sorból a metróvonalakat: minden sor elején egy egész szám van, a metróvonal megállóinak száma, majd utána a megállók nevei vesszőkkel és egy szóközzel elválasztva. Ezután a következő \(\displaystyle V\) sorban ugyanígy a villamosvonalak leírása található. A program írja ki a standard output első öt sorába a kérdésekre adott válaszokat.

Beküldendő egy tömörített i355.zip állományban a program forráskódja (i355.pas, i355.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (i355.txt, i355.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2014. november 10-én LEJÁRT.

Kovács Benedek 10 pontos megoldása:

I355.zip

Statisztika:

15 dolgozat érkezett.
10 pontot kapott:	Kovács 246 Benedek, Mócsy Miklós, Nagy Ábel, Olexó Gergely.
9 pontot kapott:	Dombai Tamás.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	5 versenyző.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2014. októberi informatika feladatai