 |
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 2 | 10 |
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.
Egy \(\displaystyle (i,j)\) pár akkor jó megoldás, ha a köztük lévő élek behúzásával körmentes gráfot kapunk.
Minden \(\displaystyle i\) számra meg kell határoznunk a legnagyobb \(\displaystyle j\) értéket, melyre a feltétel teljesül. A megoldás ezen intervallumok hosszának összege lesz.
Egy pár leellenőrzése megtehető bejárással vagy unió-holvan adatszerkezettel.
A teljes pontszámot több módszerrel is el lehet érni. Ilyen például a gyökös felbontás, mely sok hasonló problémát fel tud gyorsítani. (A 10 000-es felső korlát gyakori árulkodó jel ilyen feladatoknál.)
Megjegyezzük, hogy a feladat megoldására kész adatszerkezet is létezik, mely sok helyen elérhető online is. (link: Link/cut tree) Ennek implementálása nem volt elvárt!
Statisztika:
6 dolgozat érkezett. 5 pontot kapott: 4 versenyző. 4 pontot kapott: 1 versenyző. Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt: 1 dolgozat.
A KöMaL 2021. októberi informatika feladatai