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

1978

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Duże liczby całkowite

Opis

Zadaniem twojego programu jest wczytanie wiersza tekstu, który zawiera dwie nieujemne liczby całkowite (przynajmniej jedna z nich jest różna od zera), a następnie obliczenia i wyświetlenia ich sumy. Po wykonaniu tego zadania program powinien cyklicznie powtarzać te operacje, aż na wejściu pojawi się pusty wiersz, który kończy działanie programu.

Specyfikacja wejścia

Każdy wiersz z danymi zawiera dwie liczby całkowite. Pierwsza z nich znajduje się gdzieś w pierwszych 40 znakach tekstu, a druga w pozostałych 40 znakach - przyjmujemy, że wiersz wejściowy będzie miał długość 80 znaków. Przed liczbą mogą pojawić się zera wiodące jako spacje. Wewnątrz liczby spacje mają być potraktowane jako zera. Pusty wiersz wejściowy oznacza koniec programu. Wartość liczby całkowitej może przekraczać dozwolone wartości dla danych całkowitych.

Specyfikacja wyjścia

Dla każdego wiersza z danymi na wyjściu ma być wyświetlona suma wyrównana prawostronnie do kolumny 50. Wyświetlana liczba musi być podzielona na grupy po 3 cyfry rozdzielone przecinkiem (system anglosaski). Suma nie może posiadać zer wiodących.

Przykładowe dane wejściowe

         1         2         3         4         5         6         7         8
.........0.........0.........0.........0.........0.........0.........0.........0
                                       |
                      05 16523892                    6723519440

Przykładowe dane wyjściowe

         1         2         3         4         5         6         7         8
.........0.........0.........0.........0.........0.........0.........0.........0
                                                 |
                                    11,740,043,332
Na początek:  podrozdziału   strony 

Problem B - Wirtualne ściany z cegieł

Opis

Przy budowie ściany z cegieł istotnym jest zakup wystarczającej ilości materiału. Jeśli używane są cegły o różnych wymiarach, to można przeprowadzić interesującą symulację "wirtualnej ściany" w celu określenia liczby potrzebnych cegieł. Dla tego zadania otrzymujesz wymiary ściany oraz liczbę dostępnych cegieł każdego typu. Masz określić, czy z tych cegieł da się zbudować pożądaną ścianę i jak będą wyglądały kolejne warstwy cegieł.

Specyfikacja wejścia

Na wejściu program otrzymuje ciąg wierszy z liczbami rozdzielonymi od siebie za pomocą znaków spacji. Wiersz zawierający liczbę 0 na początku oznacza koniec działania programu. W każdym wierszu z danymi liczby określają następujące parametry:

w  - szerokość ściany w jednostkach (w ≤ 20)
h  - liczba wymaganych warstw cegieł (h ≤ 12)
n3  - liczba dostępnych cegieł typu 3
n2  - liczba dostępnych cegieł typu 2
n1  - liczba dostępnych cegieł typu 1

Cegły typu 3 mają szerokość 3 jednostek, cegły typu 2 mają szerokość 2 jednostek i cegły typu 1 są szerokie na 1 jednostkę. Cegły zawsze muszą być kładzione poziomo, nigdy pionowo.

Specyfikacja wyjścia

Dla każdego problemu budowy ściany należy albo wypisać jedyną wiadomość:

CAN'T BE DONE

jeśli dostarczone cegły nie dadzą się ułożyć w żądaną ścianę; lub jeśli da się to zrobić, należy wypisać obraz ściany wg poniższego opisu.

Drukuj obrazki cegieł o następujących wymiarach:

Cegły typu 3:   

******************
*                *
*                *
******************

Cegły typu 2:

************
*          *
*          *
************

Cegły typu 1:

******
*    *
*    *
******

Przykładowe dane wejściowe

5 3 4 2 6
0

Przykładowe dane wyjściowe

******************************
*                **          *
*                **          *
******************************
******************************
*          **                *
*          **                *
******************************
******************************
*    **                **    *
*    **                **    *
******************************
Na początek:  podrozdziału   strony 

Problem C - Kody bezpieczeństwa

Opis

Aby zapewnić poprawność często używanych kodów, przy każdym użyciu można w nich systematycznie osadzać ciąg cyfr kontrolnych. Na przykład, pewien określony algorytm kodu bezpieczeństwa mógłby korzystać z sumy wszystkich cyfr modulo 26, a następnie dołączać na końcu odpowiadający tej sumie znak alfabetu. W takim przypadku 57359 wymagałoby znaku kontrolnego 'D', ponieważ:

5 + 7 + 3 + 5 + 9 = 29
29 mod 26 = 3
A = 0
B = 1
C = 2
D = 3

Dzisiaj szeroko używa się umiarkowanie wyrafinowanych wariacji tego schematu w kartach kredytowych, kodach bezpieczeństwa oraz hasłach.

Odwrotnością opisanego wyżej procesu jest złamanie takiego schematu kodowania, mając do dyspozycji wystarczająco dużo informacji. Twoje zadanie polega na złamaniu specyficznego schematu zabezpieczania cyfr. Ten specyficzny schemat używa cyfr z lewa na prawo, w którym występuje albo dodawanie, albo odejmowanie, albo mnożenie pomiędzy sąsiednimi cyframi. Wiesz również, że w algorytmie każda cyfra używana jest tylko jeden raz.  Mając zbiór pięciocyfrowych kodów, za którymi występują pojedyncze litery alfabetu, napisz program, który złamie ten kod.

Specyfikacja wejścia

W pierwszym wierszu program otrzyma 10 sześcioznakowych kodów - pięć cyfr oraz litera zabezpieczająca. Kolejne kody będą oddzielone pojedynczą spacją.
W drugim wierszu będzie się znajdowało 10 kodów po pięć cyfr, również rozdzielonych pojedynczą spacją.

Specyfikacja wyjścia

Na podstawie danych wejściowych program ma określić algorytm litery kontrolnej. W pierwszym wierszu wyjścia mają być wypisane otrzymane kody, w drugim wierszu odgadnięty algorytm wyznaczania litery kontrolnej (w podanym przykładzie wstępnym będzie to A+B+C+D+E) oraz w trzecim wierszu zestaw kodów z drugiego wiersza wejściowego uzupełnionych o literę kontrolną.

Przykładowe dane wejściowe

31413D 45976E 22728G 76575F 33696W 50681A 96723O 44885H 24196B 22227X
52005 67861 28265 59772 96199 78614 89492 47243 81620 56593

Przykładowe dane wyjściowe

31413D 45976E 22728G 76575F 33696W 50681A 96723O 44885H 24196B 22227X 
A-B+C*D-E
52005Y 67861U 28265B 59772R 96199D 78614B 89492H 47243C 81620T 56593P
Na początek:  podrozdziału   strony 

Problem D - Symulacja obiegu skoczka

Opis

Dla szachownicy n  × n  obiegiem skoczka nazywamy ciąg ruchów, przy których każde pole szachownicy jest odwiedzane dokładnie jeden raz przez skoczka wykonującego prawidłowe (szachowe) posunięcia. Na poniższym rysunku skoczek (K) może skoczyć na dowolne z pól ponumerowanych od 1 do 8.

  8   1      
7       2    
    K       (n = 5)
6       3    
  5   4      

Oczywiście skoczek znajdujący się przy krawędzi lub w narożniku szachownicy posiada mniej dostępnych możliwych posunięć.

Ten problem wymaga znalezienia jednego z poprawnych obiegów skoczka na szachownicy o rozmiarze 5 × 5.

Specyfikacja wejścia

Na wejściu program otrzyma dwie liczby całkowite r - wiersz oraz c - kolumna, które określają pozycję startową skoczka na szachownicy (pozycja 1 1 odnosi się do lewego górnego pola).

Specyfikacja wyjścia

Na wyjściu powinna pojawić się macierz liczb o wymiarze 5 × 5, która przedstawia kolejne ruchy skoczka z pola na pole. Pod macierzą powinno się pojawić słowo OPEN lub CLOSED. Jeśli obieg skoczka kończy się na polu szachownicy, do którego można skoczyć jednym ruchem z pozycji startowej, to taki obieg nazwiemy zamkniętym - CLOSED. W przeciwnym razie jest to obieg otwarty - OPEN.

Przykładowe dane wejściowe

3 3

Przykładowe dane wyjściowe

  25   8   3  14  19
   2  13  18   9   4
   7  24   1  20  15
  12  17  22   5  10
  23   6  11  16  21
OPEN
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.