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

1988

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Kontrola ruchu powietrznego

Usługa oferowana przez FAA (Francine's Airplane Alarms) używa radaru do informowania pilotów samolotów, gdy znajdą się w niebezpieczeństwie zbyt bliskiego przelotu obok innego samolotu w powietrzu. W tym zadaniu masz napisać program symulujący ten radar.

Aby uprościć zadanie, możesz założyć, iż rozważana przestrzeń powietrzna znajduje się ponad płaską Ziemią i jest wyśrodkowana na współrzędnych (0,0). Dodatnia połowa osi y wskazuje na północ, a dodatnia połowa osi x wskazuje na wschód. Wszystkie współrzędne są w milach, wszystkie prędkości lotu są w milach na godzinę, a wszystkie wysokości są w stopach (jedna mila = 5280 stóp). Możesz również założyć, iż prędkość w powietrzu jest równa prędkości na lądzie (co oznacza brak wiatru).

Dane wejściowe dla programu będą złożone z maksymalnie dwudziestu wierszy, po jednym dla każdego samolotu w przestrzeni powietrznej. Każdy wiersz zawiera liczby rozdzielone jedną lub więcej spacjami, które podają kolejno następujące wartości:

Możesz założyć, iż przez cały czas symulacji wszystkie samoloty utrzymują stałą prędkość lotu, wysokość i kierunek.

Termin zagrożenie zderzeniem (ang. near miss) oznacza, że dwa samoloty znajdą się od siebie w odległości do pięciu mil, mierzonej tylko poziomo (zignoruj wysokość przy obliczaniu tej odległości), i jednocześnie różnią się wysokością o maksymalnie 1000 stóp. Twój program powinien wykrywać wszystkie zagrożenia zderzeniem pomiędzy dowolnymi dwoma samolotami. Dla każdego zagrożenia zderzeniem powinieneś wydrukować czas (w sekundach od początku symulacji), gdy wykryłeś to zagrożenie, jak również numery lotów, pozycje (współrzędne) i wysokości obu samolotów, których to zdarzenie dotyczy.

Twoja antena radarowa wykonuje jeden obrót co każde 20 sekund, zatem możliwe jest, iż dwa samoloty znajdą się w granicach zagrożenia zderzeniem tylko przez kilka sekund, gdy twoja antena skierowana jest w drugą stronę. Jest to akceptowalne! Dostarczony zbiór danych został tak zaprojektowany, aby posiadał zagrożenia zderzeniem trwające przez co najmniej 20 sekund, więc nie jest ważne, w którą stronę jest skierowana twoja antena, gdy symulacja się rozpocznie. Zapamiętaj również, iż zgłaszany przez ciebie czas zagrożenia zderzeniem nie musi odpowiadać dokładnie sekundzie wystąpienia tego zagrożenia; może być o 20 sekund późniejszy i wciąż być prawidłowym. Podobnie zgłaszane położenie może znajdować się w dowolnym miejscu strefy zagrożenia zderzeniem, zależnie od czasu wykrycia tego incydentu.

Każde zagrożenie zderzeniem powinno być zgłaszane tylko jeden raz. Dwa samoloty mogą wciąż znajdować się w granicach strefy zagrożenia zderzeniem po upływie 20 sekund, gdy twój radar zobaczy je ponownie. Nie zgłaszaj ponownie tych dwóch samolotów.

Twoja symulacja ma się zakończyć po trzech godzinach.

Na początek:  podrozdziału   strony 

Problem B - Punktacja w Candlepin Bowling

Kręgle Candlepin, chociaż używają tej samej liczby kręgli (10) i tej samej długości i szerokości parkietów co zwykłe kręgle Ten Pin, to jednak różnią się kształtem samych kręgli, co pokazuje obrazek powyżej. Kule są dużo mniejsze (mniej więcej o rozmiarze grapefruita) i dużo trudniej jest osiągnąć wysoką punktację niż w kręglach Ten Pin (kręglarze klasy mistrzowskiej w Ten Pin Bowling często mają średnio 210 punktów na grę, gdy natomiast kręglarze klasy mistrzowskiej w Candlepin Bowling zwykle mają średnio około 130 punktów na grę). Ta różnica może być szczególnie zaskakującą dla osób niezaznajomionych z tą grą, szczególnie że kręglarz Candlepin może wykonywać 3 rzuty kulą na ramkę, podczas gdy kręgle Ten Pin zezwalają tylko na dwa rzuty na ramkę.

W tym zadaniu masz napisać program liczący punkty w grach w kręgle Candlepin. Każda ramka składa się z maksymalnie trzech rzutów kulą. Ramki są punktowane zgodnie z następującymi regułami:

  1. Jeśli pierwsza rzucona kula zbije wszystkie dziesięć kręgli (co nazywane jest "strike" i oznaczane jako X), to punkty za tą ramkę są równe 10 plus liczba kręgli zbitych przez następne dwie kule rzucone w następnych ramkach. Gdy zostanie wyrzucony strike, to w tej ramce nie są już rzucane żadne kule, ponieważ wszystkie kręgle zostały już zbite (zobacz do punktu 4 na wyjątek finałowej ramki).
  2. Jeśli przez pierwszą kulę nie zostanie zbite wszystkie dziesięć kręgli, lecz zostaną one zbite przez połączone rzuty pierwszej i drugiej kuli w danej ramce (zwane "spare" i oznaczane jako /), to wynikiem dla tej ramki jest 10 plus liczba kręgli zbita przez następną rzucaną kulę (to jest pierwszą kulę rzuconą w następnej ramce). Gdy zostanie wykonane spare, to trzecia kula nie jest rzucana w tej ramce, ponieważ wszystkie kręgle zostały zbite (zobacz do punktu 4 na wyjątek finałowej ramki).
  3. Jeśli wszystkie dziesięć kręgli nie zostało zbite przez pierwszą kulę (strike) lub kule pierwszą i drugą (spare), rzucana jest trzecia kula, a punktacja tej ramki to po prostu liczba kręgli zbitych przez wszystkie trzy kule.
  4. Ponieważ dziesiąta ramka jest ramką finałową, nie można zliczać kręgli z następnych ramek w celu zakończenia strike'ów i spare'ów , które wypadły w ramce dziesiątej. Dlatego ramka dziesiąta zawsze składa się z 3 rzutów kul, gdzie:
    1. jeśli pierwsza kula w ramce to strike, kręgle są resetowane (ustawia się dziesięć nowych kręgli, jak na początku każdej ramki), a kręglarz rzuca jeszcze dwie kule; w przypadku kolejnego strike'a kręgle są ponownie resetowane i kręglarz rzuca w nie jeszcze jedną kulą; punktacja za taką ramkę wynosi 10 plus suma kręgli zbitych przez następne dwie kule;
    2. jeśli pierwsza kula nie jest strike'iem, ale połączenie dwóch pierwszych kul daje spare'a, kręgle są resetowane i kręglarz rzuca w nie jedną kulą; punktacja ramki wynosi 10 plus liczba kręgli zbitych przez trzecią kulę;
    3. jeśli w dziesiątej ramce nie wypadnie ani strike, ani spare, to punktacja za ramkę jest po prostu równa liczbie kręgli zbitych przez wszystkie trzy kule.

Twój program ma odczytać z pliku danych wyniki każdego rzutu kulą w dowolnej liczbie gier w kręgle i wydrukować wynik każdej z nich. Każdy wiersz danych będzie reprezentował wyniki każdego rzutu kulą w pojedynczej grze. Elementy danych reprezentujące wyniki rzutów kulami w grze znajdują się w kolumnach o numerach parzystych, rozdzielone spacjami w kolumnach o numerach nieparzystych. Wiersz danych z ** w kolumnach 1 i 2 oznacza koniec pliku danych.

Poprawne elementy danych reprezentujące wyniku rzutów kulami w grze są następujące: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, / i X. (Zauważ, iż ten program akceptuje dane w takiej postaci, w jakiej zostałyby one wprowadzone do arkusza punktacji gry w kręgle; tj. jeśli pierwsza kula w ramce była strike'iem, to wpisywane jest X, nie 10; jeśli pierwsza i druga kula dały 8 i 2 jako spare, wpisywane jest 8 /, a nie 8 2.) Jednakże zostanie zastosowane jedno drobne odstępstwo, aby pojedynczy znak A mógł reprezentować 10 jako wynik trzeciej kuli w ramce, w której dwie pierwsze kule zdobyły 0 punktów za zbite kręgle. (Zauważ, iż jeśli pierwsza kula w ramce miała 0 punktów, a wszystkie dziesięć kręgli zostało zbite drugą kulą, to zapis ma postać 0 /, co oznacza spare.)

Przykładowy wiersz danych reprezentujący prawidłowe wyniki gry wygląda następująco:

 X 8 / 7 2 1 3 5 0 6 / 7 / 5 2 2 X 9 / X X 8

Co po zamianie na ramki da punktację:

 X      8 /     7 2 1     3 5 0     6 /     7 /     5 2 2      X      9 /      X X 8

20      17       10         8       17      15        9       20      20        28  

lub punktacja kumulacyjna:

20      37       47        55       72      87       96       116     136       164  

Zakładając, iż pierwszy wiersz danych do przetworzenia był reprezentowany przez przedstawiony powyżej przykład, a punktowano n gier, twoje wyjście powinno być zaprezentowane następująco:

GAME #1:  164
GAME #2:  xxx
   .
   .
   .
GAME #n:  xxx

END OF SCORING  

Możesz założyć, iż każdy wiersz do obliczenia punktacji zawiera poprawną kombinację elementów.

Na początek:  podrozdziału   strony 

Problem C - Machlojki

xxx
Na początek:  podrozdziału   strony 

Problem D - Status procesora multikomputera

xxx
Na początek:  podrozdziału   strony 

Problem E - Pomiary opadów

xxx
Na początek:  podrozdziału   strony 

Problem F - Ładny wydruk

xxx
Na początek:  podrozdziału   strony 

Problem G - Odtwarzanie drzewiaste

xxx
Na początek:  podrozdziału   strony 

Problem H - Zarządca okien

xxx
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.