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. 51. feladat (2010. február)

S. 51. Egy vállalatnál az informatikai infrastruktúra modernizálásának jegyében ún. ultravékony kliensek bevezetését tervezik: az asztali számítógépeket egy-egy végtelenül egyszerű berendezéssel helyettesítik, melyek feladata mindössze annyi, hogy a billentyűzetről és az egérről érkező bemenetet egy központi szerverre továbbítsák, majd az onnan érkező kimenetet megjelenítsék a képernyőn. A programok futtatását, illetve minden ezzel kapcsolatos számítást valójában a központi szerver végez.

A rendszernek, számos előnye mellett, hátránya, hogy érzékeny a hálózati késleltetésre. Ezért a szervert optimálisan úgy kell elhelyezni, hogy a kliensek szervertől vett késleltetéseinek maximuma minimális legyen.

Írjunk programot, mely meghatározza, hogy a szerver optimális elhelyezése esetén mekkora lesz a hálózati késleltetés a szerver és a tőle legtávolabb eső kliens között. A hálózat fatopológiájú, tehát bármely két csúcs között pontosan egy út vezet. A kliensek a hálózat végpontjaiban (a fa leveleiben) helyezkednek el, a szervert pedig valamely belső csomópontba kell telepíteni.

A program a hálózat leírását a standard bemenetről olvassa. A bemenet első sora egyetlen egész számot, a csúcsok 1\le N\le 10\;000 számát tartalmazza. Az ezt követő N-1 sor mindegyike három, szóközzel elválasztott egész számot tartalmaz, egy-egy hálózati összekötés végpontjainak Xi és Yi sorszámát (1\leXi,Yi\leN), illetve az összekötés 0\leDi\le1000 késleltetését (a két végpontbeli feldolgozáshoz szükséges idő elhanyagolható).

A program a megoldást a standard kimenetre írja, melynek egyetlen sora egyetlen M egész számot tartalmazzon: az optimális szerverelhelyezés esetén a késleltetések maximumát.

A feladathoz kiadott tesztesetek: s51test.zip

(10 pont)

A beküldési határidő 2010. március 10-én LEJÁRT.


Statisztika:

13 dolgozat érkezett.
9 pontot kapott:Éles András.
8 pontot kapott:4 versenyző.
7 pontot kapott:2 versenyző.
6 pontot kapott:3 versenyző.
5 pontot kapott:2 versenyző.
4 pontot kapott:1 versenyző.

A KöMaL 2010. februári informatika feladatai