Problem A - Bankowość
Problem B - Wiadomości sieciowe
Problem C - Łamanie szyfru
Problem D - Dekarze
Problem E - Części wspólne figur
Problem F - Szewc Olo
Problem G - Mikrokomputerowy sterownik wyłączników

 

 

 

1982

Problem F - Szewc Olo


Opis

Olo, zwariowany szewc, pracuje zgodnie z następującym rozkładem. Zawsze gdy pojawia się w jego sklepie klient, określa on czas wykonania zlecenia. Nigdy się przy tym nie myli. Jeśli zlecenie zajmie ponad pięć minut, wstawia je na koniec swojej kolejki prac. Jeśli zajmie pięć lub mniej minut, to umieszcza je na początku tej kolejki (nawet jeśli na początku już znajduje się jakieś krótkie zlecenie). Oczywiście zawsze kończy aktualną pracę, zanim podejmie się nowej.

Wpływ zleceń do zakładu Ola w ciągu tygodnia jest opisany ciągiem wierszy z danymi. Dane te zostały zebrane w ciągu typowego, 5-cio dniowego tygodnia roboczego, od poniedziałku do piątku. Wiersze danych pojawiają się w kolejności napływania zleceń do zakładu. Jeden wiersz opisuje jedno zlecenie. Pierwszą wartością w wierszu jest czas liczony minutami od momentu otwarcia zakładu, a druga wartość określa czas potrzebny na wykonanie tego zlecenia. (Ponieważ Olo nigdy nie otwiera zakładu przed godziną ósmą rano, na minuty wystarczy liczba trzycyfrowa.) Zamówienia dla każdego dnia kończone są pustym wierszem, który nie zawiera żadnych danych. Na jeden dzień Olo nigdy nie dostaje więcej niż 50 zleceń, ani mniej niż jedno. Zanim wychodzi do domu na kolację, zostaje w swoim zakładzie aż do skończenia pracy nad zleceniami z danego dnia. Wszystkie zlecenia pozostawione przy wejściu do jego zakładu są kodowane jako przybyłe w minucie zero, czyli w czasie, gdy jego zakład rozpoczyna pracę, a w danej minucie może pojawić się więcej niż jedno zlecenie.

Olo jest uważany za zwariowanego ponieważ w szczególny sposób zajmuje się prowadzeniem swojego zakładu. Posiada w nim duży zegar ze wskazówką sekundową, który używa do ścisłego przestrzegania porządku swoich prac. Jeśli zlecenie pojawia się w czasie, gdy jest zajęty, umieszcza je w kolejce i wraca do pracy. Jeśli zlecenie pojawia się, gdy nie ma nic do roboty, czeka aż do początku następnej minuty z rozpoczęciem pracy, zatem wszystkie zlecenia pojawiające się w tej minucie zostaną umieszczone w kolejce, zanim wybierze jedno z nich do realizacji.  (Zlecenia nie czekają aż do końca minuty ich pojawienia się.) Gdy dane zlecenie jest kończone, Olo pracuje nad nim aż do końca jego ostatniej minuty, umieszczając w kolejce zlecenia, które się pojawią w tej minucie. Innymi słowy, jego niezmienny porządek pracy w każdej minucie jest następujący:

  1. Jeśli nic nie robi, rozpoczyna pracę nad kolejnym zleceniem z kolejki.
  2. Wpisuje do kolejki wszystkie napływające zlecenia.
  3. Kończy rozpoczętą pracę, jeśli jest to jej ostatnia minuta.

Twoim zadaniem jest napisanie programu, który obliczy średni czas opóźnienia dla zleceń przyjętych w zakładzie każdego dnia. Średni czas opóźnienia w minutach jest średnim czasem, w którym zlecenie jest przetrzymywane w zakładzie, zanim Olo rozpocznie jego realizację. Masz wypisać tablicę w następującym formacie:

 

DAY        AVERAGE DELAY
MONDAY        XXX.X
TUESDAY       XXX.X
WEDNESDAY     XXX.X
THURSDAY      XXX.X
FRIDAY        XXX.X

 

Na przykład, jeśli 4-minutowe i 6-minutowe zlecenia pojawią się o godzinie 8:05, a 5-minutowe zlecenie pojawi się o 8:12, to rozkład zdarzeń jest następujący:

 

8:06  Początek pracy nad zleceniem 4-minutowym (czas oczekiwania zlecenia równy 0 minut)
8:09  Koniec pracy nad zleceniem 4-minutowym
8:10  Początek pracy nad zleceniem 6-minutowym (czas oczekiwania zlecenia równy 4 minuty)
8:12  Wprowadzenie do kolejki zlecenia 5-minutowego
8:15  Koniec pracy nad zleceniem 6-minutowym
8:16  Początek pracy nad zleceniem 5-minutowym (czas oczekiwania zlecenia równy 3 minuty)

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.