ACM RTK - 2. skupina

Ribič

Nadebuden ribič se je odpravil k potoku, v katerem namerava z mrežo dolžine d uloviti točno k rib, ki jih bo prinesel domov za kosilo. Voda je kristalno čista, zato točno ve, kje se nahaja katera od n rib. Za potrebe naloge lahko potok predstavimo z ravno črto, ribe pa s točkami x_i na njej. Mrežo bo vrgel tako, da se bo začela na neki celoštevilski koordinati x. Pri tem bo ujel vse ribe, ki se nahajajo na koordinatah od vključno x do vključno x + d − 1. Opiši postopek, ki izračuna, na koliko načinov lahko ribič vrže mrežo, da bo ujel točno k rib.

Predpostavi, da so dolžina d in koordinate x_i cela števila v razponu od 1 do 109, k in n pa sta celi števili med 1 in 106. Zato naj bo tvoj postopek čim bolj učinkovit (bolj učinkovite rešitve dobijo več točk). Koordinate x_i so že podane v naraščajočem vrstnem redu in nobeni dve ribi se ne nahajata na isti koordinati.

Primer: če imamo n = 6 rib na koordinatah 1, 5, 6, 10, 12, 15 in mrežo dolžine d = 8, s katero bi radi ujeli natanko k = 3 ribe, potem je primernih položajev mreže (torej primernih vrednosti x) devet (to so −1, 0, 1, 3, 4, 6, 8, 9, 10). Položaj x = 5 na primer ni primeren, ker pri njem ujamemo 4 ribe, ne 3; položaja x = 2 in x = 7 nista primerna, ker takrat ujamemo le 2 ribi, ne 3.