 |
Az S. 156. feladat (2021. november) |
S. 156. Piripócson \(\displaystyle N\) utca van, melyek \(\displaystyle N\) csomópontban találkoznak. A csomópontok 1-től \(\displaystyle N\)-ig számozottak. Minden utca két csomópontot köt össze. Az utcákon két irányban lehet közlekedni és bármely csomópontból el lehet jutni bármelyik másikba. Egy turisztikai cég olyan túrát tervez, mely pontosan \(\displaystyle K\) utcán megy keresztül. Minden utcán legfeljebb egyszer haladnak át, és a túrán az egymás után következő utcák egyik végpontja közös.
Készítsünk programot, amely megadja, hogy hányféle túrát szervezhetnek. Két túra csak akkor különböző, ha van olyan utca, amit az egyik túra érint, de a másik nem.
Bemenet: az első sor tartalmazza a csomópontok \(\displaystyle N\) számát és a túra \(\displaystyle K\) hosszát. A következő \(\displaystyle N\) sor mindegyike egy-egy utca két végét írja le.
Kimenet: a kimenet első és egyetlen sorába a \(\displaystyle K\) hosszú túrák számát kell kiírni.
Példa:
| Bemenet (a / jel sortörést helyettesít) | Kimenet |
| 4 2 / 1 2 / 1 3 / 2 3 / 2 4 | 5 |
Korlátok: \(\displaystyle 3\le N\le 500\), \(\displaystyle 1\le K\le 20\). Időlimit: 0,5 mp.
Értékelés: a pontok 50%-a kapható, ha a program az \(\displaystyle N\le 50\) elemszámú tesztesetekre helyes megoldást ad.
Beküldendő egy s156.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. december 15-én LEJÁRT.
Sándor Péter megoldása alapján:
Egy \(\displaystyle N\) csúcsú fagráfnak \(\displaystyle N-1\) éle van, tehát a feladatban szereplő \(\displaystyle N\) élű gráfban \(\displaystyle 1\) extra él van. Ez pontosan egy kört hoz létre.
Ezt a kört megkeressük. A kör csúcsait elhagyva fagráfokat (erdőt) kapunk.
A \(\displaystyle K\) hosszú utak megkeresését két alesetre bontjuk:
1. Nem megy át a kör egy élén sem (vagyis egy előbb említett fából nem lép ki)
Minden, az adott részgráfbeli pontra megkeresem, hogy mennyi tőle "k" távolságra lévő pont van az adott részgráfban. (Így mindent kétszer számolok, emiatt az eredményt elosztom kettővel)
2. Tartalmazza a kör valamely élét. Ekkor úgy néz ki a \(\displaystyle K\) hosszú út, hogy: egy fából kiindul, átmegy a kör valamennyi élén, majd átmegy egy másik fába ahonnan már nem léphet ki (mivel az fagráf).
A kör minden pontjához hozzárendelek egy tömböt ami azt tartalmazza, hogy ha az adott pont mint a megfelelő részgráf gyökere, akkor tőle mely távolságra mennyi pontja van a fagráfnak. (Ezt egy egyszerű DFS-el megtehetjük). Miután ezek a tömbök fel vannak töltve, azt figyelembe véve, hogy mely részgráf milyen távolságra csatlakozik a körökhöz, és a kiszámolt tömbök megfelelő elemeinek összeszorzásával ki tudjuk számolni a \(\displaystyle K\) hosszú utakat.
Statisztika:
4 dolgozat érkezett. 10 pontot kapott: Sándor Péter, Tóth 057 Bálint, Veres Benedek Zoltán. 3 pontot kapott: 1 versenyző.
A KöMaL 2021. novemberi informatika feladatai