Loading [MathJax]/jax/output/HTML-CSS/jax.js
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. 165. feladat (2022. november)

S. 165. Egy gyorsétteremlánc két különböző étteremben dolgozó alkalmazottja rájött, hogy ha a jelenlegi munkahelyük helyett egymás munkahelyére járnának dolgozni, akkor mindkettőjüknek kevesebbet kellene utazni. Szeretnének javaslatot tenni a felettesüknek a munkahelyek újraosztására, de a probléma sajnos túl bonyolultnak bizonyult, hogy papíron kiszámolják.

Adott egy város úthálózata, mely csúcsokból és az őket összekötő súlyozott élekből áll. Van továbbá valahány éttermünk és D alkalmazottunk, akikről tudjuk, honnan és hova járnak dolgozni. A feladatunk úgy újraosztani a munkahelyeket, hogy az alkalmazottak munkahelytől vett távolságának összege a lehető legkisebb legyen. (Tegyük fel, hogy a dolgozóknak egyéb preferenciája nincs.)

A bemenet első sorában a csúcsok N és az élek M száma található. A következő M sor egy-egy utat ír le, a két végpontjának sorszámával és az él súlyával (az út hosszával). Ezután az alkalmazottak D száma, majd D sorban az alkalmazottak lakhelyének és munkahelyének csúcsszáma található. Mindent 0-tól indexelünk és egy csúcsban legfeljebb egy étterem van.

A kimenet egyetlen sorában az elérhető legkisebb távolságösszeg szerepeljen, ha az újraosztás után minden étteremben ugyanannyian dolgoznak, mint előtte.

Példa:

Megjegyzés: Mint ahogy a példa is mutatja, előfordulhat, hogy valaki így többet fog utazni.

Korlátok: N500, M1000, D100. Időlimit: 1 mp.

Értékelés: A pontok 50%-a kapható, ha a program helyes kimenetet ad a D10 esetekre.

Beküldendő egy s165.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ó. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

A beküldési határidő 2022. december 15-én LEJÁRT.


Statisztika:

2 dolgozat érkezett.
5 pontot kapott:2 versenyző.

A KöMaL 2022. novemberi informatika feladatai