{"id":"informatyka-2015-maj-matura-rozszerzona/zad/1","paper_id":"informatyka-2015-maj-matura-rozszerzona","number":"1","points":null,"ptype":"closed","subject":"informatyka","category":"matura","year":2015,"month":"maj","level":"rozszerzona","text":"Zadanie 1. Problem telewidza\nW Problemie telewidza mamy program telewizyjny, zawierający listę filmów emitowanych\nw różnych stacjach telewizyjnych jednego dnia. Telewidz zamierza obejrzeć jak najwięcej\nfilmów w całości. Jedyne ograniczenie jest takie, że telewidz może oglądać co najwyżej jeden\nfilm (stację telewizyjną) jednocześnie. Zakładamy, że jednego dnia wszystkie filmy są różne.\nProgram telewizyjny emisji filmów w 4 stacjach telewizyjnych:\nTelewizja / stacja\nFilm i godziny jego emisji\nCzas trwania emisji filmu\nTV1\nfilm 1: od 9:00 do 12:00\nfilm 2: od 15:00 do 17:00\n3 godziny\n2 godziny\nTV2\nfilm 3: od 11:00 do 16:00\n5 godzin\nTV3\nfilm 4: od 12:00 do 14:00\n2 godziny\nTV4\nfilm 5: od 11:30 do 12:30\n1 godzina\nDla programu podanego powyżej telewidz jest w stanie obejrzeć aż trzy filmy, np.: film 1,\nfilm 4, film 2. Przyjmujemy, że telewidz nie traci w ogóle czasu na przełączanie\npomiędzy stacjami (np. o godz. 12:00 z TV1 na TV3). Innymi słowy, czasy emisji filmów 1\ni 4 nie kolidują ze sobą.\nRozważ następujący algorytm wyboru filmów do obejrzenia przez telewidza, w którym\nw kroku 2. stosuje się jedną z czterech strategii opisanych w tabeli 1.\nSpecyfikacja:\nDane:\nT - zbiór filmów z programu telewizyjnego z godzinami emisji i czasami ich\ntrwania,\nS - strategia z tabeli 1.\nWynik:\nP - zbiór filmów, które obejrzy telewidz.\nAlgorytm:\nKrok 1.\nZainicjuj P jako zbiór pusty.\nKrok 2.\nDopóki T zawiera jakieś filmy, wykonuj:\nstosując strategię S, wybierz ze zbioru T film x i usuń go z T\ndodaj film x do zbioru P\nusuń ze zbioru T wszystkie filmy, których czasy emisji kolidują z czasem\nemisji filmu x.\nKrok 3.\nZakończ wykonywanie algorytmu i wypisz wszystkie filmy ze zbioru P.\nMIN_1R\nTabela 1. Cztery strategie (S) w Problemie telewidza:\nStrategia A\nWybierz film, który trwa najdłużej, a jeśli jest takich więcej, to wybierz\nz nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów,\nwybierz dowolny z nich.\nStrategia B\nWybierz film, który trwa najkrócej, a jeśli jest takich więcej, to wybierz\nz nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów,\nwybierz dowolny z nich.\nStrategia C\nWybierz film, który się najwcześniej zaczyna, a jeśli jest takich więcej,\nto wybierz z nich ten, który się najwcześniej kończy. Jeśli jest więcej\ntakich filmów, wybierz dowolny z nich.\nStrategia D\nWybierz film, który się najwcześniej kończy, a jeśli jest takich więcej,\nto wybierz z nich ten, który się najpóźniej zaczyna. Jeśli jest więcej\ntakich filmów, wybierz dowolny z nich.\nPrzykład:\nDla podanego programu telewizyjnego zastosowanie w kroku 2. strategii A daje wynik\nP = {film 3}, czyli telewidz obejrzy tylko jeden film.","answer":null,"answer_text":"188\n12\n-1\n16","solution":null,"image":"img/informatyka-2015-maj-matura-rozszerzona/zad-1.webp","solution_image":null,"topics":null,"page_from":2,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":null,"text_source":"ocr","source_label":"Informatyka · Matura · maj 2015 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1. Problem telewidza
W Problemie telewidza mamy program telewizyjny, zawierający listę filmów emitowanych
w różnych stacjach telewizyjnych jednego dnia. Telewidz zamierza obejrzeć jak najwięcej
filmów w całości. Jedyne ograniczenie jest takie, że telewidz może oglądać co najwyżej jeden
film (stację telewizyjną) jednocześnie. Zakładamy, że jednego dnia wszystkie filmy są różne.
Program telewizyjny emisji filmów w 4 stacjach telewizyjnych:
Telewizja / stacja
Film i godziny jego emisji
Czas trwania emisji filmu
TV1
film 1: od 9:00 do 12:00
film 2: od 15:00 do 17:00
3 godziny
2 godziny
TV2
film 3: od 11:00 do 16:00
5 godzin
TV3
film 4: od 12:00 do 14:00
2 godziny
TV4
film 5: od 11:30 do 12:30
1 godzina
Dla programu podanego powyżej telewidz jest w stanie obejrzeć aż trzy filmy, np.: film 1,
film 4, film 2. Przyjmujemy, że telewidz nie traci w ogóle czasu na przełączanie
pomiędzy stacjami (np. o godz. 12:00 z TV1 na TV3). Innymi słowy, czasy emisji filmów 1
i 4 nie kolidują ze sobą.
Rozważ następujący algorytm wyboru filmów do obejrzenia przez telewidza, w którym
w kroku 2. stosuje się jedną z czterech strategii opisanych w tabeli 1.
Specyfikacja:
Dane:
T - zbiór filmów z programu telewizyjnego z godzinami emisji i czasami ich
trwania,
S - strategia z tabeli 1.
Wynik:
P - zbiór filmów, które obejrzy telewidz.
Algorytm:
Krok 1.
Zainicjuj P jako zbiór pusty.
Krok 2.
Dopóki T zawiera jakieś filmy, wykonuj:
stosując strategię S, wybierz ze zbioru T film x i usuń go z T
dodaj film x do zbioru P
usuń ze zbioru T wszystkie filmy, których czasy emisji kolidują z czasem
emisji filmu x.
Krok 3.
Zakończ wykonywanie algorytmu i wypisz wszystkie filmy ze zbioru P.
MIN_1R
Tabela 1. Cztery strategie (S) w Problemie telewidza:
Strategia A
Wybierz film, który trwa najdłużej, a jeśli jest takich więcej, to wybierz
z nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów,
wybierz dowolny z nich.
Strategia B
Wybierz film, który trwa najkrócej, a jeśli jest takich więcej, to wybierz
z nich ten, który się najwcześniej kończy. Jeśli jest więcej takich filmów,
wybierz dowolny z nich.
Strategia C
Wybierz film, który się najwcześniej zaczyna, a jeśli jest takich więcej,
to wybierz z nich ten, który się najwcześniej kończy. Jeśli jest więcej
takich filmów, wybierz dowolny z nich.
Strategia D
Wybierz film, który się najwcześniej kończy, a jeśli jest takich więcej,
to wybierz z nich ten, który się najpóźniej zaczyna. Jeśli jest więcej
takich filmów, wybierz dowolny z nich.
Przykład:
Dla podanego programu telewizyjnego zastosowanie w kroku 2. strategii A daje wynik
P = {film 3}, czyli telewidz obejrzy tylko jeden film.

","answer_text_html":"

188
12
-1
16

","solutions":[]}