 |
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 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
Xi,YiN), illetve az összekötés 0Di1000 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