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. 140. feladat (2020. január)

S. 140. Egy titkosszolgálatnak \(\displaystyle N\) db számítógépe van, melyek közül néhányat kétirányú adatátvitelt biztosító kábelek kötnek össze, melyekből legfeljebb \(\displaystyle M\) db van. Az \(\displaystyle i\)-edik kábelnek öt fontos tulajdonsága van: \(\displaystyle a_{i}\), \(\displaystyle b_{i}\), \(\displaystyle t_{i}\), \(\displaystyle x_{i}\), \(\displaystyle y_{i}\), mely azt jelenti, hogy az \(\displaystyle a_{i}\) és \(\displaystyle b_{i}\) sorszámú számítógépek között egy információcsomag átküldése \(\displaystyle t_{i}\) időbe telik. Hogy biztonságosabbá tegyék a rendszert a hackertámadásokkal szemben, felváltva \(\displaystyle x_{i}\) ideig engedélyezik, majd \(\displaystyle y_{i}\) ideig megtiltják az adatátvitelt az \(\displaystyle i\)-edik kábelen. Kezdetben minden kábelen engedélyezve van az adatátvitel. Két számítógép között csak akkor küldhetünk át egy információcsomagot, ha a küldéstől a megérkezésig minden időpillanatban engedélyezve van az adott kábelen az adatátvitel. A \(\displaystyle K\)-adik számítógépről szeretnénk egy csomagot küldeni a \(\displaystyle V\)-edik számítógépre. Adjuk meg, hogy a csomag leghamarabb mikor érhet oda.

Standard bemenet: az első sor tartalmazza a számítógépek \(\displaystyle N\) számát, a kábelek \(\displaystyle M\) számát, valamint a \(\displaystyle K\) és \(\displaystyle V\) számítógépsorszámokat. Ezután \(\displaystyle M\) sor következik, ahol az \(\displaystyle i\)-edik sor tartalmazza az \(\displaystyle a_{i}\), \(\displaystyle b_{i}\), \(\displaystyle t_{i}\), \(\displaystyle x_{i}\), \(\displaystyle y_{i}\) számokat ebben a sorrendben.

Standard kimenet: adjuk meg, hogy leghamarabb mikor juthat el egy információcsomag a \(\displaystyle K\)-adik számítógépről a \(\displaystyle V\)-edik számítógépre. Ha nem juttatható el az információcsomag, akkor -1-et írjunk ki.

Példa:

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

Korlátok: \(\displaystyle 2\le N\le {10}^{5}\), \(\displaystyle 1\le M\le {10}^{6}\), \(\displaystyle 1\le t_{i}\), \(\displaystyle x_i,y_i\le {10}^{9}\), \(\displaystyle 1\le a_{i}, b_{i}, K, V\le N\). Időkorlát: 0,3 mp.

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

Beküldendő egy s140.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ő 2020. február 10-én LEJÁRT.


Statisztika:

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


A KöMaL 2020. januári informatika feladatai