ACM RTK - 2. skupina

Prenova ceste

V bližini mesteca Cocklebiddy v Zahodni Avstraliji se nahaja najdaljša popolnoma ravna cesta na svetu. Zaradi nedavnih poplav morajo prenoviti 100km ceste. Za popravilo ceste kandidirata dve podjetji, Kangaroads Ltd. in Wallabyway Inc. Vzdolž cestnega odseka, ki ga je treba popraviti, živi 1.000.000 prebivalcev¹ in vsak od njih ima svoje mnenje o tem, katero podjetje bi moralo popravljati cesto.

Na koncu so se prebivalci odločili za kompromis: cesto lahko popravljata obe podjetji, pri čemer bo vsak še tako majhen košček ceste popravilo tisto podjetje, za katerega glasuje večina od k najbližje stanujočih prebivalcev; k je liho število.

Opiši postopek, ki izračuna, koliko kilometrov ceste bo popravilo podjetje Kangaroads Ltd. in koliko Wallabyway Inc. Predpostavi, da že obstajajo naslednje spremenljivke: k, kot je opisan zgoraj; tabela x, kjer je x[i] realno število med 0 in 100 in opisuje položaj i-tega prebivalca (oddaljenost od zahodnega konca popravljanega odseka ceste, v kilometrih), ter tabela p, kjer je p[i] enak 0, če i-ti prebivalec glasuje za podjetje Kangaroads Ltd., in 1 sicer. Vse koordinate prebivalcev so različne in so podane v naraščajočem vrstnem redu.

¹ Poplave in kakšnih 999.950 prebivalcev je izmišljenih; tisto o najdaljši ravni cesti je pa res, dolga je 90 milj.