NézetNyomtat

Titkos társaság
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2003 > Döntő > 11-13. osztály

Titkos társaság

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!
A: Hány beosztottja - nem csak közvetlen - van az X és Y tagnak?
B: Hány lépéssel továbbítódik egy levél, ha X küld levelet Y-nak?
C: 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?

Bemenet:

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 50 1 1 3 3 5 5 0 234

Tesztadatok: