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. 160. feladat (2022. március)

S. 160. Ádám meg szeretné látogatni Évát. A kettejük közt lévő utak hálózata leírható egy irányítatlan gráffal, melyben a csúcsok a kereszteződések és az élek a köztük lévő utak. Ádám az egyes sorszámú kereszteződésből indul és a legnagyobb, \(\displaystyle N\)-es sorszámúba szeretne eljutni.

Ádám eddig mindig a két pont közötti legrövidebb utak valamelyikén ment. Adjuk meg, hányféle különböző legrövidebb út van a két pont között.

Mivel gyakran megy látogatóba, unja már ezeket a lehetőségeket, így most egy olyan útvonalat szeretne választani, amelynek hossza szigorúan nagyobb, mint a legrövidebb út hossza. Adjunk meg, hogy legalább mekkora lesz az új útvonal hossza.

Bemenet: az első sor tartalmazza a kereszteződések \(\displaystyle N\) és az utak \(\displaystyle M\) számát. A következő \(\displaystyle M\) sor mindegyike egy-egy utat ír le a két végpontjával.

Kimenet: az első sorába a legrövidebb utak száma kerüljön. A kimenet második sorába írjuk az új útvonal minimális hosszát. Ha nincs a legrövidebbnél hosszabb út, akkor -1-et kell kiírni.

Minta:

Bemenet (a / jel sortörést helyettesít) Kimenet (a / jel sortörést helyettesít)
3 3 / 1 2 / 2 3 / 3 1 1 / 2

Korlátok: \(\displaystyle 2\le N\le 300\). Időlimit: 1 mp.

Értékelés: a pontok 50%-a kapható arra a megoldásra, amelynél a kimenet első sora helyes.

Beküldendő egy s160.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ő 2022. április 19-én LEJÁRT.


Statisztika:

5 dolgozat érkezett.
10 pontot kapott:Tóth 057 Bálint.
5 pontot kapott:4 versenyző.

A KöMaL 2022. márciusi informatika feladatai