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

1985

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Słowa podzbioru

Opis

W tym problemie prosi się ciebie o określenie, czy dwa słowa pochodzą z tego samego alfabetu podstawowego. Jeśli jedno słowo powstaje poprzez przestawienie liter drugiego słowa, to te dwa słowa nazywa się "anagramami", jak "rose" i "sore". Problem ten wymaga od ciebie określenia, czy te dwa słowa używają tych samych liter, lecz niekoniecznie w tej samej ilości. Na przykład "curse" i "rescue" pochodzą z tego samego podstawowego alfabetu, lecz "cure" już nie, ponieważ jego alfabet podstawowy nie zawiera litery "s", której używają oba słowa "curse" i "rescue".

Twój program ma w kółko odczytywać pary słów z pliku. Każda para zawarta jest w jednym wierszu i jest wyrównana lewostronnie w pierwszych 20 kolumnach  tego wiersza (kolumny niewykorzystane są wypełnione spacjami). Twój program powinien wyprowadzać do innego pliku oba słowa z wiadomością o tym, że używają lub nie tych samych liter. Para słów "LAST" i "PAIR" będzie oznaczała koniec danych. Ostatniej pary słów nie należy już przetwarzać.

Na początek:  podrozdziału   strony 

Problem B - Czarodziejski kwadrat

Opis

Pewien chłop próbował rozwiązać problem umieszczenia liczb całkowitych od jeden do szesnastu w macierzy kwadratowej o czterech wierszach i czterech kolumnach w taki sposób, aby suma iloczynów liczb w każdej kolumnie i w każdym wierszu (osiem iloczynów) była jak największa. Przy pomocy kija chłop narysował swoją macierz na piasku i umieścił w niej te szesnaście liczb.

Stary czarodziej przelatywał na swoim smoku i zobaczył macierz narysowaną przez chłopa. Czarodziej wypowiedział uwagę: "Twoja macierz jest dobra, lecz największą sumę można osiągnąć poprzez przestawienie tych czterech liczb." Zsiadł ze smoka i wymazał cztery liczby w macierzy. Jednakże zanim zdołał zamienić liczby w macierzy, spróbował zaczerpnąć powietrza i padł martwy powalony starym syndromem czarodzieja.

Napisz program rekonstruujący tą macierz, którą czarodziej miał zamiar ukończyć. Dane wejściowe będą pochodziły z pliku i będą się składały z pojedynczego wiersza zawierającego szesnaście liczb całkowitych, każda wyrównana prawostronnie w 3-kolumnowym polu. Wartości te reprezentują macierz w chwili śmierci czarodzieja. Pierwsze cztery wartości należą do pierwszego wiersza macierzy, następne cztery należą do drugiego, itd. Cztery z wartości wejściowych będą zerami, które reprezentują wartości wymazane przez czarodzieja. Pozostałe wartości będą z zakresu od 1 do 16 i znajdą się na pozycjach wybranych przez chłopa.

Twój program powinien wyprowadzić do pliku zrekonstruowaną macierz jako kwadrat w czterech wierszach z czterema wartościami w każdym. Za tą macierzą ma się pojawić jej wartość będąca sumą iloczynów wierszy i kolumn.

Na początek:  podrozdziału   strony 

Problem C - Dopasowywanie wzorca

Opis

Tablica znakowa o rozmiarze dziesięć na dziesięć zawiera 5 znaków "X", 5 znaków "O" i 90 kropek (zobacz na przykłady poniżej). Wszystkie 5 znaków "X" łączy się ze sobą, albo przylegle, albo po przekątnej; podobnie jest z 5 znakami "O". Pożądanym jest określenie, czy wzór ze znaków "X" odpowiada wzorowi ze znaków "O", przez co rozumiemy, iż wzór z "X" da się dokładnie nałożyć na ten drugi. Dozwolone są tylko przesunięcia i obroty, odbicia symetryczne nie są dozwolone.

W pliku do przetworzenia znajdą się dokładnie cztery zestawy danych. Każdy zestaw składa się z dziesięciu wierszy po dziesięć znaków (kropek, "X" i "O"). Litery są dużymi literami alfabetu i nie ma pomiędzy nimi żadnych spacji. Wynik działania programu powinien zostać zapisany w pliku. Dla każdego zestawu danych twój program powinien przeskoczyć jeden wiersz, a następnie zapisać zestaw danych jako dziesięć wierszy znaków, lecz z jedną spacją pomiędzy sąsiednimi znakami (dokładnie tak, jak pokazano poniżej). Następnie twój program powinien określić, czy te dwa wzory są ze sobą zgodne i wypisać bezpośrednio pod tablicą albo "Patterns match" (wzory pasują do siebie), albo "Patterns do not match" (wzory nie pasują do siebie).

Poniżej znajdują się przykładowe dane wyjściowe z dwóch zestawów danych, poprawnie zapisane z poprawną wiadomością poniżej.

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . X . . .
. . . . . . X X . .
. . . . . . X . . .
. . O . . . X . . .
O O O O . . . . . .
. . . . . . . . . .
. . . . . . . . . .
Patterns do not match

. . . . . . . . . .
. . . . . X . . . .
. . . . . . X . . .
. . . . . . . X . .
. . . . O O X X . .
. . . O . O . . . .
. . O . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
Patterns match
Na początek:  podrozdziału   strony 

Problem D - Sterowanie fabryką chemiczną

Opis

Pewna fabryka chemiczna posiada cztery zbiorniki połączone ze sobą w sposób pokazany na rysunku. Przy każdym zbiorniku znajduje się zawór kontrolujący przepływ cieczy do zbiornika oraz pompa kontrolująca wypływ. Komputer sterujący procesem kontroluje zawory i pompy, otrzymując swoje dane wejściowe z konsoli operatora i z czujników w zbiornikach. Masz za zadanie napisać program, który będzie symulował transport płynów pomiędzy zbiornikami wg poniższego opisu.

Początkowo dokonaj założenia, iż wszystkie zawory są zamknięte i wszystkie pompy są wyłączone. Załóż również, że wszystkie rurociągi są wypełnione tak, iż płyn wypompowywany z jednego zbiornika wpływa natychmiast do innego zbiornika. Jeśli zostanie otwarty więcej niż jeden zawór, to przepływ będzie równo dzielony pomiędzy zbiornikami. W tym samym czasie może pracować więcej niż jedna pompa. Płyn może wpływać do zbiornika tylko poprzez jego zawór, a wypływać tylko poprzez jego pompę.

Dane wejściowe dla tego problemu będą odczytywane z pliku. Pierwsze cztery wiersze danych wejściowych podadzą całkowitą pojemność oraz początkową zawartość (w litrach) każdego zbiornika (zbiornik nr 1 w wierszu pierwszym, itd.). Każdy wiersz będzie zawierał dwie liczby rzeczywiste oddzielone spacją (pojemność, później zawartość). Piąty wiersz wejściowy będzie zawierał pojedynczą wartość rzeczywistą, wydajność pomp w litrach na sekundę. Wszystkie pompy mają tę samą wydajność. Możesz przyjąć, iż pojemności zbiorników i ich zawartości są mniejsze lub równe 10.000 i że wydajność pomp jest nie mniejsza niż 1 litr na sekundę oraz że żadna z tych liczb nie ma części ułamkowych.

Raz na sekundę komputer wykonuje następujące kroki. Pobiera rozkaz z konsoli operatora (opisany poniżej) i wykonuje go. Następnie sprawdza czujniki zbiorników. Jeśli dowolny zbiornik został wypełniony w 95% (lub więcej) swojej pojemności, to jego zawór jest zamknięty. Jeśli dowolny zbiornik został opróżniony do 5% (lub mniej) swojej pojemności, jego pompa jest wyłączona. Załóż, iż te środki ostrożności uniemożliwiają całkowite opróżnienie lub wypełnienie zbiorników, jedynie być może tylko w ich stanie początkowym. Aby uniknąć przeciążenia pomp, jeśli wszystkie zawory są zamknięte, wszystkie pompy są wyłączone.

Komputer otrzymuje rozkazy będące słowami 16-bitowymi. Każdy bit 0 jest ignorowany, a każdy bit 1 określa jakieś działanie. Pierwsze cztery bity reprezentują działania włączania pomp od 1 do 4, następne cztery bity reprezentują wyłączanie pomp od 1 do 4, następne 4 bity reprezentują otwarcie zaworów od 1 do 4 i ostatnie 4 bity reprezentują zamknięcie zaworów od 1 do 4. Komputer musi ignorować sprzeczne działania (np. włączenie pompy 1 i wyłączenie pompy 1, gdy bity 1 i 5 mają stan 1, wtedy oba działania zostają zignorowane i pompa nr 1 pozostaje w swoim stanie poprzednim. To samo odnosi się do zaworów.).

Każdy rozkaz jest przedstawiany jako pierwsze szesnaście znaków w wierszu wejściowym, każdy z tych znaków to 0 lub 1. Za tym rozkazem znajduje się spacja, a następnie liczba całkowita określająca czas wydania rozkazu mierzony w sekundach od startu symulacji (czas 0). Rozkazy pojawiają się w ścisłej kolejności wg czasu, jeden rozkaz na wiersz. W tym samym czasie zegara nie może pojawić się więcej niż jeden rozkaz.

Twoja symulacja powinna przetworzyć wszystkie rozkazy wejściowe, a następnie pracować dalej, aż czujniki zbiorników zatrzymają wszystkie pompy. Następnie należy wyprowadzić do pliku czas zegarowy (liczbę sekund, które upłynęły od startu symulacji) i bieżącą ilość płynu w każdym zbiorniku z dokładnością do jednej cyfry dziesiętnej po przecinku. Opisz odpowiednio każdą wartość.

Na początek:  podrozdziału   strony 

Problem E - Wnioskowany handicap

Opis

Z powodu strajku lokalnych oddziałów Sekretarzy Połączonych Lig i Związku Szpachlarzy menadżer pobliskiej kręgielni Pin Palace Petera Pipera potrzebuje pilnie nieco programowania do zautomatyzowania obliczania średnich i handicapów dla lig, które grają tam w kręgle. Parametry formuły handicapu w każdej z lig nie są dostępne, lecz znaleziono kilka starych arkuszy stanu dla każdej ligi i muszą być one użyte do wywnioskowania tych parametrów. Oczywiście żaden z sekretarzy ligowych nie zdradzi, jakie wartości używa jego lub jej liga.

Wiadomo, że algorytm obliczania handicapu jest taki sam dla wszystkich lig i wygląda następująco:

  1. Średni wynik average (na grę) kręglarza jest obcinany do liczby całkowitej (pomiędzy 0 a 300) i odejmowany od parametru o nazwie PAR.
  2. Jeśli różnica jest ujemna, to handicap wynosi 0. W przeciwnym razie wyznaczany jest procent dany parametrem FCT, a wynik obcinany do wartości całkowitej dla handicapu.

Symbolicznie:

Handicap = floor (max(0,PAR - average) * FCT/100 )

Wiadomo, iż polityką państwową jest to, iż parametry są liczbami całkowitymi z FCT w zakresie od 50 do 100 i PAR w zakresie od 150 do 300. Plik danych zawiera rekord dla każdej ligi, w którym znajdują się następujące informacje (wyrównane prawostronnie w każdym polu):

Kolumny Zawartość
1-3
5-6
8-10
12-14
16-18
20-22
.
.
64-66
68-70
Numer Ligi
Liczba par średnia-handicap w rekordzie
średnia 1
handicap 1
średnia 2 (jeśli obecne)
handicap 2 (jeśli obecne)
.
.
średnia 8 (jeśli obecne)
handicap 8 (jeśli obecne)

Możesz założyć, że wszystkie pozostałe znaki w wierszu wejściowym są spacjami.

Dla każdego rekordu w pliku aż do Numeru Ligi = 0 program ma wyprowadzić do pliku w czytelnej postaci Numer Ligi i wszystkie pary FCI-PAR, które mogły być użyte do obliczenia par średnia-handicap danych dla tej ligi. Jeśli żadna taka para nie istnieje, należy wypisać uwagę, iż przynajmniej jeden dany handicap jest zły i wypisać wszystkie pary FCT-PAR, które mogłyby zostać użyte do otrzymania wszystkich par średnia-handicap za wyjątkiem jednej  w rekordzie danych tej ligi. Jeśli żadna z par FCT-PAR nie jest spójna z mniej niż dwoma błędami w danych wejściowych, należy to zaznaczyć.

(Tekst zadania jest pisany bardzo niezrozumiałym i kolokwialnym językiem, przepraszamy za ewentualne nieścisłości w tłumaczeniu).

Na początek:  podrozdziału   strony 

Problem F - Formatowanie ekranu

Opis

Napisz program, który odczyta tekst z pliku i przeformatuje go do wyświetlenia. Tekst ma być wycentrowany na obszarze ekranu. Powinien być otoczony ramką zbudowaną ze znaku określonego w danych wejściowych.

Tekst powinien być wyświetlony w sposób następujący:

  1. Dla każdego zestawu danych wyjście powinno pojawić się na nowej stronie i powinno być wycentrowane w obszarze wyświetlania o szerokości 80 kolumn. Dane wyjściowe dla każdego zestawu danych zmieszczą się na pojedynczej stronie.
  2. Długość wiersza wyświetlanego tekstu będzie określana w danych wejściowych i będzie w granicach 1 -78 znaków.
  3. Tekst powinien być formatowany do określonej długości wiersza i wydrukowany w obszarze wyświetlania będąc w całości otoczonym ramką określoną przez dane wejściowe.

Można założyć, że w każdym zestawie danych tekst nie będzie zawierał słów dłuższych od wybranej długości wiersza i po sformatowaniu będzie mógł być drukowany na pojedynczej stronie drukarki. Znakami ograniczającymi słowa w tym tekście będą spacje, znaki końca wiersza, znaki początku wiersza i znacznik końca pliku. Każdy sformatowany wiersz tekstu ma zawierać maksymalnie możliwą liczbę słów, które tworzą wiersz o długości równej lub mniejszej od wybranej.

Specyfikacja wejścia

Plik zawiera wiele zestawów danych ułożonych następująco:

Numer rekordu Wartość
     1        Długość wiersza dla tekstu wyświetlanego (1-78)
     2        Znak do użycia w ramce otaczającej tekst
     3        Liczba następnych wierszy (1-50)
     4  ---+
     .     |
     .     +- Tekst do sformatowania i wydruku
     .     | (bez przylegających do siebie spacji)
     n  ---+

Specyfikacja wyjścia

Dla każdego zestawu danych twój program powinien zapisywać w pliku sformatowany tekst wycentrowany w obrębie 80-kolumnowego wiersza. Pierwszym wierszem zapisanym w pliku ma być wiersz ramki utworzonej ze znaku wybranego przez użytkownika, po którym następują pozostałe wiersze sformatowanego tekstu (rozpoczynające się i zakończone znakiem ramki), a na końcu ma wystąpić kolejny wiersz ramki. Każdy zestaw danych powinien się rozpoczynać u góry nowej strony.

Przykładowe dane wejściowe

Przykładowy zestaw danych:

19
*
6
This is some sample text that has been formatted
by
this program for display. The specified
line length was 19 characters with the text to be
surrounded by a border consisting
of '*'.

Przykładowe dane wyjściowe

Sformatowany tekst przykładowy (wyśrodkowany w 80 kolumnach):

                        *********************
                        *This is some sample*
                        *text that has been *
                        *formatted by this  *
                        *program for        *
                        *display. The       *
                        *specified line     *
                        *length was 19      *
                        *characters with the*
                        *text to be         *
                        *surrounded by a    *
                        *border consisting  *
                        *of '*'.            *
                        *********************
Na początek:  podrozdziału   strony 

Problem G - Wypisywanie słów z binarnych drzew wzorów

Opis

W pewnym drzewie wzorów węzły-liście zawierają litery jako dane i nie posiadają węzłów-dzieci. Węzły wewnętrzne posiadają jako dane "+" lub "*" i mają dwoje dzieci – lewe poddrzewo i prawe poddrzewo. Znak "+" oznacza alternację – można tu wybrać albo znaki z lewego poddrzewa, albo znaki z prawego poddrzewa. Znak "*" oznacza konkatencję – łańcuch z lewego poddrzewa musi być łączony z łańcuchem drzewa prawego. Na przykład:

reprezentuje słowa:

ABDF
ABEF
CDF
CEF

Masz napisać program, który odczytuje binarne drzewa wzorów z pliku, a następnie wyprowadza do pliku wszystkie słowa reprezentowane w każdym drzewie wzorów. W drzewie wzorów będzie maksymalnie 50 węzłów. Pierwszy rekord w zestawie zawiera liczbę węzłów w drzewie, N, wyrównaną prawostronnie e kolumnach 1-2. Następne N rekordów zawiera następujące informacje o węzłach:

Kolumna Zawartość
  1-2   numer węzła (korzeń jest zawsze
        węzłem nr 1; inne węzły mogą mieć
        dowolne numery w dowolnej kolejności)
  4     dane w tym węźle (albo litera, albo
        "+" lub "*")
  6-7   liczba lewych potomków (0 = żaden)
  9-10  liczba prawych potomków (0 = żaden)

Wszystkie wartości są wyrównane prawostronnie we wskazanych polach.

Dla każdego drzewa wyprowadź do pliku wszystkie słowa reprezentowane przez dane drzewo, po jednym słowie w wierszu. Kontynuuj przetwarzanie zestawów danych drzew wzorów aż do napotkania rekordu końcowego z ujemną liczbą węzłów.

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.