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 I/S. 29. feladat (2018. október)

I/S. 29. Egy ország városait kétirányú utak kötik össze, melyek használatáért díjat kell fizetni. Bármelyik városból bármelyik városba el lehet jutni az utakon. Két város között legfeljebb egy közvetlen út van. Néhány városban szupermarket is található. Az országba \(\displaystyle Q\) család érkezik, akik különböző vagyoni helyzetűek. Minden család szeretne olyan városba költözni, ahol nincs szupermarket. Ha egy család vagyoni helyzete \(\displaystyle K\), akkor csak olyan városban lakhat, ahonnan el tud menni bevásárolni egy szupermarketbe összesen legfeljebb \(\displaystyle K\) útdíjat fizetve (az oda- és visszautat számolva). Adjuk meg minden családra, hogy hány olyan város van az országban, ahol nincs szupermarket, mégsem tud odaköltözni a család, mert túl költséges lenne egy szupermarketbe való eljutás a vagyoni helyzetükhöz képest.

Bemenet: Az első sor tartalmazza a városok \(\displaystyle N\) számát, az utak \(\displaystyle M\) számát, a szupermarketet tartalmazó városok \(\displaystyle D\) számát és a családok \(\displaystyle Q\) számát. A következő \(\displaystyle M\) sor mindegyike három számot tartalmaz: az első kettő azon városok indexe, amik között az adott út van, a harmadik szám pedig az út használatának díja. A következő sorban \(\displaystyle D\) szám van: azon városok indexei, amikben van szupermarket. A következő sorban \(\displaystyle Q\) szám van: az \(\displaystyle i\)-edik szám az \(\displaystyle i\)-edik család vagyoni helyzetét leíró \(\displaystyle K\) érték. A városokat 0-tól \(\displaystyle N-1\)-ig indexeljük.

Kimenet: Egy sorba írjunk ki \(\displaystyle Q\) darab számot: a sor \(\displaystyle i\)-edik száma adja meg, hogy az \(\displaystyle i\)-edik család hány olyan városba nem tud költözni a vagyoni helyzete miatt, ahol nincs szupermarket.

Korlátok: \(\displaystyle 1\le D<N\le {10}^{5}\), \(\displaystyle 1\le M\le 5\cdot {10}^{5}\), \(\displaystyle 1\le Q\le {10}^{5}\), \(\displaystyle 0\le \text{egy}\) út díja, \(\displaystyle K\le 2\cdot 10^{9}\), egészek. Időkorlát: 0,5 s, memórialimit 100 MiB.

Értékelés: a pontok 20%-a kapható, ha minden út díja 1; további 20% kapható, ha \(\displaystyle D=1\); további 20% kapható, ha \(\displaystyle Q=1\); további 40% kapható az eredeti korlátokra.

Az I/S és S-jelű feladatok megoldását a http://mester.inf.elte.hu automatikus értékelő rendszer segítségével kipróbálhatod, tesztelheted (Téma: KöMaL - 2018/19).

(10 pont)

A beküldési határidő 2018. november 12-én LEJÁRT.


Statisztika:

13 dolgozat érkezett.
10 pontot kapott:Csertán András, Molnár Bálint, Noszály Áron, Szente Péter, Tóth 827 Balázs, Varga 256 Péter.
8 pontot kapott:1 versenyző.
5 pontot kapott:1 versenyző.
4 pontot kapott:1 versenyző.
3 pontot kapott:1 versenyző.
1 pontot kapott:3 versenyző.

A KöMaL 2018. októberi informatika feladatai