Tekmovalni dnevi Instituta Jožef Stefan

Kino

Podroben opis naloge

Kinematografi, ki v nekem manjšem mestecu upravljajo s kinom, te prosijo za pomoč pri sestavljanju filmskih sporedov. Njihov kino ima eno samo dvorano in obratuje cel dan in to vse dni v letu. Leto ima 366 dni, znano pa je tudi število sedežev v dvorani; največ toliko ljudi lahko torej hkrati gleda neko predstavo.

Kinematografi si želijo, da bi prodali čimveč vstopnic, zato so nedavno izvedli med prebivalci svojega mesteca podrobno anketo. Zdaj točno poznamo število prebivalcev in za vsakega prebivalca vemo tudi to, kdaj (ob kateri uri) najraje zahaja v kino in katere žanre filmov ima rad.

Dan je tudi seznam filmov, ki jih v našem kinematografu smemo predvajati. Za vsak film je znano njegovo trajanje (v minutah), ocena priljubljenosti (ki vpliva na to, kako verjetno je, da ga bodo ljudje prišli gledat) in to, katerim žanrom pripada. Glede tega, kolikokrat (in kdaj) smemo predvajati posamezni film, ni posebnih omejitev — lahko ga predvajamo enkrat, večkrat, nobenkrat, lahko tudi večkrat v istem dnevu ipd.

Tvoja naloga je sestaviti celoletni spored predstav za ta kinematograf. Pri tem lahko uporabljaš le filme z danega seznama. Za vsako predstavo moraš navesti številko filma ter dan in uro začetka predstave. Ker ima kino eno samo dvorano, se predstave med seboj ne smejo prekrivati. Poleg tega tudi ne sme nobena predstava segati v naslednje leto (npr. če bi začeli nek film, ki traja več kot eno uro, predvajati na 366. dan ob enajstih zvečer).

Ocenjevanje pri tej nalogi poteka takole. Če tvoja oddana datoteka ne ustreza pravilom glede formata ali pa se v njej predstave prekrivajo ali segajo v naslednje leto, se šteje ta datoteka za neveljavno in ne dobi nič točk. Drugače pa bomo na tvojem celoletnem sporedu simulirali obnašanje gledalcev; za vsako predstavo se vsak gledalec z neko verjetnostjo odloči, ali bo šel kupit karto ali ne. Verjetnost nakupa je odvisna med drugim od ocene filma, od tega, ali pripada žanru, ki ga gledalec rad gleda, in od tega, ali gledalcu ustreza ura, ob kateri se film predvaja. (Podrobnosti o ocenjevanju so opisane spodaj.) Za oceno tvojega sporeda se vzame povprečno število prodanih kart v treh ponovitvah simulacije. (Pri tem si organizatorji pridržujemo pravico, da kasneje, če si bodo tekmovalci po rezultatih zelo blizu, izvedemo še dodatne simulacije, da bi tako dobili zanesljivejšo oceno posameznega razporeda.)

Simuliranje obnašanja gledalcev

Postopek simulacije, ki ga bomo uporabili za ocenjevanje oddanih sporedov, je naslednji:

Pregleduj predstave v sporedu po naraščajočem dnevu in uri začetka.
Pri vsaki predstavi izvedi naslednje:
- Ponovi za vsakega gledalca:
  - Naj bo P verjetnost, da bi šel ta gledalec kupit vstopnico za to predstavo.
  - Z verjetnostjo P se odločimo, da bo šel res kupit vstopnico zanjo; z verjetnostjo 1 – P pa, da je ne bo šel.
- Če smo se za nakup vstopnice odločili pri več kot s gledalcih (pri čemer je s število sedežev v kino dvorani), obdržimo izmed njih naključno množico s gledalcev (pri čemer imajo vsi enake možnosti, da bodo izbrani).
- Izbrani gledalci zdaj kupijo vstopnice za to predstavo.
Izpiši skupno število prodanih vstopnic.

Ker postopek uporablja psevdonaključna števila, ga bomo pognali večkrat in za oceno vzeli povprečno število prodanih vstopnic.

Verjetnost, da gre nek gledalec kupit vstopnico za neko predstavo, izračunamo takole:

P = P_čas · P_žanri · P_prej · P_že · P_ocena

Pri tem so posamezni členi določeni takole:

P_čas je odvisna od časa predstave. Za vsakega gledalca vemo, ob katerem času v dnevu je najraje v kinu. Pogledamo razdaljo med tem časom in časom, v katerem poteka predstava. Na primer, če je nekdo v kinu najrajši ob 02:00, neka predstava pa poteka od 23:00 do 00:45, je razdalja v tem primeru 75 minut (od 00:45 do 02:00). Za nekoga, ki je v kinu najrajši ob 22:30, pa bi bila razdalja v tem primeru le 30 minut (od 22:30 do 23:00). Za nekoga, ki je v kinu najrajši ob npr. 23:15, bi bila razdalja v tem primeru 0, saj predstava pokriva tudi njegov najljubši čas. Če zdaj tako opisano razdaljo (v minutah) označimo z r, bomo vzeli
P_čas = 1 / (1 + exp(0,05 · (r – 90))). To na primer pomeni, da pri r = 90 minutah verjetnost P_čas pade na 50%; pri 120 minutah že na samo 18%; pri 180 minutah pa že na samo 1%.
P_žanri je odvisna od tega, koliko izmed tistih žanrov, ki jim pripada film, je takih, da jih opazovani gledalec rad gleda. Če ni nobenega takega žanra, vzamemo P_žanri = 0,1; če je tak žanr eden, vzamemo P_žanri = 0,9; če pa sta taka žanra dva ali več, vzamemo P_žanri = 1.
P_prej je odvisna od tega, koliko časa je minilo, odkar si je ta gledalec nazadnje ogledal kakšno predstavo v našem kinu. Če se naša predstava začne na dan d₁, on pa si je nazadnje pred tem ogledal neko predstavo, ki se je začela na dan d₂, naj bo r = d₁ – d₂. Potem vzamemo P_prej = 1 – 0,8^r. To na primer pomeni, da po sedmih dneh verjetnost P_prej naraste na 79%, po štirinajstih dneh pa že na 96%. (Za gledalca, ki ni bil še nikoli v kinu, je P_prej = 1.)
P_že je odvisna od tega, kolikokrat je ta gledalec doslej že videl ta film. Če ga ni videl še nikoli, vzamemo P_že = 1. Če pa ga je videl že k-krat (za nek k > 0), vzamemo P_že = 0,1 · 0,5^k – 1.
P_ocena je odvisna od ocene filma. Če je ta ocena r, vzamemo P_ocena = g(r) / g(9), pri čemer je g(r) definirana takole:

r 1 2 3 4 5 7 8 9
g(r) 50 100 160 170 190 210 300 350
Med temi vrednostmi je g linearna funkcija. Pri r < 1 vzamemo g(r) = g(1), pri r > 9 pa g(r) = g(9).

(Vrednosti v gornji tabeli smo dobili na podlagi povprečnega izkupička od prodaje vstopnic, ki ga za nekatere filme navajajo na IMDB.)

Ocenjevalni program

Lahko si preneseš izvorno kodo programa, s katerim bomo izvajali simulacije in ocenjevali prejete rešitve: Rtk08Kino.cpp. (Če ga hočeš prevesti, boš potreboval še izvorno kodo postopka SFMT za generiranje psevdonaključnih števil.)

Prevedena različica ocenjevalnega programa (za Windows): 32-bitna, 64-bitna.

(Opomba: program, ki ga bomo uporabljali za ocenjevanje na našem strežniku, uporablja drugačno seme za generiranje psevdonaključnih števil kot ta tu zgoraj.)

Oblika vhodne datoteke

V prvi vrstici vhodne datoteke je niz z imenom naloge (Kino), v drugi pa številka testnega primera, na katerega se nanaša ta vhodna datoteka. V tretji vrstici je število filmov, f. To je celo število, večje ali enako 1 in manjše ali enako 22000.

Sledijo podatki o vsakem izmed f filmov. Vsak film je opisan v več vrsticah. Prva izmed teh vrstic vsebuje zaporedno številko filma (filmi so po vrsti oštevilčeni z 0, 1, … f – 1). Druga vrstica vsebuje IMDBjevo oznako filma (oblike tt + 7 števk; do IMDBjeve strani tistega filma lahko potem pridemo z URLjem oblike http://www.imdb.com/title/tt#######/). Tretja vrstica vsebuje naslov filma (tudi pobran z IMDBja). Četrta vrstica vsebuje trajanje filma v minutah; to je celo število, večje ali enako 1 in manjše od 10000. Peta vrstica vsebuje oceno (rating) filma (to je realno število, večje ali enako 0 in manjše ali enako 10). Šesta vrstica vsebuje število žanrov, ki jim ta film pripada (recimo g; to je celo število, večje ali enako 1). Sledijo podatki o vseh g žanrih, ki jim ta film pripada, in sicer sta za vsak žanr dve vrstici: prva od njiju vsebuje številko žanra (to je eno od celih števil 0, 1, …, 26), druga pa ime žanra. (Lahko si preneseš tudi spisek vseh žanrov.)

Nato sledi vrstica, ki vsebuje dve celi števili, n in s, ločeni s presledkom. Pri tem je n število vseh prebivalcev našega kraja pri tem testnem primeru (večje ali enako 1 in manjše ali enako 20000), s pa število sedežev v kino dvorani (večje ali enako 1 in manjše ali enako 500).

Sledijo podatki o vseh n prebivalcih. Za vsakega je več vrstic. Prva vrstica vsebuje čas, ob katerem je ta oseba najrajši v kinu (to je niz oblike hh:mm). Druga vrstica vsebuje število žanrov, ki jih ta oseba rada gleda (recimo g; to je celo število, večje ali enako 1). Sledi še seznam teh g žanrov, in sicer so predstavljeni enako kot pri filmih: za vsak žanr sta dve vrstici, v prvi je številka žanra, v drugi pa njegovo ime.

Opomba: IMDBjeve oznake filmov, naslovi filmov in imena žanrov so v vhodni datoteki podani le zato, da se človek lažje znajde po njej. Za potrebe sestavljanja sporeda filmov pa ti podatki niso pomembni in jih lahko vaš program tudi preskoči.

Primer: tu je primer vhodne datoteke s samo štirimi filmi, desetimi gledalci in dvorano, v kateri je prostora za pet ljudi.

Kino
0
4
0
tt0442933
Beowulf (2007)
113
6.9
4
0
Action
2
Adventure
8
Drama
10
Fantasy
1
tt0346491
Alexander (2004)
175
5.4
5
0
Action
2
Adventure
4
Biography
8
Drama
25
War
2
tt0332452
Troy (2004)
163
6.9
4
0
Action
8
Drama
12
History
19
Romance
3
tt0417148
Snakes on a Plane (2006)
105
6.5
2
0
Action
24
Thriller
10 5
23:26
3
3
Animation
4
Biography
6
Crime
11:21
2
9
Family
4
Biography
01:21
1
9
Family
00:32
1
14
Music
16:59
2
9
Family
15
Musical
14:20
2
25
War
26
Western
17:43
3
9
Family
4
Biography
7
Documentary
22:03
2
4
Biography
12
History
20:54
3
9
Family
26
Western
4
Biography
18:37
3
9
Family
4
Biography
12
History

Oblika izhodne datoteke

V prvi vrstici naj bo koda, ki si jo dobil(a) ob registraciji in iz katere je razvidno, da si rešitev res poslal(a) ti, ne pa kdo drug. V drugi vrstici naj bo ime naloge (Kino). V tretji vrstici naj bo številka testnega primera, na katerega se ta izhodna datoteka nanaša. V četrti vrstici naj bo število predstav v tvojem sporedu (recimo m; to naj bo celo število, večje ali enako 0). Sledi naj m vrstic, za vsako predstavo po ena. Vsaka od teh vrstic naj vsebuje tri cela števila, ločena s presledkom; prvo od teh števil je zaporedna številka filma (0, 1, …, f – 1), drugo je dan v letu, ko se predstava začne (0, 1, …, 365), tretje pa je čas začetka te predstave (v minutah po polnoči; to je torej eno od števil 0, 1, …, 1439).

Primer: če bi bila naša uporabniška koda enaka 123456 in bi obstajal ničti testni primer, kakršen je prikazan zgoraj, bi lahko pri njem oddali spodnjo izhodno datoteko.

Vhodni podatki

Vse vhodne datoteke skupaj: kino-inputs.zip.

kino00.in (4 filmi, 10 prebivalcev, 5 sedežev)
(to je primer, ki je prikazan zgoraj)
kino01.in (100 filmov, 10 prebivalcev, 5 sedežev)
kino02.in (1000 filmov, 100 prebivalcev, 20 sedežev)
kino03.in (1000 filmov, 1000 prebivalcev, 100 sedežev)
kino04.in (1000 filmov, 5000 prebivalcev, 200 sedežev)
kino05.in (1000 filmov, 10000 prebivalcev, 300 sedežev)
kino06.in (21822 filmov, 10000 prebivalcev, 300 sedežev)
kino07.in (5000 filmov, 15000 prebivalcev, 400 sedežev)
kino08.in (21822 filmov, 15000 prebivalcev, 400 sedežev)
kino09.in (10000 filmov, 20000 prebivalcev, 500 sedežev)
kino10.in (21822 filmov, 20000 prebivalcev, 500 sedežev)

Za ocenjevanje štejejo rezultati pri primerih od kino01.in do kino10.in.

Registracija

Preden lahko oddajaš svoje rešitve, se prijavi prek spodnjega obrazca. Dodelili ti bomo enolično uporabniško kodo, ki jo boš potreboval(a) za pripravo svojih izhodnih datotek.

Opomba: pri tej nalogi lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh tekmovalcev, za morebitne praktične nagrade pa pridejo v poštev le tisti tekmovalci oz. tekmovalke, ki v letu 2007/08 obiskujejo kakšno srednjo šolo.

r	1	2	3	4	5	7	8	9
g(r)	50	100	160	170	190	210	300	350