Glasniki v vasi (3.junij 2018 - 8. nov. 2019)
Zahteve zaključka
Odprto: nedelja, 3. junij 2018, 00.00
Rok za oddajo: petek, 22. junij 2018, 23.55
Vas ima
1000 prebivalcev. Vemo, da vsak pove novico vsem svojim znancem v
enem dnevu. Koliko
ljudi najmanj moramo izbrati v tej vasi, da jim sporočimo novico, če
jo morajo v 10-ih dneh iz
vedeti prav vsi vaščani,
vemo pa le, da se vsaka novica razširi na vse vaščane?
Opomba. Naš algoritem za izbiro `glasnikov' dobi kot vhod, kdo je s kom znanec, nima pa kontrole nad strukturo teh poznanstev (tj. delovati mora v vsaki taki vasi).