4. naloga
Mase
V neki tovarni na koncu proizvodnega procesa vsak izdelek stehtajo, maso v gramih pa zapišejo v bazo. Kot vsaka tehtnica ima tudi ta znano svojo natančnost, ki je ±a gramov (torej, če tehtamo izdelek z maso m, lahko tehtnica pokaže katero koli število od vključno m − a do vključno m + a).
Izdelki so različnih vrst, vsi izdelki iste vrste imajo enako maso, izdelki različnih vrst pa imajo različne mase. Težava je v tem, da ne vemo, koliko vrst izdelkov obstaja in kakšne so njihove prave mase. Opiši postopek, ki kot vhodne podatke dobi natančnost tehtnice a in zaporedje meritev (za vsako meritev imamo izmerjeno maso v gramih) ter iz teh podatkov ugotovi, kakšno je najmanjše število različnih vrst izdelkov, pri katerem bi se (glede na dano natančnost tehtnice a) dalo s tehtanjem dobiti takšno zaporedje mas, kot je podano v vhodnih podatkih. Predpostavi, da je vhodno zaporedje meritev podano v naraščajočem vrstnem redu.
Primer: če imamo a = 5 in zaporedje meritev 15, 24, 26, je pravilni odgovor 2. Če bi imeli a = 5 in zaporedje meritev 15, 24, 25, pa bi bil pravilni odgovor 1 (kajti do vseh teh treh meritev lahko pride med drugim tako, da imamo eno samo vrsto izdelkov z maso 20).