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

1983

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Pułapka na myszy

Opis

Pułapka na myszy jest rodzajem gry w karty, w którą gra się następująco. Talia kart oznaczonych liczbami 1, 2, 3, ..., n jest rozkładana w dowolnej kolejności, karty są odkryte i ułożone w koło. Gracz rozpoczyna od pierwszej karty i liczy w koło zgodnie z kierunkiem rozkładania kart. Jeśli k-ta karta posiada numer k - takie zdarzenie nazywamy trafieniem (ang. hit) - to zostaje ona usunięta z koła i gracz znów rozpoczyna liczenie od 1.

Na przykład, jeśli talia składa się jedynie z 4 wykorzystywanych kart, a karty te zostaną rozłożone w kolejności 3214, to jako trafienie gracz otrzyma drugą kartę 2, następnie otrzymałby jako trafienie kartę 1, lecz gdyby poszedł dalej w nieskończoność, to nie uzyskałby kolejnego trafienia. Z drugiej strony, jeśli karty w talii byłyby w początkowym ułożeniu 1423, to gracz zebrałby wszystkie karty w kolejności 1, 2, 3, 4.

Załóż, że będziesz grał z talią 9 kart. Masz napisać program, który określi trafienia uzyskane przy określonym ułożeniu kart.

Specyfikacja wejścia

Na wejściu program otrzyma nieokreśloną liczbę wierszy, z których każdy będzie definiował uporządkowanie kart. Numery kolejnych kart w talii będą rozdzielone pojedynczą spacją. Pierwszy numer będzie określał numer na pierwszej karcie, drugi na drugiej, itd. Razem będzie 9 takich numerów. Wiersz z numerem 0 kończy dane wejściowe.

Specyfikacja wyjścia

Dla każdego wiersza z danymi program powinien wypisać te dane, a następnie listę wszystkich uzyskanych trafień. Trafienia można wypisywać w dowolnym dogodnym formacie.

Przykładowe dane wejściowe

1 3 5 7 9 2 4 6 8
9 7 3 1 2 4 5 6 8
0

Przykładowe dane wyjściowe

INPUT  1 3 5 7 9 2 4 6 8

     HIT 1
     HIT 8

INPUT  9 7 3 1 2 4 5 6 8

     HIT 3
     HIT 1
     HIT 7
Na początek:  podrozdziału   strony 

Problem B - Drzewo rozpinające

Opis

Graf (ang. graph) G jest zbiorem wierzchołków (ang. vertices) V oraz zbiorem krawędzi (ang. edges) E. Krawędź jest połączeniem pomiędzy dwoma (niekoniecznie różnymi) wierzchołkami. Spójny graf (ang. connected graph)  jest grafem, w którym można po krawędziach przejść z każdego wierzchołka do każdego innego. Drzewo rozpinające (ang. spanning tree) T dla spójnego grafu G jest grafem, który posiada taki sam zbiór wierzchołków V i którego zbiór krawędzi E' jest podzbiorem (niekoniecznie właściwym) zbioru krawędzi E. Co więcej, T musi być grafem spójnym bez cykli, tj. pomiędzy dwoma dowolnymi wierzchołkami istnieje tylko jedna ścieżka przejścia po krawędziach. W ten sposób E' jest minimalnym podzbiorem E, takim iż T jest grafem spójnym. Drzewo rozpinające niekoniecznie jest unikalne.

Jako przykład, poniższy graf zawiera cztery węzły (1-4) i pięć krawędzi (A-E):

obrazek

Dla tego grafu są możliwe trzy drzewa rozpinające:

obrazek   obrazek   obrazek

Masz napisać program, który wygeneruje drzewa rozpinające z grafów. Grafy będą się składały z co najwyżej 15 wierzchołków. Twój program powinien przetworzyć dowolną liczbę grafów wejściowych i dla każdego z nich wyświetlić krawędzie jednego z drzew rozpinających.

Specyfikacja wejścia

Dane wejściowe dla twojego programu będą się pojawiały w zestawach. Pierwszy wiersz zestawu zawiera liczbę n  - ilość wierzchołków grafu G. Następnie pojawi się n  wierszy, z których każdy reprezentuje jeden wierzchołek grafu oraz jego połączenia. Pierwszy z tych wierszy odnosi się do wierzchołka 1, drugi do wierzchołka 2, itd. Wiersz reprezentujący wierzchołek będzie zawierał n  liczb określających krawędzie (połączenia) pomiędzy tym wierzchołkiem a pozostałymi wierzchołkami grafu. Liczby w wierszu odnoszą się do kolejnych wierzchołków grafu. Wartość 0 oznacza brak krawędzi, a 1 istnienie krawędzi pomiędzy wierzchołkiem określonym przez wiersz a wierzchołkiem określonym przez liczbę w wierszu. Na przykład, dla wiersza reprezentującego wierzchołek k  pierwsza liczba 0 lub 1 określa, czy istnieje krawędź od wierzchołka k  do wierzchołka 1, druga liczba określa istnienie krawędzi od wierzchołka k  do wierzchołka 2, i-ta liczba w tym wierszu określa istnienie krawędzi od wierzchołka k  do wierzchołka i. Dane wejściowe kończą się, jeśli pierwszy wiersz zawiera wartość 0.

Specyfikacja wyjścia

Dla każdego zestawu danych reprezentującego graf należy wyświetlić listę par wierzchołków (po jednej parze na wiersz wydruku) określających krawędzie drzewa rozpinającego dla tego grafu. Na tej liście każda krawędź powinna być umieszczona dokładnie jeden raz.

Przykładowe dane wejściowe

4
0 1 0 1
1 0 1 1
0 1 1 1
0 1 1 0
0

Przykładowe dane wyjściowe

THE CONNECTIONS ARE

1 - 2
2 - 3
2 - 4
Na początek:  podrozdziału   strony 

Problem C - Manipulowanie tablicą

Opis zadania nr 1

Ten problem jest ćwiczeniem przekształcania jednowymiarowej listy liczb w dwuwymiarową tablicę ze zmienną liczbą kolumn. Liczby muszą być ułożone w tablicę, którą czyta się kolumnami od strony lewej do prawej. Długości kolumn powinny być wyrównane tak, aby wszystkie wiersze z wyjątkiem ostatniego były pełne. Puste miejsca w ostatnim wierszu powinny być umieszczone po jego prawej stronie.

Specyfikacja wejścia

Na wejściu program otrzyma liczbę n  określającą ilość liczb na liście, następnie n  liczb listy i na końcu liczbę c  określającą liczbę kolumn w tworzonej tablicy.

Specyfikacja wyjścia

Na wyjściu program powinien wypisać w c  kolumnach odczytaną z wejścia listę liczb.

Przykładowe dane wejściowe

17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
5

Przykładowe dane wyjściowe

   1   5   9  12  15
   2   6  10  13  16
   3   7  11  14  17
   4   8

Opis zadania nr 2

Napisz program, który dla tablicy dwuwymiarowej opisanej powyżej wyliczy sumy wyrazów w poszczególnych wierszach.

Specyfikacja wejścia

Dane dla programu będą się składały z ciągu zestawów. Ciąg ten kończy się, gdy pierwsza liczba w zestawie ma wartość 0. Dla każdego zestawu znaczenie danych jest następujące:

Pierwsza liczba n  określa ilość liczb w liście do zamiany w tablicę. Następnie występuje n  liczb listy. Na końcu pojawia się liczba c, która określa ilość kolumn tablicy do utworzenia.

Specyfikacja wyjścia

Na wyjściu dla każdego zestawu danych należy wypisać wartość C oraz kolejne sumy wierszy tablicy. Samej tablicy nie wypisujemy.

Przykładowe dane wejściowe

17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 5
17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1
17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2
0

Przykładowe dane wyjściowe

 C   ROW SUMS
 5   42 47 52 12
 1   153
 2   11 13 15 17 19 21 23 25 9
Na początek:  podrozdziału   strony 

Problem D - Figury wpisane

Opis

Rozważmy następujące układy figur geometrycznych:

a)
obrazek
kształt = CIR
  b)
obrazek
kształt = SQR

Napisz program, który będzie przetwarzał wiersze zawierające następujące dane:

n - długość boku kwadratu
r - promień 4 okręgów, które są umieszczone w rogach kwadratu i stykają się z dwoma jego bokami (zobacz na rysunki powyżej)
kształt  - CIR oznacza okrąg (ang. circle), SQR oznacza kwadrat (ang. square).

Na podstawie kształtu twój program powinien wyliczyć powierzchnię największego wpisanego kwadratu (o bokach równoległych do boków kwadratu opisującego) lub koła, które leżą w całości wewnątrz dużego kwadratu i stykają się w co najwyżej 4 punktach z czterema okręgami.

Specyfikacja wejścia

Dane wejściowe będą zawarte w wierszach. Pierwsza liczba całkowita n  określa długość boku dużego kwadratu (0 < n ≤ 100). Druga liczba rzeczywista r z dwoma miejscami po przecinku określa promień każdego z czterech wewnętrznych okręgów. Na końcu wystąpi 3 literowy tekst CIR lub SQR, który będzie określał rodzaj figury wpisanej.

Koniec danych wejściowych będzie oznaczony wartością n  = 0.

Specyfikacja wyjścia

Dla każdego wiersza z danymi program powinien wypisać odpowiednio oznaczone wartości dla n, r, kształtu oraz powierzchnię figury wpisanej z dokładnością do 0.1.

Na początek:  podrozdziału   strony 

Problem E - Słownik danych

Opis

Jednym z ważnych składników wielu współczesnych systemów informacyjnych jest słownik danych (ang. data dictionary), który definiuje własności elementów danych w rekordach danych.  Problem ten wymaga użycia prostego słownika danych (listy elementów danych oraz ich postaci) w celu sprawdzenia poprawności zawartości transakcji wejściowych i do utworzenia raportu błędów.

Specyfikacja wejścia

Plik wejściowy o nazwie in.txt zawiera dwa zbiory danych zbudowane z wierszy. Pierwszy zbiór zawiera nie więcej niż 15 wierszy i kończy się wierszem, który w pierwszych dwóch znakach posiada 00. Wiersze te będą ułożone w porządku rosnącym względem pozycji startowej (patrz niżej). Każdy wiersz w tym zbiorze będzie się składał z 80 znaków i będzie opisywał jeden element danych w sposób następujący (pierwszy znak w wierszu jest w kolumnie 1):

Kolumny Zawartość
1-2 Pozycja startowa p  w wierszu operacji (0 < p  ≤ 80), liczba całkowita
4-5 Długość pola f  (1 ≤ f  ≤ 80), liczba całkowita
7 Rodzaj pola:
    = 1 liczbowe (zawiera cyfry, znaki +/-, kropki dziesiętne lub spacje)
    = 2 alfanumeryczne (zawiera dowolne znaki)
    = 3 data w postaci MMDDYY (to pole musi zawierać dokładnie 6 cyfr, lecz może posiadać spacje w dowolnym miejscu.
          Również: 1 ≤ MM ≤ 12 i 1 ≤ DD ≤ 31)
.
9 Obecność:
    = 1 pole wymagane (nie może być puste)
    = 2 pole opcjonalne
11-30 Nazwa elementu danych (używana tylko do wydruku)
31-80 Nieużywane

Możesz założyć poprawność i spójność wszystkich danych słownikowych. Twój program nie jest odpowiedzialny za sprawdzanie znaków w polach nie określonych w słowniku danych.

Drugi zbiór danych zawiera transakcje do sprawdzenia za pomocą reguł słownika dostarczonych w pierwszym zbiorze. Format wierszy zależy  od definicji w słowniku. Jednakże wiadomo, że każdy wiersz będzie posiadał długość 80 znaków. Koniec pliku zasygnalizuje koniec drugiego zbioru danych.

Specyfikacja wyjścia

Raport na temat nieprawidłowych wierszy z danymi powinien być utworzony w następującym formacie:

ERRONEOUS TRANSACTIONS         (BŁĘDNE TRANSAKCJE)
XXX................XXX
    message 1
    message 2
    ...
    ...
    ...
XXX................XXX
    message 1
    message 2
    ...
    ...
    ...

Gdzie XXX...XXX oznacza błędną transakcję ze zbioru wejściowego, a message i  składa się z nazwy składnika danych ze słownika, za którą następuje krótkie wyjaśnienie natury błędu w języku angielskim. Typowe wiadomości błędów są następujące:

SSNO      IS MISSING                    (BRAKUJE)
SALARY    IS NOT NUMERIC                (NIE JEST LICZBĄ)
BIRTHDAY  HAS MONTH > 12                (MA MONTH > 12)
NETPAY    CONTAINS AN EMBEDDED BLANK    (ZAWIERA OSADZONĄ SPACJĘ)

Uwaga: dla pól liczbowych liczby muszą być poprawnie zapisane, lecz nie muszą być wyrównane do prawej krawędzi pola. Dla dat przyjmij, że wszystkie miesiące mają po 31 dni.

Na początek:  podrozdziału   strony 

Problem F - Domki z pni

Opis

Firma HYPOXIA Properties, Ltd. zajmuje się sprzedażą domków z pni. Cena ich usług zależy od powierzchni w stopach zamawianego modelu oraz od tego, czy pracę wykonuje firma sama HYPOXIA, czy właściciel w swoim zakresie. Chociaż ich konstrukcje domków z pni oraz zestawy do samodzielnego montażu są bardzo dobre, HYPOXIA ma pewne trudności w wyliczaniu powierzchni, ponieważ podłogi posiadają różne kształty i rozmiary.

Założyciel firmy, John Hardwood, pragnie posiadać program komputerowy, który by wspomagał te obliczenia. Kosztorysant firmy chciałby móc wprowadzać dane opisujące wymiary domku, średnice pni i ich długości, liczbę pożądanych pięter, itp., a otrzymywać w wyniku powierzchnię domku w stopach kwadratowych (zaokrągloną do najbliższej stopy kwadratowej) oraz koszt domku (w dolarach).

Plany podłóg są kodowane przez podanie, począwszy od dowolnego narożnika, listy kolejnych par (kierunek, długość), które definiują parametry domku, gdzie kierunkiem jest zawsze N, S, E lub W, a wymiary są podawane w całych stopach. Na przykład dla domku o następujących wymiarach:

obrazek

kodowanie mogłoby być następujące: (N,20), (E,10), (N,10), (E,10), (S,10), (E,15), (S,15), (W,10), (S,5), (W,25).

Koszty domków z pni są obliczane zgodnie z następującymi regułami:

  1. "Główna opłata" za domek z pni (przy użyciu pni o średnicy 6") wynosi 20 dolarów za stopę kwadratową. Jeśli HYPOXIA dostarcza zarówno zestaw jak i siłę roboczą, pobierana jest opłata 35 dolarów za stopę kwadratową (znów dla 6" pni).
  2. Pnie o średnicy 8" są dostępne za dodatkowe 10% opisanej powyżej opłaty głównej.
  3. Pierwsze piętro (strych) jest dostępne za dodatkowe 15% opłaty wyliczonej w powyższych punktach 1 lub 2.
  4. Standardowa cena dotyczy domku z pni o długości 8 stóp. Klient może określić długości pni równe 10 stóp lub więcej za dodatkowe 5%.

Specyfikacja wejścia

Na wejściu programu może pojawić się dowolna liczba opisów domków z pni. Każdy opis takiego domku wymaga następujących danych:

długości i średnicy pni:
    T6, T8 - pnie o długości 8 stóp i średnicach 6 lub 8 cali
    F6, F8 - pnie o długości 10 stóp i średnicach 6 lub 8 cali

liczby pięter: 1 lub 2 (pamiętaj, że w systemie anglosaskim dom dwupiętrowy, to nasz jednopiętrowy, ponieważ parter jest tam liczony jako pierwsze piętro!)

kto będzie budował:  T - HYPOXIA,  F - klient we własnym zakresie

liczby narożników n  (n  ≤ 18)

n par: kierunek N, S, E lub W i odległość

Ciąg opisów kończy się, jeśli pierwszą daną jest 00.

Specyfikacja wyjścia

Dla każdego opisu domku odczytanego z wejścia program powinien wypisać powierzchnię opisanego planu podłogi oraz wyliczony koszt usługi (zaokrąglony do najbliższego dolara).

Na początek:  podrozdziału   strony 

Problem G - Binarne drzewa gry

Opis

Binarne drzewo gry (ang. binary game tree) jest drzewem binarnym, w którym każdy węzeł posiada albo 0, albo 2 potomków. Każdy liść drzewa (węzeł bez potomków) ma skojarzone ze sobą dane. Dwóch potomków dowolnego węzła wewnętrznego reprezentuje wynik wykonania lub niewykonania określonego ruchu, a wartość w liściu drzewa jest miarą przydatności w zwycięstwie ruchów wzdłuż ścieżki prowadzącej od korzenia do tego liścia. Drzewo przedstawia ruchy dla dwóch graczy; korzeń oraz wszystkie węzły o parzystej odległości od korzenia (odległość wyrażana jest na drzewie liczbą krawędzi, po których należy przejść, aby dojść od korzenia do wybranego węzła) są ruchami do wyboru przez gracza A, natomiast węzły o odległości nieparzystej od korzenia są ruchami dla gracza B. Poniżej przedstawiono przykład:

obrazek

Gracz A stara się zmaksymalizować wartość wybranych ruchów, natomiast gracz B stara się zminimalizować korzyści gracza A przez wybieranie ścieżki o niższej wartości.  W dowolnym węźle reprezentującym wybór dla A gracz A wybierze wartość wyższą, a w dowolnym węźle reprezentującym wybór dla B gracz B wybierze wartość niższą. W ten sposób wartością drzewa wewnętrznego jest albo wartość maksymalna, albo minimalna jego poddrzew w zależności o tego, czy pierwotne poddrzewo jest odpowiednio dla gracza A lub B.

Dla przykładowego drzewa gry mamy:

obrazek

Danymi wejściowymi dla twojego programu będą opisy kilku binarnych drzew gry. Masz określić wartość (dla A) każdego drzewa Na wyjściu ma się pojawić jedynie wartość drzewa, nie musisz drukować drzewa w całości. Drzewo będzie posiadało co najwyżej 15 węzłów.

Specyfikacja wejścia

Dane dla tego problemu są ułożone w zestawach w pliku in.txt. Każdy zestaw może zawierać od jednego do 15 wierszy z danymi; pierwszy wiersz opisuje korzeń drzewa (węzeł numer 1), a każdy kolejny wiersz opisuje następny węzeł o wyższym numerze. Każdy wiersz będzie zawierał trzy liczby:

n - numer węzła dla lewego potomka (1 ≤ n 20)
m - numer węzła dla prawego potomka (1 ≤ m 20)
Powyższe dwie liczby przyjmują wartość 0, jeśli węzeł jest liściem
v - wartość liścia (-99 ≤ v ≤ 99) lub zero, jeśli węzeł nie jest liściem.

Każdy zestaw kończy się wierszem, w którym lewy potomek ma numer -1, a pozostałe dwie wartości przyjmują 0.

Dane wejściowe kończą się wraz z plikiem.

Specyfikacja wyjścia

Dla każdego zestawu danych należy podać wartość drzewa.

Przykładowe dane wejściowe

  2   3   0
  4   5   0
  6   7   0
  0   0   6
  0   0   3
  0   0   0        (Zauważ, że węzeł nr 6 nie jest używany)
  0   0  -5
  0   0  -2
  0   0   1
  0   0   0        (Węzeł nr 10 też nie jest używany)
  8   9   0
 -1   0   0        (Koniec zestawu)

Przykładowe dane wyjściowe

3
Na początek:  podrozdziału   strony 

Problem H - Mnożenie wielomianów

Opis

Wielomian P(x) = a0x0 + a1x1 + a2x2 + ... + anxn może być przedstawiony jako zbiór uporządkowanych par, w których pierwszy element pary jest współczynnikiem, a drugi element jest wykładnikiem zmiennej x.

Na przykład wielomian P(x) = 7 + 3x2 + 4x9 + 17x21 reprezentuje zbór par (7,0), (3,2), (4,9), (17,21).

Masz napisać program, który wczyta nieokreśloną liczbę par definicji wielomianów - każda para definiuje dwa wielomiany. Następnie dla każdej pary wejściowych wielomianów program powinien wyprowadzić na wyjście uporządkowane wg wykładników pary współczynnik, wykładnik, które odnoszą się do iloczynu wczytanych wielomianów (wielomiany wejściowe są podobnie zapisane).

Specyfikacja wejścia

Dane występują w parach. W każdej parze są zdefiniowane dwa wielomiany. Definicja wielomianu rozpoczyna się od liczby określającej ilość par współczynnik, wykładnik - pary te będą uporządkowane wg rosnących wykładników. Wszystkie współczynniki i wykładniki są nieujemnymi liczbami całkowitymi o wartości mniejszej od 100. Każdy wielomian wejściowy nie będzie zawierał więcej niż 9 składników.

Dane wejściowe kończą, jeśli liczba par jest równa zero.

Specyfikacja wyjścia

Dla każdej wczytanej z wejścia pary wielomianów należy obliczyć wielomian będący ich iloczynem i wyprowadzić na wyjście pary współczynnik, wykładnik tego wielomianu. Pary te powinny być odpowiednio opisane i wyprowadzone w porządku rosnących wykładników.

Przykładowe dane wejściowe

3  3  0 16  3 23  5        (wielomian: P(x) = 3 + 16x3 + 23x5)
2  2  2 10  5             
(wielomian: P(x) = 2x2 + 10x5)

Przykładowe dane wyjściowe

COEFF     EXP
    6       2
   62       5
   46       7
  160       8
  230      10

(wielomian wynikowy: P(x) = 6x2 + 62x5 + 46x7 + 160x8 + 230x10)

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.