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. 155. feladat (2021. október)

S. 155. Egy titkosszolgálat tagjai laza kapcsolatban állnak egymással. Ha egy tag megkap egy titkos információt, azt csak a bizalmasainak adja tovább, kivéve annak, akitől a hírt kapta. Így előfordulhat, hogy egy hír olyan ügynökhöz kerül, aki már hallotta azt. Ezt mindenképp el szeretnék kerülni.

A szolgálat tagjait pozitív egész számok jelölik. A titkosszolgálat vezetője minden tagtól bekérte, hogy kik a bizalmasai. A kapott információkat mappákban helyezte el, így mindegyik nappában egy-egy számpár szerepelt: két olyan ügynök sorszáma, akik kölcsönösen bíznak egymásban.

A titkosszolgálat vezetője sorba állította a mappákat, és a hírek továbbítására a következő stratégiát gondolta ki: minden hír esetén kiválaszt egy \(\displaystyle i\) és egy \(\displaystyle j\) számot, majd a hír továbbításánál csak azokat a \(\displaystyle k\) sorszámú mappákat tartja meg, melyekre \(\displaystyle i\le k\le j\). A hírt a kiválasztott mappákban szereplő egyik személlyel közli. Ezután mindenki csak olyan ügynöknek adhatja tovább a hírt, akivel a közös mappájuk a kiválasztottak között szerepel. Adjuk meg, hányféleképpen választhatja ki az \(\displaystyle i\) és \(\displaystyle j\) számokat úgy, hogy a megtartott mappákban szereplő bármely ügynöktől indulva a hír nem jut el kétszer egyik ügynökhöz sem.

Bemenet: az első sor tartalmazza az ügynökök \(\displaystyle N\), és a kapcsolatok \(\displaystyle M\) számát. A következő \(\displaystyle M\) sor mindegyike egy bizalmi kapcsolatot ír le, abban a sorrendben, ahogy a vezető rendezte.

Kimenet: a kimenet első és egyetlen sorába a megfelelő \(\displaystyle (i,j)\) párok számát kell írni. (Két pár akkor különböző, ha legalább az egyik tagja különböző.)

Minta:

Bemenet (a / jel sortörést jelent)Kimenet
4 5 / 1 3 / 3 2 / 2 1 / 1 4 / 4 210

Magyarázat: a lehetséges \(\displaystyle (i, j)\) párok: \(\displaystyle (1, 1)\), \(\displaystyle (1, 2)\), \(\displaystyle (2, 2)\), \(\displaystyle (2, 3)\), \(\displaystyle (2, 4)\), \(\displaystyle (3, 3)\), \(\displaystyle (3, 4)\), \(\displaystyle (4, 4)\), \(\displaystyle (4, 5)\), \(\displaystyle (5, 5)\).

Korlátok: \(\displaystyle 3\le N,M\le 10\,000\). Időlimit: 0,5 mp.

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

Megjegyzés: egy-egy hírt nem feltétlenül kap meg minden ügynök.

Beküldendő egy s155.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. november 15-én LEJÁRT.


Statisztika:

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


A KöMaL 2021. októberi informatika feladatai