ACM RTK - 2. skupina

Virus

V računalniškem podjetju so naredili 1000 zgoščenk z nekim programom, namenjenim za prodajo. Žal pa je na eno izmed zgoščenk zašel tudi virus, ki ga želimo odkriti in tisto zgoščenko uničiti. Okuženo zgoščenko bi radi našli čim prej tako, da zgoščenke testiramo na enem ali več računalnikih. Na enem računalniku lahko poženemo poljubno mnogo zgoščenk. Če je na nekem računalniku med zagnanimi zgoščenkami bila tudi taka z virusom, se bo računalnik do naslednjega dne sesul. Takrat (torej naslednji dan) ga lahko ponovno usposobimo in ga uporabimo za nadaljnje poskuse.

Čas za zagon zgoščenk je zanemarljivo majhen (lahko ga odmisliš). Virus iz okuženega računalnika se ne bo razširil na druge zgoščenke.

Opiši postopek, kako na računalnikih poganjati zgoščenke, da ugotovimo, katera zgoščenka je okužena z virusom. Pravzaprav opiši dva postopka (vsak je vreden polovico točk pri tej nalogi) z naslednjimi omejitvami:

1. Za eksperimentiranje imamo na voljo le en računalnik, zgoščenko pa bi radi našli v minimalnem številu dni.
2. Zgoščenko moramo najti v enem dnevu, za eksperimentiranje pa želimo uporabiti čim manj računalnikov (po možnosti precej manj kot 1000).