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

1980

Rok konkursu ACM
Tematy zadań konkursu

Problem A - Zapytania

Opis

Szefowa pragnie posiadać prostą metodę realizacji zapytań (kwerend) w swoim pliku z danymi personelu i prosi ciebie, abyś w ciągu 1/2 dnia roboczego napisał program, który będzie zliczał lub wypisywał rekordy pliku spełniające pewne kryteria. Plik składa się z wierszy. W każdym wierszu znajdują się cztery dodatnie liczby całkowite: identyfikator pracownika (ID), wiek pracownika (AGE), stawka płacowa w centach na godzinę (WAGE) oraz kod rodzaju wykonywanej pracy (JOBTYPE). Wszystkie wartości są mniejsze od 32768. Zestaw rekordów pracowników będzie zawierał nie więcej niż 100 wierszy z danymi. Plik będzie się kończył pustym wierszem, który nie zawiera żadnych liczb. Nie trzeba sprawdzać poprawności tych danych, lecz następne wiersze, które będą zawierać zapytania, muszą być sprawdzone pod kątem poprawności.

Każde zapytanie będzie zawarte w pojedynczym wierszu, a żaden wiersz nie będzie zawierał więcej niż jedno zapytanie. Format poprawnego zapytania wygląda następująco:

obrazek

gdzie:

field={ID,AGE,WAGE,JOBTYPE},
ro={LT,EQ,GT},
initval=wartość całkowita bez znaku < 32768,

{ } oznacza "jeden z",
[ ] oznacza element opcjonalny,
_ oznacza jedną lub więcej spacji,

COUNT = zliczaj
LIST = listuj
QUIT = zakończ
RECORDS = rekordy
WHERE = gdzie
LT = Less Than = mniejszy niż
EQ = Equal = równe
GT = Greater Than = większe niż

Po prawej stronie zapytania mogą pojawić się różne znaki, które należy zignorować. Poprawne zapytanie rozpoczyna się od początku wiersza i nie będzie zawierało żadnych błędów w pisowni.

Program ma działać wykonując dla każdego zapytania następujące kroki nad rekordami pracowników:

  1. Odczytać wiersz z zapytaniem i wydrukować go w całości.
  2. Jeśli odczytany wiersz nie zawiera poprawnego zapytania, należy wypisać w następnym wierszu słowo ERROR, wydrukować pusty wiersz i kontynuować od kroku 1.
  3. a) Jeśli zapytanie jest typu QUIT, program ma zakończyć działanie.
    b) Jeśli zapytanie jest typu COUNT, należy wyznaczyć liczbę rekordów spełniających warunek podany w zapytaniu i wypisać ją w następnym wierszu w postaci ANSWER: liczba. Wydrukować pusty wiersz i kontynuować od kroku 1.
    c) Jeśli zapytanie jest typu LIST, to należy wyznaczyć wszystkie rekordy spełniające kryterium podane w zapytaniu i wypisać je w kolejnych wierszach w postaci: ANSWER: cztery liczby. Wydrukować pusty wiersz i kontynuować od kroku 1.

Przykładowe dane wejściowe

1 22 1200 12
2 34 1800 16
3 28 2100 4
4 39 2000 3
5 31 2800 2
6 37 3500 10
7 29 1750 12
8 25 3325 10
9 45 3725 9

COUNT RECORDS WHERE AGE.GT.30
COUNT RECORDS WHERE JOPTYPE.EQ.10
LIST  RECORDS WHERE WAGE.LT.3000
QUIT

Przykładowe dane wyjściowe

COUNT RECORDS WHERE AGE.GT.30
ANSWER: 5

COUNT RECORDS WHERE JOPTYPE.EQ.10
ERROR

LIST  RECORDS WHERE WAGE.LT.3000
ANSWER: 1 22 1200 12
ANSWER: 2 34 1800 16
ANSWER: 3 28 2100 4
ANSWER: 4 39 2000 3
ANSWER: 5 31 2800 2
ANSWER: 7 29 1750 12

QUIT
Na początek:  podrozdziału   strony 

Problem B - Analizator ciągów

Opis

Rozważmy ciąg liter alfabetu (A-Z). Mówimy, że taki ciąg posiada "stały krok", jeśli odległość alfabetyczna sąsiednich znaków w ciągu jest taka sama. (Odległość alfabetyczna pomiędzy A i B wynosi 1 <AB>, pomiędzy D a F wynosi 2 <DEF>, pomiędzy P a V wynosi 6 <PQRSTUV>, pomiędzy Z a C wynosi 3 <ZABC>). Następujące ciągi posiadają "stały krok":

ACEG...  krok = 2
AZYX...  krok = 25

Zauważ, że po Z następuje litera A i ciąg jest kontynuowany dalej. Nazywamy to własnością przewinięcia.

Mówimy, że dany ciąg jest "spleciony" z dwóch lub więcej ciągów, jeśli jego kolejne elementy są elementami pobieranymi po kolei z każdego z tych ciągów. Na przykład poniższe ciągi są splecione (kolorami zaznaczyliśmy kolejne litery ciągów splatanych) :

AQBRCSDT...  ciągi: ABCD...  krok = 1
                    QRST...  krok = 1
AZTAYRAXP... ciągi: AAA... krok = 0
                    ZYX... krok = 25
                    TRP... krok = 24

Specyfikacja wejścia

Na początku program odczyta liczbę wierszy do wczytania n. Następnie pojawi się n  wierszy zawierających 12 początkowych liter ciągu splecionego z 2 lub z 3 ciągów. Wszystkie ciągi składowe posiadają stały krok z własnością przewinięcia.

Specyfikacja wyjścia

Dla każdego z wczytanych ciągów należy wypisać 12 dalszych znaków ciągu.

Przykładowe dane wejściowe

2
AZTAYRAXOAWN
XXYHZRABBLCV

Przykładowe dane wyjściowe

AVLAUJATHASF
DFEPFZGJHTID
Na początek:  podrozdziału   strony 

Problem C - Dopasowywanie wzorca do tekstu

Opis

Raczej prostym zadaniem jest porównanie dwóch łańcuchów znakowych w celu sprawdzenia, czy są one takie same. Jednakże, jeśli jeden z łańcuchów (który nazwiemy "wzorcem") będzie mógł zawierać znaki "zastępcze" - znaki, które pasują do od zera do dowolnej liczby innych znaków - to problem ten stanie się bardziej wyzywający. Na przykład, załóżmy, że porównanie dotyczy 26 liter oraz znaku specjalnego *. Znak * oznacza "dowolną grupę liczącą zero lub więcej znaków". Wzorzec A*B pasuje do łańcuchów AB, AWB, AMNB, ACEFGHUKPWODJGPOIJWLAB, itp. Podobnie, wzorzec A*B*C pasuje do łańcuchów ABC, ABBABC, itp.

Napisz program, który odczyta dowolne pary wzorca i łańcucha znakowego, wypisze je i sprawdzi, czy łańcuch pasuje do wzorca.

Wszystkie znaki (litery od A-Z) muszą pasować do danego wzorca. Jeśli łańcuch pasuje do wzorca, program powinien wypisać odpowiednią wiadomość oraz podać wartość każdego "znaku zastępczego" *. Tj. mając dany wzorzec A*B*B oraz łańcuch ABDDGB, powinien wypisać, że łańcuch pasuje do wzorca, a *1 (pierwszy znak zastępczy) nie pasuje do żadnych znaków, *2 pasował do DDG. Program powinien odczytać dowolną liczbę takich par wzorca i łańcucha znakowego, wypisać je wraz z raportem na temat wyników próby dopasowania wzorca.

Specyfikacja wejścia

Na wejściu program otrzyma ciąg wierszy. W każdym wierszu będą zawarte dwa łańcuchy tekstowe, zbudowane z liter A-Z oraz znaku *. Łańcuchy te będą oddzielone od siebie co najmniej jedną spacją. Jeśli program napotka wiersz pusty, to powinien zakończyć działanie. Pierwszy łańcuch jest wzorcem. Drugi łańcuch jest sprawdzanym tekstem.

Specyfikacja wyjścia

Dla każdej pary wzorzec - łańcuch należy wypisać tę parę, następnie wiadomość, czy tekst pasuje do wzorca, a dalej należy podać do jakich fragmentów łańcucha pasowały kolejne znaki zastępcze (możemy je numerować *1, *2...). Jeśli znakom zastępczym można przydzielić znaki łańcucha na kilka sposobów, to wybierz taki, który pierwszemu znakowi zastępczemu przydziela najmniej znaków z tekstu. Jeśli to nie rozwiązuje problemu, z pozostałych sposobów wybierz taki, który przypisuje najmniej znaków do drugiego znaku zastępczego, itd. Do wzorca musi pasować cały tekst ze wszystkimi znakami od A do Z.

Przykładowe dane wejściowe

A*B*B ABDDGB

Przykładowe dane wyjściowe

A*B*B ABDDGB
STRING MATCHES THE PATTERN
*1 NO CHARACTERS
*2 DDG
Na początek:  podrozdziału   strony 

Problem D - Problem z trójkątem

Opis

Napisz program, który będzie sprawdzał, czy dany punkt znajduje się wewnątrz lub na zewnątrz danego trójkąta.

Specyfikacja wejścia

Pierwsza liczba n  określa ilość punktów do testowania. n  jest liczbą całkowitą i nie przekracza wartości 50. Za n  pojawią się trzy pary liczb zmiennoprzecinkowych, które definiują współrzędne x,y  wierzchołków trójkąta. Następnie wystąpi n  par liczb zmiennoprzecinkowych, które określają współrzędne x,y  punktów do sprawdzenia w programie. Żaden z tych punktów nie będzie leżał na boku trójkąta.

Specyfikacja wyjścia

Dla każdego z n  punktów program powinien wypisać współrzędne tego punktu i słowo INSIDE, jeśli dany punkt jest wewnątrz trójkąta, lub OUTSIDE, w przypadku przeciwnym.

Przykładowe dane wejściowe

25
1.00 4.50
3.50 -3.50
-4.00 -5.00
-2.61 -0.66
-0.92 -3.46
-4.00 2.67
-0.29 -1.17
3.82 -1.23
2.09 -0.69
-4.36 4.84
-3.88 2.80
3.58 -2.48
-0.91 -1.50
-4.29 -1.52
3.65 4.99
4.70 4.08
-4.69 -2.61
1.85 -3.70
-3.82 3.00
-0.28 -1.31
-0.19 -3.97
0.55 -2.19
-1.58 4.07
-4.19 -4.76
-1.34 -4.24
-2.53 -1.65
1.96 -2.67
-4.22 -0.94

Przykładowe dane wyjściowe

  -2.61   -0.66  OUTSIDE
  -0.92   -3.46  INSIDE
  -4,00    2.67  OUTSIDE
  -0.29   -1.17  INSIDE
   3.82   -1.23  OUTSIDE
   2.09   -0.69  INSIDE
  -4.36    4.84  OUTSIDE
  -3.88    2.80  OUTSIDE
   3.58   -2.48  OUTSIDE
  -0.91   -1.50  INSIDE
  -4.29   -1.52  OUTSIDE
   3.65    4.99  OUTSIDE
   4.70    4.08  OUTSIDE
  -4.69   -2.61  OUTSIDE
   1.85   -3.70  INSIDE
  -3.82    3.00  OUTSIDE
  -0.28   -1.31  INSIDE
  -0.19   -3.97  INSIDE
   0.55   -2.19  INSIDE
  -1.58    4.07  OUTSIDE
  -4.19   -4.76  OUTSIDE
  -1.34   -4.24  INSIDE
  -2.53   -1.65  OUTSIDE
   1.96   -2.67  INSIDE
  -4.22   -0.94  OUTSIDE
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.