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

1979

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Zagadka z kołków

Opis

Mała zagadka, która stała się popularna w różnych restauracjach, składa się z trójkątnego kawałka drewna z przewierconymi w nim 15 otworami. Numeracja oraz układ tych otworów są  następujące:

obrazek

Zagadka rozpoczyna się od drewnianych kołków w 14 otworach. Celem jest "skakanie i usuwanie" 13 z tych kołków, kończąc z tylko jednym kołkiem pozostałym na planszy. Reguły są następujące:

  1. Kołek można przesunąć tylko skokiem ponad innym kołkiem w wolny otwór, zbijając przeskoczony kołek.
  2. Wolno przeskakiwać tylko przez sąsiedni kołek, który jest połączony linią z kołkiem, który skacze.
  3. Skok musi w całości odbyć się wzdłuż łączącej linii i jej przedłużenia.
  4. Skok można wykonać tylko wtedy, gdy bezpośrednio za przeskakiwanym kołkiem znajduje pusty otwór.

Daje to 36 potencjalnych ruchów, które zebrano w poniższej tabeli:

Kołek
na pozycji
przeskakuje
kołek
na pozycji
i ląduje
w pustym otworze
na pozycji
01 02 04
04 02 01
01 03 06
06 03 01
02 04 07
07 04 02
03 06 10
10 06 03
04 07 11
11 07 04
06 10 15
15 10 06
11 12 13
13 12 11
12 13 14
14 13 12
13 14 15
15 14 13
02 05 09
09 05 02
03 05 08
08 05 03
04 05 06
06 05 04
04 08 13
13 08 04
05 08 12
12 08 05
07 08 09
09 08 07
05 09 14
14 09 05
06 09 13
13 09 06
08 09 10
10 09 08

Program ma odczytać początkowy układ kołków na planszy. Układ ten jest opisany za pomocą 15 cyfr dwójkowych, gdzie "1" oznacza, że otwór odpowiadający pozycji cyfry zawiera w sobie kołek, a "0" oznacza, że jest on pusty - będzie 14 cyfr o wartości "1" oraz jedna cyfra "0". Program ma następnie obliczyć i wypisać ciąg ruchów, które kończą się jednym kołkiem pozostałym na planszy. Taki ciąg będzie istniał dla początkowej konfiguracji, którą program napotka w trakcie oceniania.

Specyfikacja wejścia

Na wejściu program będzie otrzymywał ciąg wierszy z cyframi binarnymi, które określają konfigurację planszy. Cyfry są numerowane od strony lewej do prawej.. W każdym wierszu będzie dokładnie 15 cyfr. Pierwsza cyfra określa otwór nr 1, ostatnia cyfra określa otwór nr 15. Wiersz końcowy będzie się składał z 15 zer. Po napotkaniu wiersza końcowego program ma zakończyć działanie.

Specyfikacja wyjścia

Dla każdego zestawu konfiguracji planszy program ma wyznaczyć ciąg ruchów, które prowadzą do rozwiązania zagadki - po wykonaniu tych ruchów na planszy ma pozostać tylko jeden kołek. Każdy ruch ma być opisany następująco:

PEG AT n1 JUMPS PEG AT n2 AND MOVES TO n3
n1 - pozycja kołka, którym wykonujemy skok
n2 - pozycja kołka, nad którym przeskakujemy - ten kołek zostanie usunięty z planszy
n3 - pozycja otworu, w którym ląduje skaczący kołek

Po wypisaniu wszystkich ruchów w danym ciągu program powinien wypisać trzy puste wiersze i przejść do analizy kolejnego zestawu danych lub zakończyć działanie w przypadku otrzymania w danych wejściowych 15 zer.

Przykładowe dane wejściowe

111101111111111
000000000000000

Przykładowe dane wyjściowe

PEG AT 14 JUMPS PEG AT  9 AND MOVES TO  5
PEG AT  7 JUMPS PEG AT  8 AND MOVES TO  9
PEG AT 10 JUMPS PEG AT  9 AND MOVES TO  8
PEG AT 12 JUMPS PEG AT 13 AND MOVES TO 14
PEG AT  3 JUMPS PEG AT  6 AND MOVES TO 10
PEG AT 15 JUMPS PEG AT 10 AND MOVES TO  6
PEG AT  2 JUMPS PEG AT  4 AND MOVES TO  7
PEG AT  6 JUMPS PEG AT  5 AND MOVES TO  4
PEG AT  7 JUMPS PEG AT  4 AND MOVES TO  2
PEG AT  1 JUMPS PEG AT  2 AND MOVES TO  4
PEG AT  4 JUMPS PEG AT  8 AND MOVES TO 13
PEG AT 14 JUMPS PEG AT 13 AND MOVES TO 12
PEG AT 11 JUMPS PEG AT 12 AND MOVES TO 13
Na początek:  podrozdziału   strony 

Problem B - Dziesiętne ułamki okresowe

Opis

Gdy x  i y  są liczbami całkowitymi, liczba wymierna x/y posiada postać dziesiętną:

iiii.fffff...

Jeśli od pewnego miejsca wszystkie dalsze cyfry f  są zerami, to zwykle opuszcza się je i można zapisać dokładny odpowiednik dziesiętny danej liczby wymiernej. Inaczej ciąg cyfr ułamkowych (f  = fraction) jest nieskończony, lecz w końcu stanie się powtórzeniami pewnego podciągu. Oznaczając powtarzający się podciąg za pomocą literek r, okresowy ułamek dziesiętny używa następującej notacji:

iii.fffff(r1...rk)

w celu zapisu okresowego odpowiednika nieskończonego ułamka dziesiętnego:

iii.fffffr1...rkr1...rkr1...rk...

Na przykład:

22  = 3.(142857)       5  = 0.41(6)       100  = 9.(09)
7 12 11

Zwróć uwagę, że powtarzany ciąg cyfr znajduje się na końcu zapisu liczby i występuje tylko w części ułamkowej.

Napisz program, który:

  1. Odczyta wiersz zawierający dwie liczby całkowite dodatnie, powiedzmy x  i y.
  2. Wyprowadzi dwa puste wiersze, a następnie wypisze trzy wiersze z ułamkiem oraz jego okresowym zapisem dziesiętnym. Jeśli ułamek będzie wymagał więcej niż 50 cyfr na prawo od kropki dziesiętnej (ułamki dziesiętne zapisujemy w systemie anglosaskim z kropką zamiast przecinka), należy wypisać wiersz pokazujący wartości x  i y  oraz wiadomość z informacją o tym utrudnieniu. Jeśli liczba wymierna posiada skończony odpowiednik dziesiętny, program powinien wypisać go bez okresu w nawiasie oraz bez zer końcowych.
  3. Należy powtarzać procedurę od kroku 1, aż zostanie napotkany wiersz, w którym druga liczba y  = 0. Wtedy program powinien zakończyć działanie.

Specyfikacja wejścia

Na wejściu program otrzymuje ciąg wierszy. W każdym wierszu znajdują się dwie nieujemne liczby całkowite x i y, rozdzielone spacją. W ostatnim wierszu druga z liczb jest równa zero. Po napotkaniu ostatniego wiersza program kończy działanie. Liczby x i y będą posiadały co najwyżej 10 cyfr.

Specyfikacja wyjścia

Dla każdego wiersza wejściowego z niezerową liczbą y program powinien wypisać trzy wiersze o następującej postaci:

         x
---------- = iii.fff(rrr)
         y

gdzie

x, y - wejściowe liczby całkowite
i - cyfry całkowite
f - cyfry ułamkowe
r - cyfry okresu

Przykładowe dane wejściowe

27836 462
1 252
2 17
300030003 16
0 0

Przykładowe dane wyjściowe

     27836
---------- = 60.(251082)
       462

         1
---------- = 0.00(396825)
       256

         2
---------- = 0.(1176470588235294)
        17

 300030003
---------- = 18751875.1875
        16
Na początek:  podrozdziału   strony 

Problem C - Zamiana liczb arabskich na rzymskie

Opis

Cesarz rzymski właśnie otrzymał wiadomość od angielskiego króla. Jednakże cesarz nie rozumie liczb arabskich. Napisz program, który przetłumaczy wszystkie wartości liczbowe na liczby rzymskie, pozostawiając bez zmian resztę znaków w łańcuchu tekstowym.

Specyfikacja wejścia

Program otrzyma ciąg wierszy z wiadomością dla cesarza rzymskiego. Wyrazy w wierszach mogą być dzielone. Jednakże wszystkie liczby znajdują się w całości w swoim wierszu. Każda z liczb jest większa od 0 i mniejsza niż 4000. Liczby są dodatnie, całkowite i nie posiadają wewnątrz siebie żadnych znaków interpunkcyjnych. Wiadomość kończy się parą znaków ##.

Do konwersji wykorzystaj poniższą tabelkę:

Cyfry
arabskie
Cyfry
rzymskie
1
2
3
4
5
6
7
8
9
10
20
30
50
90
100
140
500
1000
I
II
III
IV
V
VI
VII
VIII
IX
X
XX
XXX
L
XC
C
CXL
D
M

Specyfikacja wyjścia

Program powinien wypisać kolejno wszystkie wczytane wiersze, w których liczby arabskie są zastąpione liczbami rzymskimi. Tekst otaczający te liczby nie powinien być zmieniony.

Przykładowe dane wejściowe

PLEASE ADVISE BY 19 OCTOBER, 1001.
##

Przykładowe dane wyjściowe

PLEASE ADVISE BY XIX OCTOBER, MI.
##
Na początek:  podrozdziału   strony 

Problem D - Poprawki szybkościomierza

Opis

Szybkościomierz samochodowy jest połączony z napędem samochodu i zamienia liczbę obrotów na sekundę wału silnika na prędkość w milach na godzinę. Lecz od czasu do czasu wielkość opony zmienia się, maleje, gdy zużywa się bieżnik, rośnie, gdy jest gorąco, jej rozmiar zależy od ilości powietrza w dętce, itd. W konsekwencji, jeśli nawet szybkościomierz dokładnie mierzy liczbę obrotów na sekundę, to jego odczyty mogą się różnić od prędkości, z jaką podróżuje samochód. Rogatki oraz niektóre z międzystanowych dróg posiadają ustawione słupy milowe wzdłuż jezdni. Jeśli kierowca utrzymuje prędkość samochodu na ustalonym odczycie z prędkościomierza, a pasażer mierzy okresy czasu pomiędzy słupami milowymi, to rzeczywista prędkość samochodu może być obliczona. Program ma wypisać liczbę sekund pomiędzy słupami milowymi dla samochodu jadącego z prędkościami 10, 20, 30, 40, 50, 60, 70 i 80 mil na godzinę, zaokrągloną do najbliższej sekundy. (Droga s  jest powiązana z prędkością v  i czasem t  zgodnie ze wzorem s = vt.) Prędkość jest w milach na godzinę, zatem będziesz musiał pomnożyć prędkość w milach na godzinę przez odpowiedni współczynnik, aby zmienić ją na prędkość w milach na sekundę.

 

Średnica toczna opony wynosi około 29 cali dla pełnowymiarowego samochodu oraz 25 cali dla małego samochodu osobowego. Obwód jest równy średnicy pomnożonej przez liczbę π. Program ma określić i wypisać liczbę obrotów wykonanych przez każdą z opon po przejechaniu przez samochód jednej mili (w każdej mili jest 5280 stóp) zaokrągloną do najbliższego obrotu. Program powinien również określić i wypisać liczbę obrotów na sekundę każdej z dwóch opon, gdy samochód porusza się z szybkością 30, 50, 70 i 90 mil na godzinę.

π = 3.1415926535897932385

Załóżmy, że średnica opony różni się o -10%, -5%, -1%, +1%, +5% lub +10% od średnicy założonej przy kalibracji szybkościomierza. Program ma określić i wypisać rzeczywistą prędkość, gdy odczyt prędkościomierza ma wartość 50, 60, 70, 80 lub 90 mil na godzinę dla każdego z tych błędów i dla każdego rozmiaru opony z dokładnością do najbliższej dziesiątej części mili na godzinę.

Dane produkowane przez program powinny być jasno opisane. Tam gdzie jest to możliwe należy zastosować tabele.

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.