Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Tłumaczył: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

1982

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Bankowość

Opis

Twój program ma za zadanie wypisać szczegółowy dziennik transakcji dokonywanych za pomocą książeczki czekowej.

Specyfikacja wejścia

Na wejściu program oczyma ciąg danych, który będzie zawierał pewną sumę, kod transakcji oraz datę. Dane będą w kolejności chronologicznej ze względu na datę. Wiersze wejściowe po pierwszym wierszu będą przedstawiały wypisane czeki oraz dokonane wpłaty. Każdy czek będzie reprezentowany przez jeden wiersz wejściowy o następującej postaci:

xxxxx.xxDBmmddyy

gdzie x oznacza cyfry sumy, DB jest kodem transakcji dla czeku, a mmddyy oznacza kolejno numer dnia, numer miesiąca oraz numer roku akceptacji czeku.

Każda wpłata będzie przedstawiana za pomocą wiersza o postaci:

xxxxx.xxCRmmddyy

Znaczenie jest oczywiste w kontekście poprzedniego.

Pierwszy wiersz wejścia będzie zawierał początkowy bilans konta (znak oznaczany za pomocą DB lub CR) oraz datę, od której rozpoczyna się naliczanie odsetek. Ten pierwszy wiersz nie powinien być traktowany jako transakcja.

Specyfikacja wyjścia

Twój program ma wypisać raport ukazujący wszystkie transakcje oraz opłaty za usługi (wyjaśnione poniżej). Dla każdego wiersza wejściowego należy wyświetlić wiersz o następującej postaci:

PREVIOUS BALANCE xxxxxx.xx
CR
DB
    xxxxx.xx
CR
DB
SC
     NEW BALANCE  xxxxxx.xx
CR
DB
PREVIOUS BALANCE = poprzedni bilans
NEW BALANCE = nowy bilans

W drukowanych liczbach nie są używane znaki + lub -. Bilanse mniejsze od zera mają na końcu symbol DB, a większe lub równe zero CR. Wszystkie wartości mają być drukowane z przynajmniej jedną cyfrą na lewo od kropki dziesiętnej, zatem 3 centy powinno się pojawić jako 0.03DB. Jeśli bilans rachunku spadnie kiedykolwiek w miesiącu poniżej 500.00 dolarów, to za realizację każdego czeku jest w tym miesiącu pobierana z rachunku opłata 12 centów. Opłata za usługi (SC - service charge) ma być wydrukowana przed drukowaniem transakcji dla kolejnego miesiąca. Wiersz SC nie powinien się pojawiać, jeśli nie zrealizowano żadnych czeków lub jeśli stan konta pozostaje wysoki. Na końcu danych należy wypisać opłatę za usługi dla końcowego miesiąca. Uwaga, jeśli na końcu miesiąca bilans jest poniżej minimum, to implikuje to bilans poniżej minimum na początku następnego miesiąca.

Na początek:  podrozdziału   strony 

Problem B - Wiadomości sieciowe

Opis

Zbudowano pewną sieć komputerową, która łączy duże komputery w różych miastach. Nie wszystkie komputery są ze sobą połączone bezpośrednio, lecz każdy z nich może wysyłać wiadomość do każdego innego, przesyłając ją przez kilka komputerów pośrednich. Sieć jest trzewem, co oznacza, że istnieje dokładnie jedna ścieżka pomiędzy dwoma dowolnymi komputerami. Przykład takiej sieci jest pokazany poniżej:

obrazek

Pożądane jest określenie sposobu przesyłu wiadomości od określonego komputera do wszystkich pozostałych w najmniejszym czasie. Przesłanie wiadomości z jednego komputera do drugiego zajmuje jedną jednostkę czasu, a danym czasie komputer może przesyłać wiadomość tylko do jednego z pozostałych. Podczas pierwszej jednostki czasu komputer źródłowy wiadomości może przesłać ją do jednego z sąsiednich komputerów. Podczas drugiej jednostki czasu zarówno nadawca wiadomości jak i ten sąsiad mogą przesłać tą wiadomość do kolejnych sąsiadów. W tym punkcie wiadomość została przeglądnięta przez przez co najwyżej cztery komputery. Podczas trzeciej jednostki czasu, każdy z nich może przesłać wiadomość do kolejnych sąsiadów, itd.

Ponieważ każdy komputer może posiadać kilku sąsiadów, wybór jednego z nich na odbiorcę wiadomości potrafi znacząco wpłynąć na całkowity czas przesłania wiadomości. Na przykład, na poniższych rysunkach numery na krawędziach oznaczają jednostkę czasu, w której ta gałąź przenosi wiadomość. Nadawcą wiadomości jest w każdym przypadku węzeł C, lecz na lewym rysunku wymagane jest 6 jednostek czasu, natomiast na prawym rysunku potrzebne są jedynie trzy jednostki.

obrazek

Twój program powinien wykonać następujące operacje:

  1. Wczytać opis sieci wg reguł podanych poniżej.
  2. Wczytać węzeł wysyłający wiadomość.
  3. Określić optymalną kolejność wysyłania tej wiadomości. Wypisać tę kolejność, pokazując nadawcę i odbiorcę każdej transmisji w obrębie każdej jednostki czasu.

Specyfikacja wejścia

Sieć będzie reprezentowana przez następującą strukturę danych wejściowych:

W pierwszym wierszu będzie podana liczba n  określająca ilość węzłów w sieci, 2 ≤ n  ≤ 9.

W każdym z n  kolejnych wierszy będą podane następujące elementy rozdzielone spacjami:

Specyfikacja wyjścia

Dla każdej jednostki czasu należy wypisać słowo TIME, numer jednostki oraz pod spodem nazwy miast skojarzonych z węzłami wysyłającymi i odbierającymi wiadomość. Miasto wysyłające powinno być umieszczone najpierw, następnie słowo TO (ang. do) i miasto odbierające wiadomość:

Przykładowe dane wejściowe

7
1 A 3 0
2 B 3 0
3 C 1 2 4 0
4 D 3 5 6 0
5 E 4 0
6 F 4 7 0
7 G 6 0
3

Przykładowe dane wyjściowe

TIME 1
C             TO D

TIME 2
C             TO B
D             TO F

TIME 3
C             TO A
D             TO E
F             TO G
Na początek:  podrozdziału   strony 

Problem C - Łamanie szyfru

Opis

Pewna wiadomość została zaszyfrowana przy pomocy prostego szyfru podstawieniowego. Oznacza to, że wybrano pewną permutację alfabetu i każda z liter oryginalnej wiadomości została zastąpiona przez odpowiadającą jej literę w alfabecie spermutowanym. Na przykład, wykorzystując permutację:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
J X R I D Z T A Q K E B H P W C O L F S V M G Y U N

wiadomość THE CAT IS OUT OF THE BAG (kot uciekł z worka) staje się wiadomością SAD RFS QF WVS WZ SAD XJT.

Częstotliwości występowania liter w angielskim tekście nie są jednorodne; najczęściej pojawia się litera E, następnie T, itd. Mając do dyspozycji wystarczająco dużą zaszyfrowaną wiadomość, częstotliwości pojawiania się w niej liter powinny wskazać, które z liter alfabetu oryginalnego są przez nie reprezentowane. Na przykład, jeśli litera D pojawiała by się najczęściej w zaszyfrowanej wiadomości, to podejrzewalibyśmy, że reprezentuje ona literę E, jak w powyższym przykładzie.

Opierając się na tym pomyśle, twój program musi rozszyfrować wiadomość. Dane składają się z dwóch wiadomości. Pierwsza wiadomość będzie normalnym teksten angielskim (niezaszyfrowanym). Twój program powinien wykorzystać ten tekst do określenia względnej częstotliwości liter w normalnym angielskim. Druga wiadomość będzie zaszyfrowaną wiadomością. Twój program powinien określić względne częstotliwości występowania liter w tej wiadomości, a następnie rozszyfrować wiadomość zastępując każdą k-tą najczęstszą literę przez k-tą najczęstszą literę w tekście angielskim. Odszyfrowaną wiadomość należy wyświetlić.

Specyfikacja wejścia

Dane wejściowe składają się z co najwyżej 20 wierszy tekstu angielskiego, zakończonego wierszem z pojedynczym znakiem *, następnie z co najwyżej 20 wierszy tekstu zaszyfrowanego, zakończonych wierszem z pojedynczym znakiem *. Każdy wiersz zawiera do 80 znaków, niektóre z nich mogą być spacjami.

Specyfikacja wyjścia

Na wyjściu należy wyświetlić odczytane wiersze drugiej wiadomości, w których znaki zostały zastąpione zgodnie z podaną regułą częstości występowania.

Na początek:  podrozdziału   strony 

Problem D - Dekarze

Opis

Firma Budgets Roofers, Inc. sprzedaje swoje usługi poprzez domokrążców, którzy potrafią wymierzyć dach wystarczająco dokładnie, jednakże zupełnie nie radzą sobie przy określaniu potrzeb materiałowych. Firma potrzebuje programu, który określi minimalną liczbę wiązek gontów, które są potrzebne dla każdej z prac. Niestety, dane są zapisywane w dziwny sposób, którego kierownictwo nie chce jednakże zmieniać, ponieważ opanowanie go zajęło sprzedawcom tak dużo czasu.

Specyfikacja wejścia

Każdy dach jest opisany jednym wierszem wejściowym. Wiersz ten zawiera następujące dane, rozdzielone pojedynczą spacją:

jn  - numer zlecenia (ang. job number), liczba całkowita < 10000, różna od zera;
rt  - typ dachu (ang. roof type), cyfra 1, 2 lub 3;
rs - nachylenie dachu (ang. roof slope), w procentach, liczba zmiennoprzecinkowa
A - wymiar A, liczba zmiennoprzecinkowa
B - wymiar B, liczba zmiennoprzecinkowa
C - wymiar C (tylko dla dachów typu 3, w pozostałych typach nie występuje), liczba zmiennoprzecinkowa
D - wymiar D (tylko dla dachów typu 3, w pozostałych typach nie występuje), liczba zmiennoprzecinkowa

Wiersze wejściowe nie są sortowane, jednakże dla prac dotyczących budynków z kilkoma dachami kolejne wiersze będą zawierały ten sam numer zlecenia. Wiersz z numerem zlecenia równym 0 kończy dane wejściowe. Poniżej przedstawione są typy dachów. Wszystkie wymiary są mierzone poziomo i zapisywane przy użyciu konwencji:

ff.iie

gdzie ff oznacza liczbę stóp, ii oznacza liczbę cali (i jest mniejsze od 12), a e (w zakresie od 0 do 7) oznacza ósme części cala.

Nachylenie dachu jest takie samo na wszystkich częściach dachu. Nie posiada wymiaru i jest równe 100 razy wysokość podniesienia dachu przez jego długość poziomą:

obrazek

 

obrazek
 Dach typu 1
obrazek
Dach typu 2
obrazek
Dach typu 3

Dla wszystkich dachów obowiązuje ograniczenie: B ≥ A ≥ C.

Specyfikacja wyjścia

Na pokrycie 100 stóp2 dachu zużywane jest 3 wiązki gontów. Wymagany program ma wypisać dwukolumnowy raport, w którym ma się znaleźć numer zlecenia oraz całkowita liczba wiązek gontów potrzebna do jego realizacji. Jeśli jedno zlecenie obejmuje kilka dachów, to wszystkie gonty dla tego zlecenia będą tej samej wielkości i koloru, zatem część gontów pozostała po jednym dachu może zostać wykorzystana w innym w ramach tego samego zlecenia.

Na początek:  podrozdziału   strony 

Problem E - Części wspólne figur

Opis

Masz napisać program, który określi wszystkie punkty o całkowitych współrzędnych x i y wewnątrz części wspólnej obszarów ograniczonych przez dwuwymiarowe figury geometryczne. Dla przypadku pokazanego poniżej:

obrazek

punkty (0,1) (0,2) i (-1,1) leżą dokładnie wewnątrz obszaru wspólnego wnętrz koła, trójkąta i prostokąta. (Punkty leżące na brzegach nie mają być wliczane.) Twój program przetwarzający ten układ figur powinien wypisać podaną wyżej listę, stosując jakiś rozsądny format. Kolejność punktów nie ma znaczenia. Uwaga, lista może być pusta.

Figury, które mogą się pojawić, to prostokąty, trójkąty i koła. Żadna z tych figur nie będzie zdegenerowana i wszystkie zostaną określone poprawnie. Wnętrza co najwyżej trzech kształtów mogą posiadać część wspólną.  Twój program powinien przetwarzać dowolną liczbę zbiorów figur. Wszystkie figury leżą wewnątrz kwadratu ograniczonego przez punkty (-10,10), (10,10), (10,-10), (-10,-10).

Specyfikacja wejścia

Dane wejściowe są zorganizowane następująco:

powtarzane,
n  = 0
obrazek     n  - liczba figur, 1 < n ≤ 3. Wartość 0 kończy dane wejściowe.
powtarzane
n  razy
obrazek s  - jednoliterowy kod figury, C - koło, T - trójkąt, R - prostokąt
ciąg liczb zależny od rodzaju figury, zdefiniowany poniżej
  1. s="R" oznacza prostokąt (ang. rectangle). Wystąpią cztery pary współrzędnych x i y, które będą określały narożniki prostokąta, podane w kolejności zgodnej lub przeciwnej do ruchu wskazówek zegara.
  2. s='T' oznacza trójkąt (ang. triangle). Wystąpią trzy pary współrzędnych x i y, które będą określały wierzchołki trójkąta.
  3. s='C' oznacza koło (ang. circle). Pierwsza para współrzędnych x i y określa środek koła, a następna liczba r określa jego promień.

Specyfikacja wyjścia

Dla każdego zestawu figur program powinien powtórzyć ich definicję, którą odczytał na wejściu, w celu identyfikacji figur. Następnie program powinien wypisać ciąg współrzędnych punktów leżących wewnątrz części wspólnej podanych figur i posiadających całkowite wartości x i y.

Na początek:  podrozdziału   strony 

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)
Na początek:  podrozdziału   strony 

Problem G - Mikrokomputerowy sterownik wyłączników

Opis

Twoim zadaniem jest napisanie programu, który hipotetycznie mógłby pracować na komputerze sterującym 16 wyłącznikami w całym domu. Twój program może wykonywać następujące funkcje związane z wyłącznikami:

  1. Włączenie jednego lub wszystkich.
  2. Wyłączenie jednego lub wszystkich.
  3. Wykrycie stanu wyłącznika.

Właściciel domu ma posiadać następujące możliwości w tym programie:

  1. Polecić włączenie dowolnego wyłącznika lub wszystkich.
  2. Polecić wyłączenie dowolnego wyłącznika lub wszystkich.
  3. Sprawdzić stan dowolnego wyłącznika lub wszystkich.
  4. Określić porę wykonania rozkazów (1) lub (2) w każdym dniu.

Twój program nie posiada dostępu do zegara, więc czas będzie symulowany poprzez wejście. Czasy mają postać 24-ro godzinną, od 0000 do 2300. Jeśli na wejściu napotkasz wiersz o postaci "TIME 0400", to jest godzina czwarta nad ranem, aż do odczytania nowego wiersza z czasem. Ponieważ czas nie może iść do tyłu, to jeśli po wierszu "TIME 0400" pojawi się wiersz "TIME 0100", to będzie to oznaczało upływ 21 godzin. Czasy będą podawane w postaci 4 cyfr, gdzie minuty (dwie ostatnie cyfry) będą zawsze równe zero.

Specyfikacja wejścia

Dane dla programu pochodzą z wejścia. Wiersze wejściowe mogą posiadać polecenia w swobodnym formacie. Poleceniami są słowa TIME, ON, OFF, ?, ALL, AT, STOP. W obrębie wiersza polecenia i ich argumenty mogą pojawić się w dowolnym miejscu, rozdzielone co najmniej jedną spacją. W jednym wierszu będzie tylko jedno polecenie. Polecenia posiadają następującą składnię (gdzie # oznacza liczbę dziesiętną pomiędzy 1 a 16, która określa numer wyłącznika, a @ jest 4 cyfrową liczbą określającą czas):

# ON natychmiast włącz wyłącznik #
# OFF natychmiast wyłącz wyłącznik #
# ON AT @ każdego dnia o godzinie @ włącz wyłącznik #
# OFF AT @ każdego dnia o godzinie @ wyłącz wyłącznik #
? # wypisz bieżące ustawienie wyłącznika #
? ALL wypisz bieżące ustawienie wszystkich wyłączników
TIME @ przesuń symulowany czas do godziny @
STOP zakończ symulację, wyświetl wiadomość

Specyfikacja wyjścia

Twój program powinien na wyjściu wypisywać echo wszystkich danych wejściowych oraz wypisywać wiadomości z poleceń ? i STOP.

Przykład

Dane Znaczenie Podjęte działanie
1 ON Włącz przełącznik #1 Żadne
TIME 0700 Jest godzina 7:00 rano Żadne
? 1 Jaki jest stan wyłącznika #1? Wypisz SWITCH 1 ON
2 ON AT 1300       Włączaj wyłącznik 2 o 1:00 po południu Żadne
TIME 1300 Jest godzina 1:00 po południu Żadne
? ALL Jaki jest stan 16 wyłączników Wypisz
 1   2   3   4      16
ON  ON OFF OFF ... OFF
STOP Zatrzymanie symulacji Pisz SIMULATION END

Polecenie # ON AT @ ma być wykonane w momencie, gdy czas osiągnie stan @.

Jeśli jakiś wyłącznik ma być automatycznie włączany lub wyłączany o określonym czasie, tj. 7 ON AT 1000, to jego stan zostaje ustawiony na ON za każdym razem, gdy godzina 10:00 przewinie się w symulacji, chyba że zostanie to bezpośrednio anulowane przez polecenie 7 OFF AT 1000, Gdy w ten sposób ON kasuje OFF (lub OFF kasuje ON) , nic się nie dzieje o godzinie 10:00 - stan wyłącznika nie jest w żaden sposób zmieniany. Aby przełączyć system z automatycznego ON o godzinie 10:00 na automatyczne OFF o 10:00, potrzebne są dwa polecenia 7 OFF AT 1000.

Możesz założyć, że wszystkie polecenia zostaną poprawnie wprowadzone. W danym czasie nie będzie obowiązywało nigdy więcej niż 100 automatycznych poleceń ON i OFF. Początkowo wszystkie wyłączniki znajdują się w stanie OFF, a czas ma wartość 0000.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.