 |
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 6 | 1 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.
Két fő esetünk van:
Ha eltávolítunk egy adott pontot, akkor a fa leghosszabb útjának hossza nem változik, vagy változik.
Mindkét esetet figyelembe kell venni, hogy optimálisan válasszunk.
Részletes leírás ábrával az egyedüli maxpontos Horcsin Bálint megoldásában:
Statisztika:
4 dolgozat érkezett. 10 pontot kapott: Horcsin Bálint. 9 pontot kapott: Varga 256 Péter. 6 pontot kapott: 1 versenyző. 5 pontot kapott: 1 versenyző.
A KöMaL 2020. decemberi informatika feladatai