ACM RTK - 2. skupina

Največji pretok

Imamo mrežo enostavnih merilnih računalnikov. Vsakega sestavlja procesor, senzor in pet komunikacijskih kanalov. Štirje kanali so namenjeni povezavi med računalniki: L (levo), D (desno), Z (zgoraj) in S (spodaj). Peta povezava, M (merilnik) sprejema podatke od senzorja.

Računalniki so s kanali L, D, Z in S povezani v dvodimenzionalno mrežo.

Mrežo potopimo v reko, pri čemer merilniki na posameznih računalnikih merijo pretok vode v reki. Na zgornji levi računalnik priključimo prenosnik, ki bo zajemal podatke.

Na vseh računalnikih je pognan enak program, ki se izvaja v neskončni zanki. Program ima na voljo funkciji Beri in Pisi.

function Beri(Kanal: char): integer;               { v pascalu }
procedure Pisi(Kanal: char; Vrednost: integer);

int Beri(char kanal);                              /* v C/C++ */
void Pisi(char kanal, int vrednost);

public static int Beri(char kanal);                // v javi/C#
public static void Pisi(char kanal, int vrednost);

def Beri(kanal): ... # vrne                        # v pythonu
int def Pisi(kanal, vrednost): ...

Funkcija Beri prebere podatek iz komunikacijskega kanala (če je na voljo) in vrne njegovo vrednost. Če je kanal prazen ali pa ni nikamor povezan (večina kanalov na robu mreže), funkcija vrne −1.

Podprogram Pisi zapiše podatek na podani kanal. Predpostaviš lahko, da je v kanalu vedno dovolj prostora za zapis podatka. Če ta kanal ni nikamor povezan, podprogram ne naredi ničesar.

S prenosnikom, priključenim na zgornji levi računalnik, bi radi prebrali največji izmerjeni pretok reke v celem omrežju. Napiši program, ki se bo izvajal na vseh računalnikih v omrežju in bo poskrbel za to, da bo zgornji levi računalnik na kanal L pošiljal največji doslej zaznani pretok (največji od začetka delovanja celotne mreže). Predpostavi, da so procesorji hitri, komunikacija med njimi tudi, sprejemljivo pa je, če pride podatek o največjem pretoku do zgornjega levega računalnika z majhno zakasnitvijo.

PDF besedilo.