Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 148. feladat (2020. december)

S. 148. Adott egy \(\displaystyle N\) csúcsú fa. Megkértek minket, hogy töröljük ennek a fának az egyik levelét, tehát egy olyan csúcsot, aminek pontosan egy éle van. Jelöljük ezt a levelet \(\displaystyle L\)-lel. A törlés után visszamarad egy \(\displaystyle N-1\) csúcsú fa. Ebben az új fában jelöljük \(\displaystyle D\)-vel két, egymástól legmesszebb levő pont távolságát, és \(\displaystyle P\)-vel azon (nem rendezett) pontpárok számát, amelyek távolsága \(\displaystyle D\). Adjuk meg \(\displaystyle P\) minimális értékét és azt, hogy ehhez hányféleképpen választhatjuk meg az \(\displaystyle L\) levelet (amit törlünk).

Bemenet: az első sor tartalmazza az \(\displaystyle N\) számot. A csúcsokat 0-tól indexeljük. A következő \(\displaystyle N-1\) sor mindegyike egy \(\displaystyle x\) és egy \(\displaystyle y\) számot tartalmaz, ami azt jelenti, hogy az \(\displaystyle x\)-edik és \(\displaystyle y\)-adik csúcsot él köti össze.

Kimenet: adjuk meg \(\displaystyle P\) minimális értéket, és azt, hogy az hányféleképpen érhető el.

Példa:

Bemenet (a / jel sortörést helyettesíti) Kimenet
7 / 0 1 / 1 2 / 1 3 / 3 4 / 3 5 / 5 61 2

Magyarázat: ha töröljük a 0-s csúcsot, akkor \(\displaystyle D=4\), és a 2-es és 6-os csúcsok távolsága 4, tehát \(\displaystyle P = 1\). Ha töröljük a 2-es csúcsot, akkor \(\displaystyle D=4\), és a 0-s és 6-os csúcsok távolsága 4, tehát \(\displaystyle P = 1\). Két esetben kaptunk minimális \(\displaystyle P=1\)-et, a többi esetben \(\displaystyle P\) nagyobb lesz.

Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 0\le x,y\le N-1\). Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N \le 100\).

Beküldendő egy s148.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2021. január 15-én LEJÁRT.


Statisztika:

Az S. 148. feladat értékelése még nem fejeződött be.


A KöMaL 2020. decemberi informatika feladatai