Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Dalej  

Tłumaczył: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

1974

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Górna liga

Opis

HARDFLOR Ic. jest firmą specjalizującą się w wykonywaniu podłóg z lastriko. Pobierana jest opłata od stopy kwadratowej ułożonej podłogi. Firma jest bardzo dobra w wykonywaniu tych podłóg, lecz ma pewien kłopot w obliczaniu powierzchni, ponieważ podłogi występują w wielu kształtach i rozmiarach, np.

obrazek

Jedną z reguł, którą stworzył przed laty założyciel firmy, John Hardflor, jest "nigdy nie podejmować się wykonania podłogi bez prostych narożników". Firma wciąż stosuje się do tej reguły. Jednakże dalej mają kłopoty w oszacowaniu powierzchni i chcieliby teraz, aby został dla nich opracowany program, który by ich wspierał w tym przedsięwzięciu.

Firmowy kosztorysant chciałby pojawić się na miejscu potencjalnej pracy i zmierzyć wymiary pokoju, kodując je w sposób następujący:

Np. pewien pokój o poniżej przedstawionych wymiarach:

obrazek

mógłby być zakodowany za pomocą następującego zbioru par: [(N,9) (E,16) (N,4) (E,7) (S,13) (W,23)].

Napisz program, który obliczy powierzchnię. Załóż, że kodowanie jest zawsze prawidłowe - zawsze kończy się w tym samym narożniku, od którego się zaczęło.

Specyfikacja wejścia

Dane wejściowe mogą się składać z dowolnej liczby pokoi. Pierwsza liczba n  określa liczbę narożników. Jeśli liczba ta wynosi 0, to jest to znak, że dane wejściowe się kończą. Za liczbą narożników występuje n  par postaci: litera (N, S, E lub W) liczba.

Specyfikacja wyjścia

Dla każdego wczytanego opisu pokoju program powinien wypisać jego powierzchnię w postaci:

THE AREA IS 99999

Przykładowe dane wejściowe

6 N 9 E 16 N 4 E 7 S 13 W 23
0

Przykładowe dane wyjściowe

THE AREA IS 235

Problem B - Górna liga

Opis

Ten problem wymaga napisania programu wykonującego trzy zadania, które mogłyby ułatwić użycie linii telekomunikacyjnej.

Pierwsze zadanie polega na tłumaczeniu z jednego zbioru kodów na inny, Drugim zadaniem jest kompresowanie wierszy do mniejszego rozmiaru przez kompresowanie pustych znaków. Ostatnie zadanie polega na grupowaniu tych "skompresowanych" rekordów w większe rekordy. Te trzy zadania mają być wykonane kolejno.

Specyfikacja wejścia i wyjścia

Program otrzyma na wejściu wiersz sterujący, za którym wystąpi dowolna liczba wierszy z danymi. Ostatni wiersz będzie zawierał tylko cztery gwiazdki "****". wiersz sterujący będzie posiadał następującą budowę:

Pierwsza liczba N określa długość "nowych" rekordów, N < 1000.
Druga liczba M określa liczbę znaków, które powinny być tłumaczone, M ≤ 20.
M kolejnych znaków, które mają być tłumaczone.
M kolejnych znaków, na które mają być tłumaczone te pierwsze M znaków.

Na przykład, wiersz sterujący, który zawiera:

400 3 ABC $,$

oznacza, że program powinien utworzyć 400 znakowe rekordy, gdzie wszystkie litery A i C są zastąpione znakiem "$", natomiast litery B mają być zamienione na ",". Znaki pojawiające się w wierszach danych, których nie ma na liście zamian, mają pozostać niezmienione.

Kompresja polega na zastępowaniu każdego łańcucha z 4 lub więcej spacji przez wyrażenie rozpoczynające się od znaku "&", za którym należy umieścić cyfry liczby określającej liczbę spacji. W ten sposób skompresowana postać przetłumaczonego 80-znakowego wiersza, w którym pierwsze 9 znaków to spacje, następnie litery ABC i reszta to również spacje, wygląda następująco:

&9ABC&68

Na koniec, po tłumaczeniu i kompresji, wynikowe rekordy powinny być pogrupowane w "nowe" rekordy o długości N przez konkatencję skompresowanych rekordów, aż do zapełnienia "nowego" rekordu. Żaden ze skompresowanych rekordów nie powinien być dzielony pomiędzy dwa "nowe" rekordy. Jeśli nie można już dodać kolejnego rekordu bez przekroczenia rozmiaru N, pozostałe miejsce w "nowym" rekordzie powinno być uzupełnione spacjami.

Wynik działania programu powinien być wysłany do pliku tekstowego o nazwie out.txt. Plik powinien zawierać wiersze o maksymalnej długości 100 znaków. Każdy "nowy" rekord powinien być umieszczany od nowego wiersza.

Na początek:  podrozdziału   strony 

Problem C - Dolna liga

Opis

Załóżmy, że na stawie unosi się n  kaczek tworzących koło. W stawie mieszka również aligator, który uwielbia jeść kaczki. Rozpoczynając od określonej pozycji (kaczka nr 1) aligator liczy w koło i zjada każdą m-tą kaczkę (koło się zamyka w miarę zjadania kaczek). Na przykład, gdy n  = 8, a m  = 4, to poniższy schemat pokazuje numery kaczek na zewnątrz węzła oraz kolejność ich zjadania wewnątrz węzła:

obrazek

Pierwsza kaczka zostanie pożarta jako piąta z kolei, drugą kaczkę aligator zje jako czwartą z kolei, itd. Ciąg 5 4 6 1 3 8 7 2 kolejności zjadania kaczek całkowicie określa jadłospis aligatora. Napisz program, który określi ten ciąg dla danych n  i m.

Specyfikacja wejścia

Wejście składa się z ciągu wierszy. W każdym wierszu są dwie liczby rozdzielone spacją. Liczby te określają kolejno n  - liczbę kaczek (n  > 0, n  < 100), m  - odstęp (m  > 0, m  < 100). Ostatni wiersz posiada obie liczby n  i m  równe 0.

Specyfikacja wyjścia

Dla każdego wiersza danych program powinien wypisać wiersz z ciągiem liczb, które określają numery kolejno zjadanych kaczek. Każda liczba na wydruku ma zajmować 3 znaki z cyframi dosuniętymi do prawej krawędzi pola.

Przykładowe dane wejściowe

8 4
10 3
0 0

Przykładowe dane wyjściowe

  5  4  6  1  3  8  7  2
  6  4  1 10  8  2  5  7  3  9
Na początek:  podrozdziału   strony 

Problem D - Zliczanie liczb

Opis

Twój program ma wczytać zbiór wierszy i dla każdego z nich obliczyć sumę liczb w tym wierszu zawartych. Każdy wiersz zawiera 1 lub więcej liczb. Liczby są rozdzielone przecinkami. Liczba może być dodatnia lub ujemna (poprzedzona znakiem minus) i może lub nie musi zawierać część ułamkową (poprzedzoną kropką dziesiętną wg systemu anglosaskiego). Pomiędzy liczbami oraz wewnątrz samych liczb mogą wystąpić spacje. Oto przykładowy wiersz:

1    23.4,-5  ,  .00 2 , 1 8 6

W wierszu tym znajdują się liczby:

123.4, -5, 0.002, 186

Specyfikacja wejścia

Na wejściu znajduje się ciąg wierszy. Ostatni wiersz jest wierszem pustym. W każdym niepustym wierszu znajdują się zapisane liczby zgodnie z podanym wcześniej opisem.

Specyfikacja wyjścia

Dla każdego niepustego wiersza program powinien wypisać:

CARD = treść wiersza
SUM  = wartość sumy

Przykładowe dane wejściowe

1    23.4,-5  ,  .00 2 , 1 8 6

Przykładowe dane wyjściowe

CARD = 1    23.4,-5  ,  .00 2 , 1 8 6
SUM  =       304.402000000

Do wyświetlenia sumy użyj pola o szerokości 20 znaków, liczba ma posiadać 9 cyfr dziesiętnych po przecinku i być dosunięta do prawej krawędzi pola.

UWAGI:

  1. Załóż, że dane wejściowe są zawsze poprawne.
  2. Załóż, że wszystkie wartości można przedstawić jako standardowe liczby zmiennoprzecinkowe.
  3. Nie musisz się martwić precyzją części ułamkowych; 0,1 nie można przedstawić dokładnie, lecz wewnętrzna reprezentacja będzie zaakceptowana jako poprawna.
Na początek:  podrozdziału   strony 

Problem E - Trójkątny tekst

Opis

Napisz program, który wczyta wiersze tekstu i wypisze ten tekst w trójkącie. Wiersze trójkąta mają być wyrównane z lewej strony. Ostatni wiersz trójkąta ma zawierać jeden wyraz. Kropka kończąca zdanie ma być razem z ostatnim wyrazem - w tekście będą zawarte tylko kropki jako znaki interpunkcyjne. Każdy z wierszy powinien zawierać minimalną liczbę słów, które są potrzebne, aby dany wiersz był dłuższy od leżącego pod nim. Wszystkie nadmiarowe słowa mają być umieszczone w pierwszym wierszu. Tekst będzie zawierał co najwyżej 400 znaków. Pomiędzy słowami nie pojawiają się dodatkowe spacje. Również spacje nie występują przed pierwszym słowem, a żadne ze słów nie jest rozdzielone pomiędzy dwoma wierszami. Koniec tekstu jest oznaczony pustym wierszem.

Przykładowe dane wejściowe

MUCH CURRENT RESEARCH IN ARTIFICIAL INTELLIGENCE INVOLVES
DESIGNING PROGRAMS THAT CAPTURE THE KNOWLEDGE AND REASONING
PROCESSES OF HIGHLY INTELLIGENT SPECIALISTS. THE PRACTICAL GOAL OF
SUCH WORK IS TO MAKE SPECIALIZED EXPERTISE MORE GENERALLY
ACCESSIBLE.

Przykładowe dane wyjściowe

MUCH CURRENT RESEARCH IN ARTIFICIAL INTELLIGENCE INVOLVES
DESIGNING PROGRAMS THAT CAPTURE THE KNOWLEDGE AND
REASONING PROCESSES OF HIGHLY INTELLIGENT
SPECIALISTS. THE PRACTICAL GOAL
OF SUCH WORK IS TO MAKE
SPECIALIZED EXPERTISE
MORE GENERALLY
ACCESSIBLE.
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.