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

1981

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Obszary szachownicy

Opis

Rozważmy szachownicę o wymiarze 10 × 10, której każde pole posiada kolor biały lub czarny. Obszarem szachownicy jest każdy zbiór przyległych pól. (Dwa pola nie są przyległe, jeśli posiadają wspólny narożnik, lecz nie stykają się krawędziami.)  Obszar jest dziurą, jeśli wszystkie jego pola są białe i jeśli każda krawędź nie zawarta w całości wewnątrz obszaru znajduje się albo na krawędzi szachownicy, albo styka się z polem czarnym. Na przykład, poniższa szachownica zawiera 8 dziur.

obrazek

Masz napisać program, który znajdzie liczbę dziur w takiej szachownicy i wypisze liczbę białych pól w każdej z dziur.

Specyfikacja wejścia

Na wejściu program otrzyma dziesięć wierszy, które będą reprezentować kolejne rzędy pól szachownicy. Każdy wiersz będzie się składał z 10 cyfr 0 lub 1. Cyfry te będą przedstawiały kolor pola w danym wierszu szachownicy. Kolor czarny będzie przedstawiony cyfrą 1, kolor biały będzie przedstawiony cyfrą 0. Możesz założyć, że w danych wejściowych nie będzie błędów.

Specyfikacja wyjścia

Na wyjściu program powinien wypisać liczbę dziur, oraz dla każdej z nich liczbę zawartych w niej białych pól szachownicy. Kolejność wypisywania tych liczb pól jest dowolna.

Przykładowe dane wejściowe

1011111011
1110010011
0100110000
0110100000
1010111000
1011101000
1000001000
1111111000
0001011000
0000101000

Przykładowe dane wyjściowe

NUMBER OF HOLES IS 8
HOLE 1 CONTAINS 1 SQUARES
HOLE 2 CONTAINS 6 SQUARES
HOLE 3 CONTAINS 30 SQUARES
HOLE 4 CONTAINS 2 SQUARES
HOLE 5 CONTAINS 8 SQUARES
HOLE 6 CONTAINS 7 SQUARES
HOLE 7 CONTAINS 1 SQUARES
HOLE 8 CONTAINS 1 SQUARES
Na początek:  podrozdziału   strony 

Problem B - Analiza progu rentowności producenta

Opis

Ten problem polega na wyliczeniu punktu progu rentowności BEP (ang. Break-Even Point) dla danego produktu, który ma być produkowany. Punkt BEP występuje wtedy, gdy całkowity koszt wydatków jest równy całkowitemu kosztowi dochodów. W ten sposób punkt BEP określa minimalną ilość produktu, która musi zostać sprzedana, aby dochód firmy pokrył całkowite wydatki poniesione na wytworzenie tego produktu.

Całkowity dochód (R) jest równy jednostkowej cenie sprzedaży (P) pomnożonej przez ilość jednostek do wyprodukowania (Q).

R = P × Q

Całkowity koszt (C) jest równy sumie ustalonych kosztów operacyjnym (F) i zmiennych kosztów jednostkowych (V) pomnożonych przez ilość jednostek do wyprodukowania (Q).

C = F + V × Q

Punkt BEP występuje wtedy, gdy całkowity dochód (R) jest równy lub większy od całkowitego kosztu (C). Zysk lub stratę jednostkową (U) można wyliczyć, odejmując całkowity koszt (C) podzielony przez ilość jednostek do wyprodukowania (Q) od jednostkowej ceny sprzedaży (P).

U = P - C / Q

Mając dane ustalone koszty operacyjne (F), zmienne koszty jednostkowe (V), jednostkową cenę sprzedaży (P) oraz zakres jednostek produktu do wytworzenia (N), program dla podanego zakresu od 1 do N ma utworzyć tablicę pokazującą całkowity koszt, całkowity dochód, całkowity zysk (lub stratę) oraz jednostkowy dochód (lub stratę). Dla celów tej analizy podziel zakres na 25 równych kroków. Jeśli N nie dzieli się przez 25, to użyj kroków, które są liczbami całkowitymi o wartościach najbliższych do

(k × N) / 25, dla k = 1, 2, ..., 25

Specyfikacja wejścia

Program na wejściu otrzyma nazwę produktu w pierwszym wierszu, a w następnym ciąg liczb, które będą kolejno reprezentować:

Specyfikacja wyjścia

W pierwszym wierszu należy umieścić nazwę produktu.

W drugim wierszu należy umieścić etykiety kolumn: QUANTITY, TOTAL COST,  TOTAL REVENUE, TOTAL PROFIT/LOSS, PROFIT/LOSS PER UNIT.

W kolejnych 25 wierszach, odpowiadających 25 krokom zakresu N, należy podać kolejno wartości kroku, C, R, R-C, U. Obok wiersza najbliższego punktowi BEP wydrukuj gwiazdkę *. Jeśli występują dwa wiersze jednakowo bliskie BEP, gwiazdkę wydrukuj przy obu.

Przykładowe dane wejściowe

DVD DRIVE
60000.00 54.00 65.00 10000

Przykładowe dane wyjściowe

DVD DRIVE
QUANTITY    TOTAL COST  TOTAL REVENUE  TOTAL PROFIT/LOSS  PROFIT/LOSS PER UNIT
     400      81600.00       26000.00          -55600.00               -139.00
     800     103200.00       52000.00          -51200.00                -64.00
    1200     124800.00       78000.00          -46800.00                -39.00
    1600     146400.00      104000.00          -42400.00                -26.50
    2000     168000.00      130000.00          -38000.00                -19.00 
    2400     189600.00      156000.00          -33600.00                -14.00
    2800     211200.00      182000.00          -29200.00                -10.43
    3200     232800.00      208000.00          -24800.00                 -7.75
    3600     254400.00      234000.00          -20400.00                 -5.67
    4000     276000.00      260000.00          -16000.00                 -4.00
    4400     297600.00      286000.00          -11600.00                 -2.64
    4800     319200.00      312000.00           -7200.00                 -1.50
    5200     340800.00      338000.00           -2800.00                 -0.54
    5600     362400.00      364000.00            1600.00                  0.29 *
    6000     384000.00      390000.00            6000.00                  1.00
    6400     405600.00      416000.00           10400.00                  1.63
    6800     427200.00      442000.00           14800.00                  2.18
    7200     448800.00      468000.00           19200.00                  2.67
    7600     470400.00      494000.00           23600.00                  3.11
    8000     492000.00      520000.00           28000.00                  3.50
    8400     513600.00      546000.00           32400.00                  3.86
    8800     535200.00      572000.00           36800.00                  4.18 
    9200     556800.00      598000.00           41200.00                  4.48
    9600     578400.00      624000.00           45600.00                  4.75
   10000     600000.00      650000.00           50000.00                  5.00 
Na początek:  podrozdziału   strony 

Problem C - Interpreter

Opis

Oto opis w notacji BNF (Backus-Naur Form) bardzo prostego języka programowania:

<cyfra> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<zmienna> ::= A | B | C | D | E
<operator> ::= + | - | *
<liczba> ::= <cyfra> | <cyfra> <cyfra>
<składnik> ::= <liczba> | <zmienna>
<wyrażenie> ::= <składnik> | <składnik> <operator> <składnik>
<polecenie> ::= <zmienna> = <wyrażenie> | STOP

Zauważ, że poniższe polecenia są poprawne w tym języku i posiadają oczywiste znaczenie:

A=4
B=33
C=A+B
D=62*B
STOP

Natomiast poniższe polecenia nie są poprawne w tym języku:

K=31      (K nie jest prawidłową zmienną)
B=962    
(liczba nie może posiadać więcej niż dwie cyfry)
C=-A     
(jednoargumentowy minus nie jest zdefiniowany)
D=A+B*C  
(dozwolony jest tylko jeden operator w wyrażeniu)
A = B + C
(nie są dozwolone spacje)

Masz napisać interpreter dla tego języka. Interpreter powinien akceptować poprawne polecenia aż do polecenie STOP. Gdy otrzyma polecenie STOP, powinien wypisać wszystkie przypisane zmienne oraz ich bieżący stan. Interpreter nie powinien wykonywać polecenia, jeśli wymaga ono wartości zmiennej, do której jeszcze nie została przypisana wartość. Program na wejściu będzie otrzymywał tylko poprawne składniowo polecenia w tym języku. Możesz założyć, że w danych wejściowych będzie obecne polecenie STOP. Również możesz założyć, że wielkość wszystkich zmiennych nie przekroczy zakresu 32 bitowych liczb całkowitych.

Specyfikacja wejścia

Na wejściu program otrzymuje ciąg wierszy, które zawierają kolejne polecenia do wykonania przez interpreter. Ostatni wiersz będzie zawsze zawierał polecenie STOP.

Specyfikacja wyjścia

Po otrzymaniu wiersza z poleceniem STOP program powinien wypisać wszystkie zmienne o przypisanej wartości oraz ich bieżącą zawartość.

Przykładowe dane wejściowe

A=5
D=6*A
C=D+60
STOP

Przykładowe dane wyjściowe

A=        5
C=       90
D=       30
Na początek:  podrozdziału   strony 

Problem D - Milaż

Opis

Producent samochodów przeprowadza badania dotyczące milażu, w których pewna liczba pojazdów ma być normalnie użytkowana. Każdemu kierowcy zostanie przydzielony samochód, dla którego ma on notować informację o zużyciu benzyny, warunkach pracy, itp. W szczególności przy każdym zakupie benzyny kierowca notuje wskazania licznika przebytej odległości, ilość zakupionej benzyny, czy zbiornik paliwa został zapełniony, czy też nie, oraz cenę zakupu. Twoim zadaniem jest napisanie programu, który umieści w tabeli informację o wszystkich samochodach uczestniczących w tych badaniach.

Specyfikacja wejścia

Dane wejściowe będą się składały z ciągu wierszy, które posiadają następującą budowę:

cn or gp cd tf

gdzie:

cn - numer samochodu (ang. car number). Będzie to liczba całkowita od 0 do 999 włącznie.
or - odczyt licznika przebytej drogi (ang. odometer reading) w milach. Będzie to liczba zmiennoprzecinkowa z jedną cyfrą po kropce.
gp - liczba zakupionych galonów benzyny (ang. gallons purchased). Będzie to liczba zmiennoprzecinkowa z jedną cyfrą po kropce
cd - koszt jednego galonu benzyny w dolarach (ang. cost in dollars). Będzie to liczba zmiennoprzecinkowa z dwoma cyframi po przecinku.
tf - F, jeśli zbiornik był pełny (ang. tank full), X, jeśli nie.

Wiersze będą pogrupowane w pakiety; każdy pakiet będzie zawierał opis jednego samochodu o określonym numerze - numer ten wystąpi tylko w jednym pakiecie. Wewnątrz pakietu wiersze będą ułożone w rosnącym porządku odczytów licznika przebytej drogi. Ostatni wiersz danych wejściowych zawiera ujemny numer samochodu. Możesz założyć, że dane wejściowe będą w podanym formacie i nie będą zawierały błędów. W pierwszym wierszu będzie podana tylko początkowa wartość licznika przebytej drogi oraz na końcu wystąpi litera F, która oznacza pełny zbiornik w tym punkcie. Możesz dalej założyć, że podczas trwania badań żaden z liczników przebytej drogi nie będzie zerowany.

Specyfikacja wyjścia

Dane wyjściowe dla każdego samochodu uczestniczącego w badaniach powinny wyglądać następująco:

                            CAR NUMBER xxx
                 GALLONS
ODOMETER        PURCHASED       FILL UP?        COST            MPG
 xxxxx.x                           YES                                  INITIAL
 xxxxx.x           xx.x            zzz          xx.xx           xx.x
 .......           ....            ...          .....           ....
 xxxxx.x           xx.x            zzz          xx.xx           xx.x
 xxxxx.x          xxx.x                       xxxx.xx           xx.x    FINAL

gdzie CAR NUMBER - numer samochodu, ODOMETER - wskazania licznika przebytej drogi, GALLONS PURCHASED - liczba zakupionych galonów benzyny, FILL UP? - czy zbiornik był pełen, COST - koszt jednego galonu benzyny, MPG - liczba przebytych mil na jeden galon benzyny, x - oznacza cyfrę lub spację, zzz - oznacza napis YES, gdy zbiornik paliwa był pełny, lub NO w przypadku przeciwnym, INITIAL - pierwszy wiersz danych, FINAL - końcowy wiersz danych dla danego samochodu. Możesz założyć, że liczba cyfr określona w powyżej podanych polach jest wystarczająca.

Uwaga, kolumna MPG powinna przedstawiać milaż pomiędzy napełnieniami zbiornika paliwa, a dane te należy wyświetlać tylko wtedy, gdy da się je policzyć. Wierszu końcowy tabeli (FINAL) zawiera w pierwszej kolumnie liczbę przebytych mil, całkowitą liczbę zakupionych galonów paliwa, całkowity koszt zakupionego paliwa oraz wartość liczby mil na jeden galon, wyliczoną z początkowej i ostatniej wartości licznika przebytej drogi. Każdą tabelę należy oddzielić jednym pustym wierszem od pozostałych.

Na początek:  podrozdziału   strony 

Problem E - Pozycja drużyny

Opis

Twoim zadaniem jest napisanie programu analizującego wyniki zawodów sportowych.

Specyfikacja wejścia

Na wejściu twój program otrzyma 30 wierszy z danymi. Pierwsze 20 wierszy posiada następujący format (poszczególne pola są rozdzielone znakami tabulacji o kodzie 9):

nazwa drużyny A - do 12 znaków;
punkty drużyny A - liczba całkowita;

nazwa drużyny B - do 12 znaków;
punkty drużyny B - liczba całkowita.

Następne 10 wierszy posiada następujący format (pola rozdzielone znakami tabulacji o kodzie 9):

nazwa drużyny - do 12 znaków;
nazwa drużyny - do 12 znaków.

Pierwsze 20 wierszy stanowi zapisy 20 lub mniej drużyn w 20 różnych meczach, jeden wiersz dotyczy jednego meczu. Na przykład, wiersz z zawartością:

FLORIDA	17	AUBURN	14

będzie oznaczał, że FLORIDA pokonała AUBURN punktacją 17 do 14. Zwycięska drużyna niekoniecznie będzie podana jako pierwsza. W meczach nie ma remisów i żadna z drużyn nie gra dwóch meczów z żadną inną drużyną - zawsze tylko jeden.

Specyfikacja wyjścia

Ostatnie 10 wierszy wejściowych będzie odpowiadało zapytaniom na temat "faktów: przedstawionych w pierwszych 20 wierszach. Każdy z tych wierszy będzie zawierał dwie nazwy drużyn. Zadaniem twojego programu będzie ustalić, czy:

  1. Jedna z drużyn pokonała drugą bezpośrednio w meczu.
  2. Jedna z drużyn pokonała drugą pośrednio - przez pokonanie drużyny, która wygrała z pierwszą drużyną lub poprzez pokonanie drużyny, która pokonała drużynę, która pokonała tę pierwszą, itd.
  3. Każda z drużyn pokonała się pośrednio.
  4. Żadna z drużyn ani się nie pokonała w meczu, ani nie pokonała się pośrednio.

Dla każdego z 10 ostatnich wierszy twój program powinien wypisać na wyjściu odpowiedni do sytuacji wiersz:

  1. team-A DEFEATED team-B
  2. team-A DEFEATED team-B INDIRECTLY
  3. team-A AND team-B HAVE DEFEATED EACH OTHER INDIRECTLY
  4. team-A AND team-B ARE NOT COMPARABLE

team-A i team-B oznaczają nazwy drużyn odczytane z wiersza (uwaga: team-A nie oznacza pierwszej drużyny, jest jedną z dwóch podanych w wierszu).

Na początek:  podrozdziału   strony 

Problem F - Edytowanie liczb

Opis

Celem tego zadania jest stworzenie programu, który będzie edytował liczby całkowite, korzystając z "szablonu" do wytworzenia dogodnej do wydruku liczby wyjściowej z przecinkami, kropką dziesiętną (liczby są zapisane w systemie anglosaskim, przyp. tłum.), itp.

Specyfikacja wejścia

Na wejściu pojawi się zbiór wierszy o następującym formacie:

n m

gdzie:

n  - liczba całkowita, która może być poprzedzona spacjami lub zerami wiodącymi. Możesz założyć, że wartość tej liczby zmieści się w zmiennej o standardowym typie liczb całkowitych 32 bitowych.

m  - maska, która będzie złożona ze znaków "Z", "9", ",", "-"  i ".".

Koniec danych wejściowych jest oznaczany przez pusty wiersz.

Specyfikacja wyjścia

Znaki w masce są przetwarzane od strony lewej do prawej. Każde Z lub 9 odnosi się do jednej cyfry we wejściowej liczbie całkowitej; liczba przetworzonych cyfr w tej liczbie jest równa całkowitej ilości znaków Z i 9 w masce. Jeśli maska posiada n znaków Z i 9, to edycji ulega n cyfr liczby całkowitej znajdujących się po prawej stronie. Przy przetwarzaniu obowiązują następujące reguły:

  1. Znaki Z mają być zastąpione albo przez cyfry z liczby (jeśli dana cyfra nie jest zerem wiodącym ani spacją) lub przez spację (jeśli cyfra jest zerem wiodącym lub spacją).
  2. Znaki 9 mają być zastąpione cyfrą z liczby, nawet jeśli ta cyfra zostałaby normalnie uznana za zero wiodące. Wszystkie zera w liczbie całkowitej przetwarzane po znaku 9 mają być traktowane jako zera nie-wiodące (czyli wyświetlane normalnie jako 0, gdy w masce wystąpi znak Z).
  3. Znaki "," i "." mają być zastąpione przez spację, jeśli jedynie przetwarzane były dotychczas zera wiodące; w przeciwnym razie mają pojawić się na wyjściu na tej samej pozycji co w masce.
  4. Znak "-", jeśli będzie obecny, musi pojawić się na końcu maski i powinien być zastąpiony spacją dla liczb dodatnich, a dla liczb ujemnych powinien pojawić się na końcu liczby.

W ten sposób ma być przetworzony każdy wiersz wejściowy z danymi. Na wyjściu ma być wypisana odczytana liczba, maska oraz liczba po edycji. Całość ma przyjąć formę tabeli z odpowiednim nagłówkiem.

Przykładowe dane wejściowe

 0234567 ZZZ,ZZ9.99
-1234567 Z,999.999-
     123 ZZ,Z99.99
 1234567 Z,999,999-
 1234567 Z,999

Przykładowe dane wyjściowe

  NUMBER      MASK     EDITED VALUE
 0234567  ZZZ,ZZ9.99      2,345.67
-1234567  Z,999.999-    1,234.567-
     123  ZZ,Z99.99          01.23
 1234567  Z,999,999-    1,234,567
 1234567  Z,999             4,567
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.