Megpróbálom sorra venni a 2013-as válogatóverseny feladatait.

Feladat

Adott egy bináris fa (van egy gyökérpont, az 1-es csúcs, és minden csúcsnak lehet egy bal és egy jobb oldali gyereke – és persze a gyökér kivételével pontosan egy szülője van). Keressük meg a gyökérhez legközelebbi olyan csúcsot, hogy az abból „leszármazó” részfa szimmetrikus, azaz a jobb és bal oldali részfák egymás tükörképei.

input

Az első sorban az összes csúcs száma, N, majd a gyerekkel rendelkező csúcsok M száma található, ahol 1<=M<=N<=10 000. A következő M sor tartalmazza az elágazásokat: minden sorban három szám található, sorra a szóban forgó csúcs, a bal oldali gyereke és a jobb oldali gyerekének sorszáma. Ha valamelyik oldalon nincs gyerek, akkor 0-t írunk.

output

Az output egyetlen szám: a keresett csúcs sorszáma (ha több lehetőség van, akkor mindegy, melyik).

Olimpiai válogatóverseny, 2013/1

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.