Algoritmi in podatkovne strukture (23/24)

V raznih trgovinah delijo razne sličice, od Živalskega kraljestva do slik junakov iz najnovejše risanke v kinu. Neki zbiralci hranijo sezname sličic, ki jih imajo, v datotekah takšne oblike:

1-2
7-16
18-28
35-35
42-45

Tale, recimo, ima prvi dve sličici, potem sličice od 7 do 16 (vključno s 16) in tako naprej. Številka prve je vedno 1, številka zadnje pa je zadnja številka v katerikoli izmed datotek (kadar je zbiralcev več, je več tudi datotek).

Intervali v teh datotekah so vedno urejeni. Interval lahko vsebuje utdi le eno sličico, npr. 35-35.

Za ogrevanje lahko napišete funkcijo, ki prebere datoteko in izpiše datoteko z vsemi manjkajočimi slikami, v obliki

3-6
17-17
29-34
36-41

Prava naloga pa je takšna: imamo več zbiralcev, vsakega s svojo datoteko. Zamisli si algoritem, ki sestavi datoteko z intervali številk slik, ki jih nima nobeden od njih.

1. Obstaja preprost postopek, ki ustreza temu, da preprosto "zložijo slike skupaj". Zahteval bo čas, sorazmeren številki zadnje slike, in prav toliko pomnilnika. Opiši postopek in ga sprogramiraj. Za to nalogo zadošča, da program izpiše število manjkajočih slik, ne nujno intervalov.
2. Sestavi boljši, hitrejši postopek, katerega časovna in pomnilniška zahtevnost ne bosta odvisna od številke zadnje slike. Opiši ga in ga sprogramiraj. V tej točki smeš predpostaviti, da je intervalov sorazmerno malo (lahko gre v tisoče, ne pa v milijarde), prav tako je zbiralcev le nekaj (na primer ducat). Kakšna je časovna zahtevnost sestavljenega algoritma glede na število intervalov in število zbiralcev?
3. Kaj pa, če je zbiralcev veliko, na primer tisoče? Kako spremeniti algoritem, da bo imel manjšo časovna zahtevnost glede na število zbiralcev? Opišite, sprogramirajte. Kakšna je njegova časovna zahtevnost glede na število intervalov in število zbiralcev

Za pozitivno oceno morate sestaviti vsaj algoritem in program, ki reši točko 1, torej za datoteke iz primer1, primer2 in primer3 pove število manjkajočih sličic. Za višje ocene pa morate čim boljše rešiti čimveč izmed ostalih nalog.

Nalogi je priloženih pet primerov; v primer1 imamo le enega zbiralca, v primer2 dva in v primer3 več. Vsi trije so primerni za prvo točko. V primer4 in primer5 imamo kartice z groteskno velikimi številkami; to je za točki 3 in 4. Datoteke z intervali z v karticeN.txt znotraj teh direktorijev. Datoteke manjkajoci.txt vsebujejo, kar mora izpisati vaš program.

V datoteki pomoc.py so vam podarjene tri funkcije, ki jih lahko uporabite pri reševanju.

Oddajte besedilo kot .pdf, programe pa v eni ali več datotekah .py.