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

1984

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Rozbiór addytywny

Opis

Masz odczytać ciąg wierszy, z których każdy będzie zawierał dwie liczby całkowite; nazwijmy je "suma" i "składniki". Liczby będą oddzielone od siebie przynajmniej jedną spacją. Dla każdej pary "suma" i "czynniki" masz wypisać wiersz zawierający wartości "sumy" i "czynników" oraz liczbę wszystkich różnych kombinacji, w których "suma" może być przedstawiona jako suma dodatnich liczb całkowitych, których ilość określa drugi składnik "czynniki".

Na przykład sześć można przedstawić jako sumę jednej liczby dodatniej tylko na jeden sposób, mianowicie 6; sześć można przedstawić jako sumę dwóch dodatnich liczb całkowitych na trzy różne sposoby: 5+1, 4+2 i 3+3. (Zwróć uwagę, że 2+4 nie różni się w istotny sposób od 4+2.)  Dla tego przykładu twój program powinien wypisać na wyjściu mniej więcej taki wiersz:

 6 MAY BE REPRESENTED AS THE SUM OF 2 INTEGERS IN 3 WAYS
(6 MOŻNA PRZEDSTAWIĆ JAKO SUMĘ 2 LICZB CAŁKOWITYCH NA 3 SPOSOBY)

Twój program powinien wczytywać pary liczb całkowitych i wypisywać dla nich wynik aż do momentu, gdy obie wczytane liczby będą miały wartość 0. Wtedy program powinien się zatrzymać.

Możesz założyć, że wartości wejściowe posiadają następujące ograniczenia:

0 < "suma" < (31 - "czynniki")
0 < "czynniki" < 11
Na początek:  podrozdziału   strony 

Problem B - Automatyczne poprawianie pisowni

Opis

Badania pokazały, że najpowszechniejszymi błędami pisowni popełnianymi przez użytkowników edytorów tekstowych lub systemów przetwarzania tekstów są często błędy przy wpisywaniu, a szczególnie:

  1. Zamiana miejscami dwóch sąsiednich liter.
  2. Wpisanie niewłaściwej litery.
  3. Pominięcie jednej litery.

Przy pomocy słownika system przetwarzania tekstu może często wykryć i automatycznie poprawić tego rodzaju błędy pisowni. Twoim zadaniem jest napisanie programu, który wykonuje część pracy związanej z wyszukiwaniem błędów pisowni, a dokładniej ma on rozpoznawać trzy rodzaje błędów, które przedstawiliśmy powyżej. W tym zadaniu "słowo" będzie złożone z od 1 do 10 znaków dużych liter, a każde słowo wejściowe będzie się rozpoczynało od nowego wiersza w pierwszej kolumnie.

Na wejściu najpierw zostanie podane do 100 słów, które będą stanowiły "słownik". Słowa należące do słownika zostaną zakończone przez wiersz zawierający w pierwszej kolumnie znak gwiazdki – *.

Po wierszach słownika pojawią się wiersze ze słowami, które należy sprawdzić. W każdym z tych wierszy będzie tylko jedno słowo. Ciąg wierszy słów będzie zakończony wierszem zawierającym gwiazdkę – *. Dla każdego ze słów najpierw wypisz sprawdzane słowo na początku nowego wiersza, a następnie wypisz na jego temat jedną z poniższych wiadomości:

Jeśli słowo występuje w słowniku bez błędów, wypisz CORRECT i przejdź do przetwarzania kolejnego słowa.

Jeśli słowa nie ma w słowniku, to znajdź w nim wszystkie słowa, dla których dane słowo wejściowe może błędem pisowni. Wypisz odpowiednią ilość następujących wiadomości:

TWO LETTERS TRANSPOSED IN słowo
ONE LETTER DIFFRENT FROM słowo
ONE LETTER OMITTED FROM słowo

Zauważ, że może być potrzebne dwie lub więcej tych wiadomości oraz jedna wiadomość może stosować się do więcej niż jednego słowa ze słownika. Wypisz wszystkie wiadomości, które mają zastosowanie. W każdym przypadku "słowo" w powyższych wiadomościach oznacza słowo ze słownika. Wiadomości te powinny być wypisywane w osobnych wierszach.

Jeśli nie można zastosować żadnej z powyższych wiadomości, wypisz UNKNOWN.

Wszystkie wiadomości powinny być wypisywane w wierszu z odstępem 4 spacji.

Na początek:  podrozdziału   strony 

Problem C - Owady

Opis

Znany powszechnie owad gryzący (rzędu hemiptera o nazwie naukowej Obżartus wszystkożerus), spotykany głównie na północy New Jersey, objawia ciekawe zachowanie wśród przedstawicieli swojego gatunku. Gdy umieści się go na płaskiej powierzchni z innym owadem w zasięgu jego wzroku, to zaczyna iść ze stałą prędkością w kierunku tego drugiego owada w celu próby złapania go i pożarcia. Jeśli drugi owad ma w zasięgu wzroku trzeciego owada, to postępuje tak samo; podobnie dla trzeciego owada. Gdy kilka owadów zostanie umieszczonych razem na płaskiej powierzchni, to wszystkie zaczynają poruszać się wzdłuż krzywych w kierunku innego poruszającego się owada.

W tym zadaniu otrzymasz początkowe współrzędne kilku owadów i będziesz musiał określić miejsce, w którym zakończą one swoją wędrówkę. Do przetworzenia będzie dokładnie cztery zestawy danych o następującej strukturze:

Pierwszy wiersz zawiera liczbę całkowitą od 2 do 9 (włącznie), która reprezentuje liczbę owadów. Następne kilka wierszy (po jednym dla każdego owada w kolejności owad1, owad2, ..., owadN) zawierają po dwie liczby rzeczywiste, które reprezentują kolejno współrzędne x i y pozycji początkowej owada. Każda liczba będzie w zakresie od -9999.9 do +9999.0, każda będzie zawierała jednocyfrową część dziesiętną.

Każdy owad widzi tylko następnego owada w numeracji, a owad o najwyższym numerze widzi owada nr 1. Jednocześnie każdy owad wykonuje krok o długości dokładnie jednej jednostki w kierunku owada, którego widzi. Dla celów tego zadania, symulacja trwa do momentu, gdy:

  1. Co najmniej jeden owad osiągnie pozycję odległą o jednostkę lub mniej od pozycji owada, którego ściga; lub
  2. zostanie wykonane 100 kroków.

Gdy tylko wystąpi jeden z tych warunków, wypisz:

dwa puste wiersze;
liczbę wykonanych kroków;
numer każdego owada i jego końcową pozycję (współrzędne x i y) z dokładnością do jednego miejsca po przecinku. Każdy owad w osobnym wierszu.

Zwróć uwagę, że po każdym kroku każdy owad być może będzie zmuszony do zmiany kierunku ruchu, ponieważ jego owad docelowy również się porusza. Zauważ również, że jeśli pozycja początkowa jakiegoś owada jest w odległości jednostki lub mniejszej od jego owada docelowego, to symulacja kończy się natychmiast bez wykonywania żadnych kroków.

Na początek:  podrozdziału   strony 

Problem D - Kod rozwijanych kwadratów

Opis

Jedna z metod kodowania wiadomości jest znana pod nazwą "kodu rozwijanych kwadratów". Metoda ta koduje wiadomości przez umieszczanie znaków wiadomości w kwadratowej macierzy nieparzystego stopnia wiersz po wierszu, a następnie pobieranie ich w spiralnie rozwijanym zgodnie z ruchem wskazówek zegara kwadracie poczynając od środka macierzy. Jeśli wiadomość nie wypełnia całkowicie macierzy, to na wolnych pozycjach są wstawiane gwiazdki (*).

Na przykład dwie poniższe macierze kwadratowe pokazują kolejność wstawiania znaków do macierzy oraz kolejność ich pobierania. Zauważ, iż pobieranie znaków zaczyna się w środku macierzy, następnie przechodzi na prawo i kontynuuje się w sposób spiralny zgodnie z ruchem wskazówek zegara.

Kolejność wstawiania
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Kolejność pobierania
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
Wiadomość wejściowa:
"THIS IS A TEST MESSAGE!!"
T H I S  
I S   A  
T E S T  
M E S S A
G E ! ! *
Wiadomość wyjściowa:
"STSSEES A  A*!!EGMTITHIS "

Twój program musi umieć zarówno kodować jak i dekodować wiadomości wg tej metody. Dane wejściowe będą złożone z par wierszy. Pierwszy wiersz każdej pary będzie zawierał albo słowo ENCODE (koduj), albo słowo DECODE (dekoduj) pisane dużymi literami od kolumny nr 1. Drugi wiersz każdej pary będzie złożony z wiadomości do zakodowania lub do dekodowania zawierającej maksymalnie 72 znaki.

Z długości wiadomości powinieneś określać minimalny stopień nieparzysty macierzy i wykonać określoną operację. Wyjście dla każdej operacji będzie się składać z jednego pustego wiersza, danej wiadomości oraz wiadomości wynikowej. Każda wiadomość ma być w osobnym wierszu i każda powinna być odpowiednio opisana. Zdekodowana wiadomość nie może zawierać znaków gwiazdki używanych do wypełniania macierzy w procesie kodowania. Możesz założyć, że żadna wiadomość nie będzie się kończyć gwiazdką.

Twój program powinien kontynuować odczytywanie wierszy wejściowych i wykonywanie operacji, aż zostanie napotkana operacja inna niż ENCODE lub DECODE.

Na początek:  podrozdziału   strony 

Problem E - Wybory do honorowego stowarzyszenia

Opis

Uniwersytet Imatellin otrzymał sekcję Upsilon Gamma Eta narodowego stowarzyszenia honorowego studentów w Zarządzie Całonocnej Kręgielni. Uniwersytet Imatellin potrzebuje jakiegoś programu do wyboru tych studentów, którzy nadają się do wstąpienia do tego boskiego stowarzyszenia. Kryteria są następujące:

  1. 30 lub więcej obowiązkowych godzin kursów i średnia ocena 3.0 lub wyższa na tych kursach oraz
  2. 12 lub więcej obowiązkowych godzin kursów Zarządu Kręgielni ze średnią ocen 3.25 lub wyższą na tych kursach.

Plik historii kursów dla studentów Uniwersytetu Imatellin zawiera dla każdego z nich ciągłą grupę 68-znakowych rekordów, z których każdy zawiera nazwisko studenta w pierwszych 20 znakach, po którym bezpośrednio następuje do ośmiu sąsiadujących ze sobą elementów kursów. Wszystkie litery alfabetu są duże.

Każdy 6-znakowy element kursu składa się z dwuliterowego prefiksu departamentu (BM dla kursów Zarządu Kręgielni), dwucyfrowego numeru kursu, jednej cyfry określającej liczbę godzin obowiązkowych na kursie oraz literowej oceny otrzymanej na kursie. Nieużywane elementy kursów są wypełnione spacjami.

Punkty średnich ocen mają być obliczone w cztero-punktowej skali (A=4, B=3, C=2, D=1, F=0), ważone jak zwykle wg liczby godzin obowiązkowych dla każdego kursu. Aby utrzymać swoją cenioną akredytację, Imatellin nie ma innych skal oceniania, takich jak zaliczył/nie zaliczył, i każde podejście do każdego kursu jest obecne w rachunku punktów oceny.

Napisz program odczytujący plik danych opisanych powyżej i wymieniający na liście nazwiska tych studentów z pliku, którzy kwalifikują się do Upsilon Gamma Eta.

Przykładowa grupa rekordów studenta jest podana poniżej.

KEGLER, STAR        PE014AHI013DMA024CBM014ASS223F
KEGLER, STAR        SS223CPE024AMA044DBM024AHI023DTX031D
Na początek:  podrozdziału   strony 

Problem F - Optymalne kody przedrostkowe

Opis

Dla danego zbioru wartości zdefiniuj pewien "kod" jako zbiór symboli do reprezentowania tych wartości. "Symbol" jest definiowany jako łańcuch cyfr wybranych ze zbioru 0, 1, ..., k-1.  Nie wszystkie symbole będą koniecznie zawierały tę samą liczbę cyfr.

"Optymalnym kodem prefiksowym" jest kod o dwóch własnościach:

  1. Żaden symbol nie jest prefiksem żadnego innego symbolu oraz
  2. Wszystkie symbole są tak krótkie, jak jest to możliwe.

Na przykład zbiór dziesięciu wartości może być zakodowany symbolami wybranymi z 0, 1 jako:

0000  0001   010  011  100  101  110  111  0010  0011

Ten kod posiada powyżej opisane dwie własności i dlatego jest optymalnym kodem przedrostkowym.

Następny przykład pokazuje inny sposób kodowania dziesięciu wartości symbolami utworzonymi z 0, 1, lecz nie posiada własności (1).

0  1  00  01  10  11  000  001  010  011

Kolejny przykład również pokazuje sposób kodowania dziesięciu wartości za pomocą symboli utworzonych z 0,1, lecz nie posiada własności (2).

0  10  110  1110  11110  111110 1111110  11111110  111111110  1111111110

Masz napisać program, który znajdzie i wydrukuje optymalne kody przedrostkowe. Dane wejściowe będą złożone z n (liczby wartości do reprezentowania) i k (liczby cyfr dozwolonych w symbolach). Wartości te będą liczbami całkowitymi 2 ≤ n ≤ 100 i 2 ≤ k ≤ 8. Wartość n będzie wyrównana prawostronnie w kolumnach od 1 do 3, a wartość k będzie wyrównana prawostronnie w kolumnach od 4 do 6 i obie będą w tym samym wierszu. W przedstawionym powyżej przykładzie n = 10, k = 2. Będą dokładnie cztery zbiory danych.

Dla każdego zbioru danych wydrukuj odpowiednio opisane wartości n i k, a następnie symbole kodu z ośmioma symbolami na jeden wiersz wyjściowy (z wyjątkiem być może ostatniego wiersza). Symbole można drukować w dowolnej kolejności.

Zauważ, że jeśli symbole optymalnego kodu przedrostkowego ustawić w drzewo, gdzie każdy poziom w drzewie dodaje jedną więcej cyfrę do symbolu, to optymalny kod przedrostkowy posiada minimalną liczbę poziomów, a każdy symbol odpowiada węzłowi liścia tego drzewa. Pokazany powyżej pierwszy przykład kodu tworzy poniższe drzewo:

Na początek:  podrozdziału   strony 

Problem G - Zliczanie punktów w brydżu

Opis

"Ręka" w brydżu składa się z 13 kart. Licytowanie rozpoczyna się od sumowania wartości punktowych ręki, a następnie wykonuje się odzywkę w licytacji, jeśli suma jest odpowiednia.

Masz napisać program, który na wejściu otrzyma 13 kart w ręce w grze w brydża, a następnie obliczy wartość punktową tej ręki. Każda karta reprezentowana jest przez dwie dwucyfrowe liczby. Każda liczba rozdzielona jest od poprzedniej spacją. Pierwsza liczba określa rangę karty: 1=as, 2=dwójka, ..., 10=dziesiątka, 11=walet, 12=dama, 13=król. Druga liczba określa kolor: 1=trefl, 2=karo, 3=kier, 4=pik. Stąd:

 9 3 = 9 kier
 1 2 = as karo
13 4 = król pik

Wartości reprezentujące trzynaście kart ręki znajdą się wszystkie w tym samym wierszu wejściowym występując naprzemiennie jako ranga, kolor, ..., ranga kolor.

Oblicz wartość punktową ręki używając następujących reguł:

  1. 4 punkty za asa
  2. 3 punkty za króla z przynajmniej jedną inną kartą tego samego koloru (tj. co najmniej dwie karty w tym kolorze)
  3. 2 punkty za damę z co najmniej dwoma innymi kartami tego samego koloru
  4. 1 punkt za waleta z co najmniej trzema innymi kartami tego samego koloru
  5. 3 punkty za kolor bez kart
  6. 2 punkty za kolor z tylko jedną kartą
  7. 1 punkt za kolor z tylko dwoma kartami
  8. stosuj reguły f i g, nawet jeśli jedna z pozostałych reguł ma również zastosowanie
  9. stosuj reguły a ... d tak często, jak jest to odpowiednie dla dowolnego koloru
Przykład: Jeśli na ręce jest król, dama i walet kier:
dodaj 3 punkty za króla
dodaj 2 punkty za damę
brak punktów za waleta, ponieważ w tym kolorze są tylko trzy karty

Przykład: Jeśli na ręce jest król i trójka pik
dodaj 3 punkty za króla
dodaj 1 punkt za kolor z tylko dwoma kartami

Dla każdej ręki odczytaj wartości kart, oblicz wartość punktową i wypisz rękę z jej wartością punktową i odpowiednim opisem. Program powinien zakończyć się po przetworzeniu wszystkich rąk.

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.