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

1987

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Słownik anagramów

Anagramem pewnego słowa jest inne słowo stworzone z tych samych liter, które tworzą słowo oryginalne. Na przykład słowo BRAINY jest anagramem słowa BINARY.

Słownik anagramów pokazujący wszystkie słowa. które można skonstruować przy użyciu danego zbioru liter, jest przydatny przy pewnego rodzaju łamigłówkach słownych i grach. Każda pozycja w takim słowniku zawiera klucz dający zbiór liter ułożonych w kolejności alfabetycznej oraz jedno lub więcej słów, które można utworzyć przy użyciu liter znajdujących się w kluczu. Pozycja słownika anagramów dla klucza ABINRY może wyglądać tak:

ABINRY      : BRAINY       BINARY

W tym zadaniu masz utworzyć słownik anagramów zawierający dany zbiór słów. Słowa będą się pojawiały po jednym na wiersz w danych wejściowych, poczynając od pierwszej kolumny. W danych wejściowych słowa nie będą się powtarzały, a każde słowo będzie zawierało do 12 dużych liter alfabetu. W danych wejściowych nie będzie więcej niż 1000 słów, a z każdego klucza da się utworzyć nie więcej niż 20 anagramów.

Twój program musi utworzyć słownik anagramów tak, aby same klucze były w kolejności alfabetycznej. Każdy wiersz każdej pozycji w słowniku będzie zawierał pięć anagramów z wyjątkiem ostatniego wiersza, który może zawierać mniej niż pięć anagramów. Anagramy w każdej pozycji nie muszą występować w żadnej szczególnej kolejności. Pierwszy wiersz każdej pozycji będzie rozpoczynał się od klucza, wyrównanego lewostronnie w 12-znakowym polu, po którym następuje dwukropek. Każdy dodatkowy wiersz każdej pozycji będzie rozpoczynał się od 13 spacji. Pięć lub mniej anagramów w każdym wierszu jest wyświetlane z wyrównaniem lewostronnym w 12-znakowych polach rozpoczynających się w kolumnie 14, po każdym polu następuje spacja.

Przykładowo, jeśli dane wejściowe zawierają słowa:

CRAPES
INTEGRAL
RELATING
ESCARP
PACERS
ALTERING
SYZYGY
ALGORITHM
CAPERS
TRIANGLE
MARTLESSNESS
SCARPE
LOGARITHM
BINARY
SPACER
TRAMLESSNESS
ALERTING
STY
BRAINY
RECAPS

to odpowiadający mu słownik anagramów, który twój program mógłby utworzyć, wyglądałby następująco:

ABINRY      : BRAINY       BINARY
ACEPRS      : RECAPS       SPACER       SCRAPE       CAPERS       PACERS
              ESCARP       CRAPES
AEELMNRSSSST: TRAMLESSNESS MARTLESSNESS
AEGILNRT    : ALERTING     TRIANGLE     ALTERING     RELATING     INTEGRAL
AGHILMORT   : LOGARITHM    ALGORITHM
GSYYYZ      : SYZYGY
STY         : STY
Na początek:  podrozdziału   strony 

Problem B - Szachy

Masz napisać program, który określi, czy zbiór figur szachowych atakuje daną pozycję na szachownicy. (Nie musisz umieć grać w szachy, aby rozwiązać ten problem, ponieważ potrzebne ci informacje o szachach podano poniżej.) Program ma wczytać pozycję trzech figur szachowych: skoczka, gońca i króla; określić figury atakujące zbiór pól szachownicy, jeśli takie są; wyświetlić wyniki; i wrócić w pętli, aby powtórzyć ten proces. Procedura ma się zakończyć po wczytaniu określonej konfiguracji szachownicy.

Do rozwiązania tego problemu wystarczająca jest następująca informacja o grze w szachy:

Szachy są rozgrywane na kwadratowej planszy złożonej z ośmiu wierszy i ośmiu kolumn (tj. siatki 8 na 8). Pozycje na szachownicy są opisane uporządkowaną parą liczb (r,c), gdzie 1 ≤ r ≤ 8 i 1 ≤ c ≤ 8 to odpowiednio wiersz (ang. r = row) i kolumna (ang. c = column) danej pozycji.

Figury szachowe (bierki) mogą poruszać się z danej pozycji do nowej pozycji w sposób zależny od ich typu i zgodnie z następującymi regułami: (i) żadnej figurze nie wolno zejść z szachownicy i (ii) figurze nie wolno przejść na pole zajęte przez inną figurę (nie musisz zaprzątać sobie głowy wyjątkiem od tej reguły stosowanym przy zbiciu figury przeciwnika).

Skoczek może poruszać się z danej pozycji (i,j) na szachownicy na dowolną z ośmiu innych pozycji (bez łamania ograniczeń podanych wyżej). Możliwe nowe pozycje mogą znajdować się o dwa wiersz wyżej lub niżej i o jedną kolumnę na prawo lub na lewo od pozycji początkowej (cztery kombinacje) albo o dwie kolumny na prawo/lewo i o jeden wiersz wyżej/niżej od pozycji początkowej (cztery dalsze kombinacje). W ten sposób, jeśli skoczek jest początkowo na pozycji (4,4), to może się przesunąć na pozycje (2,3), (2,5), (6,3), (6,5), (3,2), (5,2), (3,6) i (5,6) zakładając, iż żadna z tych pozycji nie jest już zajęta.

Goniec może poruszać się z pozycji szachownicy (i,j) do dowolnej z pozycji przekątnych (i±k,j±k) z dodatkowym zastrzeżeniem, iż nie może "przeskakiwać ponad" żadnymi innymi figurami, które mogły się znaleźć wzdłuż tej przekątnej. Stąd jeśli goniec jest początkowo na pozycji (3,2), to może przesunąć się na pozycje (2,1), (4,3), (5,4), (6,5), (7,6), (8,7), (2,3), (1,4) lub (4,1) przy założeniu, iż wzdłuż tych przekątnych nie ma innych figur. Jeśli na pozycji (6,5) znajdowałaby się inna figura, to ruchy na pozycje (6,5), (7,6) i (8,7) nie byłyby dozwolone.

Król może poruszać się z danej pozycji (i,j) na szachownicy do dowolnej z 8 pozycji bezpośrednio przyległych, o ile są one niezajęte. W ten sposób, jeśli król jest początkowo na pozycji (4,4), to może przesunąć się na pozycje (3,3), (3,4), (3,5), (4,3), (4,5), (5,3), (5,4) lub (5,5).

Figura na pozycji (i,j) "atakuje" inną pozycję (r,c), jeśli może ona przejść z (i,j) na (r,c). (Dana pozycja może być jednocześnie atakowana przez wiele figur.) "Konfiguracja" jest danym zestawem figur szachowych i ich pozycji na szachownicy.

Twój program powinien wczytać konfigurację wraz ze zbiorem pozycji na szachownicy do sprawdzenia i wydrukować wiadomość wskazującą, które figury konfiguracji, jeśli takie są, atakują każdą z pozycji szachownicy do sprawdzenia. Ten proces jest powtarzany dla wielokrotnych zestawów konfiguracji.

Konfiguracja reprezentowana jest przez zbiór sześciu liczb całkowitych z zakresu od zera do ośmiu, które znajdują się w pojedynczym wierszu wejściowym i są oddzielone jedną lub kilkoma spacjami (w danych nie będzie pustych wierszy). Pierwsza para liczb całkowitych reprezentuje wiersz i kolumnę pozycji skoczka, druga reprezentuje wiersz i kolumnę pozycji gońca, a trzecia para liczb całkowitych reprezentuje wiersz i kolumnę pozycji króla. Wartości zerowe będą użyte tylko do "pustej" konfiguracji strażniczej, oznaczającej koniec danych wejściowych (tj. twój program powinien się zakończyć po odczytaniu konfiguracji złożonej z sześciu wartości zero).

Każda pozycja, która ma być sprawdzona dla danej konfiguracji jest reprezentowana przez zbiór dwóch liczb całkowitych z zakresu od zera do osiem. Każda pozycja wystąpi w oddzielnym wierszu z jedna lub więcej spacjami pomiędzy tymi liczbami całkowitymi (nie będzie pustych wierszy w danych). Każda para liczb całkowitych reprezentuje wiersz i kolumnę pozycji do sprawdzenia. Wartości zerowe pojawią się jedynie w "pustej" pozycji strażniczej, która oznacza brak dalszych pozycji do sprawdzenia dla bieżącej konfiguracji (tj. gdy zostanie wczytana pozycja zero zero, to za nią nastąpi nowa konfiguracja).

Dla kazdej pozycji do sprawdzenia, twój program powinien wydrukować oddzielny wiersz o następującym formacie:

N:a,b   B:c,d   K:e,f - g,h UNDER ATTACK BY xyz

gdzie "a" i "b" są wierszem i kolumną skoczka (ang. kNight), "c" i "d" są wierszem i kolumną gońca (ang. Bishop), "e" i "f" są wierszem i kolumną króla (ang. King); "g" i "h" są wierszem i kolumną sprawdzanej pozycji (numery wierszy i kolumn są jednocyfrowymi liczbami); a "xyz" są jedną z ośmiu możliwych wartości "NOTHING" , "N", "B", "K", "NB", "NK", "BK" lub "NBK" odpowiadającej atakowaniu pozycji (g,h) odpowiednio przez żadną z figur (NOTHING), tylko przez skoczka (N), tylko przez gońca (B), tylko przez króla (K), przez skoczka i gońca (NB), przez skoczka i króla (NK), przez gońca i króla (BK) lub razem przez skoczka, gońca i króla (NBK). Informacja ta powinna zostać wyprowadzona w tej samej kolejności, w jakiej została wprowadzona, tj. informacja o pierwszej pozycji dla pierwszej konfiguracji, informacja o drugiej pozycji dla pierwszej konfiguracji, ..., informacja o ostatniej pozycji dla ostatniej konfiguracji. Żadna informacja nie powinna być wyprowadzana dla pustych pozycji strażniczych lub konfiguracji strażniczych. Dla przykładu załóżmy następujące dane wejściowe:

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

Wtedy na wyjściu powinno pojawić się:

N:1,1   B:2,2   K:3,3 - 3,2 UNDER ATTACK BY NK
N:1,1   B:2,2   K:3,3 - 7,7 UNDER ATTACK BY NOTHING
N:5,6   B:4,4   K:2,5 - 3,5 UNDER ATTACK BY NBK
Na początek:  podrozdziału   strony 

Problem C - Przecinanie się odcinków

Termin angielski splay oznacza zbiór rozrzuconych odcinków na płaszczyźnie kartezjańskiej. Masz napisać program, który wczyta ten zbiór i wyliczy liczbę par przecinających się odcinków.

Przy znajdowaniu przecięć należy rozważyć cztery przypadki specjalne:

  1. Splay może zawierać identyczne odcinki, w którym to przypadku należy brać pod uwagę tylko jeden z identycznych odcinków przy wyszukiwaniu przecięć z innymi odcinkami. Dwa odcinki są identyczne, jeśli mają takie same punkty końcowe, chociaż nie muszą one być podane w tej samej kolejności w danych wejściowych.
  2. Dwa równoległe odcinki nie są uważane za przecinające się, nawet jeśli mają wspólny punkt końcowy lub wspólny krótszy odcinek.
  3. Odcinek o długości zero jest uważany za równoległy do wszystkich pozostałych odcinków, stąd nie może on przecinać żadnego innego.
  4. Dwa nierównoległe odcinki przecinają się, jeśli posiadają dokładnie jeden punkt wspólny (który może być końcem odcinka).

Zbiór danych dla tego problemu będzie się składał z kilku wierszy danych, a każdy z nich będzie zawierał współrzędne dwóch punktów końcowych jednego odcinka, w kolejności x1, y1, x2, y2. Każda współrzędna będzie liczbą całkowitą z zakresu od 0 do 50 (włącznie). Kolejne wartości będą rozdzielone przynajmniej jedną spacją. W splay będzie co najwyżej 50 odcinków.

Wyjście z twojego programu powinno zawierać dwie wartości, każda odpowiednio opisana. Pierwsza jest liczbą różnych (nieidentycznych) odcinków w splay, a druga jest liczbą par przecinających się odcinków w splay.

Na początek:  podrozdziału   strony 

Problem D - Szybkie i proste szyfrowanie wiadomości

Podczas niezaplanowanej i nieautoryzowanej misji dostarczania "towarów" do niezbyt przyjaznego kraju stało się niezbędne porozumiewanie za pomocą zaszyfrowanych wiadomości. Metoda szyfrowania ma być łatwa i szybka w implementacji (nie więcej niż 4 programistów, 1 komputer PC i mniej niż 6 godzin na ukończenie programu).

Wiersze wiadomości do zaszyfrowania będą zawarte w pliku. Każdy wiersz będzie miał długość nie większą niż 80 znaków, liczba wierszy do zaszyfrowania będzie nieokreślona. Koniec wiadomości będzie oznaczony przez koniec pliku.

Metoda szyfrowania będzie następująca:

Przykładowa wiadomość wejściowa:

This is
a message

Powinna wygenerować następujące dane na wyjściu:

BiissTa h
esmaeags
Na początek:  podrozdziału   strony 

Problem E - Nielegalne transmisje

Jesteś członkiem bardzo tajnej grupy dokonującej telemetrii sygnałów radiowych, której zadaniem jest badanie podejrzanych sygnałów radiowych nadawanych z grupy wysp w twoim regionie. Twoim zadaniem jest wytropienie źródeł tych nielegalnych transmisji.

Mapa, która reprezentuje te wyspy w twoim regionie jako wypukłe wieloboki w prostokątnym układzie współrzędnych całkowitych, jest przechowywana w pliku danych mapy. Ściśle tajny szperacz transmisji tworzy plik danych transmisji, który zawiera położenia źródeł nielegalnych transmisji.

Napisz program, który dla każdej transmisji w pliku danych transmisji zidentyfikuje nazwę wyspy, z której pochodzi transmisja lub, jeśli transmisja nie pochodzi z żadnej wyspy, zaraportuje, że pochodzi ona z morza. Twoje wyjście powinno wyglądać następująco:

Transmission #1 at site (20,17) is from the island "Pangea".
Transmission #2 at site (35,30) is from the island "Oil Platform".
Transmission #3 at site (0,0) originated at sea.

Opis danych wejściowych

Plik danych mapy składa się z listy wielowierszowych zbiorów danych reprezentujących część obszaru wyspy. Pierwszy wiersz takiego zbioru danych jest nazwą wyspy, na której znajduje się dany obszar, wyrównaną lewostronnie w pierwszych 20 kolumnach. Drugi wiersz zawiera liczbę wierzchołków wypukłego wieloboku, który definiuje granice obszaru, wyrównaną prawostronnie w pierwszych 5 kolumnach. Każdy z pozostałych wierszy zawiera współrzędne prostokątne jednego wierzchołka tego wieloboku ze współrzędnymi x i y wyrównanymi prawostronnie odpowiednio w kolumnach 1-5 i 7-11. Zakłada się, iż kolejne wierzchołki są połączone bokiem wieloboku, a ostatni i pierwszy wierzchołek są również połączone bokiem. Wyspa składa się z wnętrz i boków obszarów w pliku danych mapy posiadających nazwę tej wyspy. Żadne dwie wyspy nie stykają się ze sobą.

Plik danych transmisji jest ciągiem wierszy, z których każdy zawiera współrzędne źródła pojedynczej transmisji w prostokątnym układzie współrzędnych mapy ze współrzędnymi x i y wyrównanymi przwostronnie odpowiednio w kolumnach 1-5 i 7-11.

Dodatkowe kryterium oceniania:

Wszystkie współrzędne w testowych zbiorach danych posiadają wartości całkowite od 0 do 1000.

Na początek:  podrozdziału   strony 

Problem F - Rozkład liczb całkowitych

Znany jest fakt, iż każdą liczbę całkowitą n większą od 17 można zapisać jako sumę trzech różnych liczb całkowitych większych od jeden, które są parami względnie pierwsze, tzn. żadna para z tej trójki nie posiada wspólnego dzielnika pierwszego. Aby zilustrować ten fakt, napisz program odczytujący wartości n z kolejnych wierszy wejściowych i dla każdego n pokazujący rozkład n na sumę takich trzech liczb całkowitych a, b i c przez wypisanie wiersza o postaci:
n = a + b + c

Na przykład, jeśli n = 18, to na wyjściu może pojawić się:

18 = 4 + 9 + 5

Twój program powinien przetworzyć tyle wartości, ile znajduje się w pliku wejściowym. Przyjmij, iż każdy wiersz zawiera dokładnie jedną wartość wejściową z zakresu od 18 do 32.767 wyrównaną prawostronnie w kolumnach 1-5.

Twój program może wyprowadzać dowolny poprawny rozkład. Co więcej, kolejność czynników dodawania jest nieistotna. Jeden z poniższych wierszy jest również akceptowalny dla n = 18:

18 = 9 + 5 + 4
18 = 2 + 3 + 13
Na początek:  podrozdziału   strony 

Problem G - Drabinki słowne

Mając dane dwa słowa o tej samej liczbie liter, drabinka słowna jest ciągiem słów zmieniającym pierwsze słowo w drugie przez zmianę za każdym razem tylko jednej litery. Zatem, aby zmienić COLD w WARM, moglibyśmy zbudować poniższą drabinkę słowną:
C O L D
C O R D
C A R D
W A R D
W A R M

Dla tego zadania musisz napisać program, który wczyta "słownik" czteroliterowych słów, a następnie zbuduje drabinki słowne (lub zgłosi, że żadna nie istnieje) dla określonych par słów.

Pierwsza część danych wejściowych będzie zawierała dowolną liczbę wierszy (maksymalnie 100) każdy zawierający czteroliterowe słowo pisane dużymi literami w pierwszych czterech kolumnach wiersza. Następnie pojawi się wiersz kończący słownik, który będzie zawierał znak dolara ($) w pierwszej kolumnie.

Druga część danych wejściowych będzie złożona z kilku wierszy, z których każdy będzie zawierał dwa czteroliterowe słowo. Pierwsze słowo będzie w pierwszych czterech pozycjach znakowych wiersza, następnie będzie dokładnie jedna spacja, a następnie drugie czteroliterowe słowo na następnych czterech pozycjach znakowych. Ta część danych wejściowych kończy się z końcem pliku.

Twój program powinien najpierw wydrukować te dwa słowa. Jeśli drabinka istnieje przy użyciu tylko słów ze słownika, wydrukuj ją w formacie pionowym pokazanym powyżej. W przeciwnym razie wydrukuj wiadomość NO LADDER EXISTS.

Dla niektórych par słów może istnieć więcej niż jedna drabinka. Akceptowana jest dowolna poprawna drabinka.

Na początek:  podrozdziału   strony 

Problem H - Rurociągi z rafinerii

Pewna rafineria posiada trzy duże rurociągi przebiegające pomiędzy dwoma budynkami. Rurociągi i ściany tych budynków są wszystkie równoległe. Poniższy rysunek pokazuje ściany i rurociągi w widoku od końca, dlatego rurociągi pojawiają się na nim jako koła.

Rafineria chce dodać czwarty rurociąg w przestrzeni pomiędzy pozostałymi rurociągami, jak pokazano na rysunku w postaci koła z przerywaną linią. Twój program musi określić promień i położenie największego rurociągu, który można tam umieścić tak, aby stykał się z istniejącymi rurociągami biegnącymi równolegle. Ani ściany, ani okapy, ani ziemia, ani ciemność nocy nie powinny ograniczać rozwiązania tego problemu.

Dane dla twojego programu będą opisywały bieżące ułożenie rurociągów. Dla każdego rurociągu jeden wiersz danych poda współrzędne x i y środka rurociągu oraz jego promień jako trzy liczby rzeczywiste (w postaci: część całkowita, kropka dziesiętna i część ułamkowa) rozdzielone przynajmniej jedną spacją. Stąd będą trzy wiersze danych. Wszystkie wartości są podane w centymetrach. Początek układu współrzędnych jest umieszczony tak, jak pokazano na rysunku: na ziemi (oś x) i przy lewej ścianie (oś y).

Twoje odpowiedzi powinny być również w centymetrach i powinny pokazywać promień nowego rurociągu oraz współrzędne jego środka z odpowiednimi opisami. Odpowiedzi powinny mieć dokładność do jednego milimetra.

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.