Bogus Airlines (BA) ma zamiar obsługiwać do 30 miast. Zna następującą informację na temat planowania lotu: Czas przelotu pomiędzy dwoma miastami jest równy odległości pomiędzy nimi podzielonej przez 500 mph (mil na godzinę) plus 30 minut. W każdym locie należy uwzględnić 30 minut postoju na ziemi przed startem i 30 minut postoju na ziemi po lądowaniu. Dlatego, na przykład, 1000 milowy lot musi zostać zaplanowany jako lot trwający trzy i pół godziny (1000/500 + 0,5 + 0,5 + 0,5). Musi upłynąć co najmniej jedna godzina  w węźle pomiędzy stykającymi się lotami. Jednakże nie ma potrzeby doliczania jednej godziny pomiędzy porannym lotem z określonego miasta a lotem popołudniowym  z powrotem do tego samego miasta; zakładamy, iż żaden pasażer nie wziąłby tych dwóch lotów. Żaden lot nie może się rozpocząć przed 8:00 rano, ani zakończyć po 10:00 wieczorem. Wybór jakiegoś miasta na węzeł zawsze pozwoli dowolnemu pasażerowi na podróż z dowolnego miasta do węzła, a następnie do dowolnego innego miasta w ciągu jednego dnia (tj. pomiędzy 8:00 a 22:00). Możesz również założyć, że lotnisko jest w stanie obsłużyć dowolną liczbę jednoczesnych przylotów i odlotów.

Na potrzeby tego problemu wolno ci swobodnie interpretować słowa "rano" i "popołudniu". Na przykład "popołudniowy" lot może być zaplanowany przed południem lub po 6:00 popołudniu pod warunkiem spełnienia pozostałych warunków lotu przedstawionych wyżej.

Otrzymasz pięć zestawów danych w pojedynczym pliku. Dla prostoty miejsca będą podane jako współrzędna na płaszczyźnie (nie będzie potrzebna geometria sferyczna). Wysokość i szerokość geograficzna będą wyrażone jako liczby całkowite z zakresu od 0 do 9999, a jednostką miary jest mila. Odległości pomiędzy miastami można policzyć za pomocą normalnej funkcji odległości euklidesowej. Pierwszy wiersz każdego zestawu danych składa się z dwucyfrowej liczby na dwóch pierwszych pozycjach znakowych wiersza; jest to liczba miast. Reszta zestawu danych składa się z wierszy, z których każdy opisuje jedno miasto. Pierwsze osiem znaków wiersza zawiera nazwę miasta (tylko duże litery, cyfry i spacje, wyrównanie lewostronne). Bezpośrednio za tą nazwą znajdują się dwa pięcioznakowe pola, które przechowują odpowiednio wysokość i szerokość geograficzną miasta ; wartości te są wyrównanymi prawostronnie liczbami całkowitymi. Każdy kolejny zestaw danych następuje tuż za swoim poprzednikiem.

Dla każdego zestawu danych twój program powinien zidentyfikować każde miasto, które mogłoby być węzłem, co oznacza, że pozwalałoby ono na zaplanowanie lotów wg opisu podanego powyżej. Następnie twój program musi zidentyfikować miasto, które byłoby najlepszym węzłem centralnym. Takie miasto musiałoby pozwalać na najkrótszy czas całkowity od pierwszego lotu rano (o 8:00) do końca ostatniego lotu popołudniowego (oczywiście z uwzględnieniem czasów postoju na ziemi opisanych powyżej). Jeśli więcej niż jedno miasto jest równie dobre, zidentyfikuj je wszystkie. Twój program musi również wydrukować liczbę możliwych węzłów oraz liczbę najlepszych węzłów dla każdego zestawu danych. Przykładowe dane wejściowe i odpowiadające im dane wyjściowe powinny pomóc ci zrozumieć, co masz zrobić.

Przykładowe dane wejściowe

06
CITY 1    200  400
CITY 2    100  300
CITY 3    100  200
CITY 4    200  100
CITY 5    300  200
CITY 6    300  300

Odpowiadające im dane wyjściowe

6 POSSIBLE HUB(S) MAY BE AT
CITY 1
CITY 2
CITY 3
CITY 4
CITY 5
CITY 6

4 BEST HUB(S) AT
CITY 2
CITY 3
CITY 5
CITY 6

Baza danych będzie opisywała, kto oraz jakie przedmioty znajdują się w każdym z pokojów pewnego domu. Każda osoba, obiekt i pokój posiadają nazwy zbudowane z pojedynczych słów zapisanych dużymi literami, o długości maksymalnie dziesięciu znaków. W domu znajduje się dokładnie osiem pokoi, a każdy pokój zawiera dokładnie jedną osobę i jeden obiekt. Baza danych będzie opisana w pierwszych ośmiu wierszach danych. Każdy z tych wierszy zawiera nazwę pokoju wyrównaną lewostronnie w pierwszych dziesięciu znakach wiersza, nazwisko osoby wyrównane lewostronnie w następnych dziesięciu znakach oraz nazwę obiektu również wyrównana lewostronnie w następnych dziesięciu znakach. Na przykład:

LIVINGROOMSMITH     PIANO     
BATHROOM  JONES     TOOTHBRUSH

Język zapytań zezwala tylko na cztery rodzaje pytań:

WHO IS IN THE <pokój>?
WHAT IS IN THE <pokój>?
WHERE IS <osoba>?
WHERE IS THE <obiekt>?

Pytania będą wyrażane dużymi literami, po jednym w wierszu. Twój program musi odczytać pytanie, wydrukować jeden pusty wiersz, wydrukować to pytanie w następnym wierszu, a następnie w kolejnym wierszu wydrukować jedno słowo odpowiedzi lub wiadomość o błędzie. Jeśli pytanie zostało ułożone nieprawidłowo, to wydrukuj wiadomość ERRONEOUS QUESTION. Jeśli poprawnie ułożone pytanie odwołuje się do pokoju, osoby lub obiektu nieobecnych w bazie danych, wydrukuj wiadomość UNKNOWN.

Odpowiedzi pojawiają się w osobnym wierszu zaraz pod pytaniem. Pytania rozpoczną się od dziewiątego wiersza wejściowego, po ośmiu wierszach bazy danych. W pytaniach słowa będą rozdzielone przynajmniej jedną spacją, a spacje mogą wystąpić przed pierwszym słowem lub przed pytajnikiem. Słowa pytań nie będą posiadały więcej niż dziesięć liter. Pytajnik musi być obecny; inaczej pytanie jest błędne. Znaki występujące po pytajniku powinny zostać zignorowane i nie mają być drukowane razem z pytaniem. Liczba wierszy pytań będzie dowolna. Wiersze będą zakończone znacznikiem końca pliku.

Na przykład, dla bazy danych zawierającej wartości z dwóch wierszy podanych powyżej:

WHERE IS JONES?
BATHROOM

   WHAT   IS   IN   THE   LIVINGROOM   ?
PIANO

WHAT IS IN THE VARDAGSRUM?
UNKNOWN

WHO ATE MY WOMBAT?
ERRONEOUS QUESTION

Napisz program, który tworzy raport zawierający wszystkie wiadomości w tym pliku. Raport będzie się składał z nagłówka, za którym wystąpi ciąg raportów klientów pojawiających się w kolejności rosnącej wg numeru konta. Nagłówek i pierwszy raport klienta będą rozdzielone dwoma pustymi wierszami; raporty klientów będą rozdzielone jednym pustym wierszem. Nagłówek będzie się składał z wiersza pokazanego poniżej, w którym <date> zostanie zastąpione datą otrzymania wiadomości.

Midnight Message Service -- messages received on <date>

Raporty klienta będą składały się z wierszy jeden pod drugim. Pierwszy wiersz każdego raportu klienta będzie zawierał numer konta klienta. Pozostałe wiersze będą wymieniać wiadomości klienta, po jednej na wiersz, w kolejności otrzymywania.

Wiadomość 'ABCDEFGHIJKLMNOPQRSTUVWXYZ .,()-' jest zaszyfrowana jako 0,  255,  3855,  13107,  -10923,  -1,  127,  1927,   6553,  10922,  -8193,  -8193,  -16384,  -8193,  -8193.

Procedura szyfrowania jest zilustrowana poniżej:

blok 1 -->  A B C D E F G H I J K L M N O
    bit 1   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  daje 0
    bit 2   0 0 0 0 0 0 0 1 1 1 1 1 1 1 1  daje 255
    bit 3   0 0 0 1 1 1 1 0 0 0 0 1 1 1 1  daje 3855
    bit 4   0 1 1 0 0 1 1 0 0 1 1 0 0 1 1  daje 13107
    bit 5   1 0 1 0 1 0 1 0 1 0 1 0 1 0 1  daje -10923

blok 1  --> P Q R S T U V W X Y Z   . , (
    bit 1   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -1
    bit 2   0 0 0 0 0 0 0 0 1 1 1 1 1 1 1  daje 127
    bit 3   0 0 0 0 1 1 1 1 0 0 0 0 1 1 1  daje 1927
    bit 4   0 0 1 1 0 0 1 1 0 0 1 1 0 0 1  daje 6553
    bit 5   0 1 0 1 0 1 0 1 0 1 0 1 0 1 0  daje 10922

blok 3 -->  ) -
    bit 1   1 0 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -8193
    bit 2   1 0 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -8193
    bit 3   1 0 0 0 0 0 0 0 0 0 0 0 0 0 0  daje -16384
    bit 4   1 0 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -8193
    bit 5   1 0 1 1 1 1 1 1 1 1 1 1 1 1 1  daje -8193

Z podanego przykładu można wywnioskować, że każdy znak jest reprezentowany przez unikalny kod 5-bitowy. Co więcej, pierwsza z pięciu liczb całkowitych reprezentujących blok pochodzi z interpretacji pierwszych bitów każdego znaku w bloku jako 15-bitowej liczby całkowitej U2. 15 drugich bitów łączone jest w podobny sposób, aby utworzyć drugą liczbę całkowitą, itd.

Plik danych dla twojego programu jest w dwóch częściach. Pierwsza część jest ciągiem jednego lub więcej wierszy, każdy po 16 znaków w pierwszych 16 kolumnach. Dla każdego wiersza zapisz ciąg pięciu liczb całkowitych generowanych przez szyfrowanie pierwszych 15 znaków. Zapisuj te liczby kodu we właściwej kolejności w pojedynczym wierszu wyjściowym.  Jeśli szesnasty znak jest znakiem plus ("+"), to ma być zaszyfrowany następny wiersz, inaczej faza szyfrowania kończy się.

Reszta pliku składa się z zera lub więcej wierszy, każdy zawierający pięć liczb całkowitych pochodzących z kodowania bloku tekstu wiadomości. Liczby te są wyrównane prawostronnie w pięciu kolejnych polach siedmioznakowych. Możesz założyć, że pomiędzy sąsiadującymi liczbami jest co najmniej jedna spacja. Dla każdego z tych wierszy zapisz rozszyfrowany blok tekstu w pojedynczym wierszu.

Wygenerowane obrazki mają być zbudowane ze znaków zawartych w wiadomości klienta i wyświetlone w matrycy o formacie 24 wiersze na 64 kolumny. Wiadomość może posiadać maksymalnie 32 znaki długości bez spacji i ma być wstawiona cyklicznie do matrycy wiersz po wierszu aż do wypełnienia całego obszaru. Opis obrazka składa się z listy liczb oznaczających liczbę pozycji wyliczanych wiersz po wierszu, które mają zostać na przemian maskowane spacjami lub drukowane jako znaki wiadomości wewnątrz matrycy. Pierwsza liczba w pliku oznacza, że pole to ma zostać wydrukowane jako znaki wiadomości.

Specyfikacja wejścia:

Pojedynczy zestaw danych zawarty w pliku jest zorganizowany następująco:

Specyfikacja wyjścia:

Twój program powinien utworzyć obrazek w matrycy złożonej ze znaków wiadomości i spacji określonych przez plik wejściowy i zapisać wynikową matrycę w pliku. Znaki w tej matrycy mają być zapisane do tego pliku w 24 wierszach po 64 kolumn każdy.

Przykład:

Przykładowy zestaw danych:

BILBO.BAGGINS.FOR.PRESIDENT
    4   56    8   56    4   76   35   29   35   29
   35   45    6   58    6   58    6   58    6   58
    6   58    6   58    6   52   18   46   18   46
   18  244    6   58    6   30    4   24    6   26
    8   56    8   56    4    0

Wyjście wygenerowane przez powyższe dane:

BILB                                                        BAGG
INS.                                                        R.PR
                                                                
            OR.PRESIDENTBILBO.BAGGINS.FOR.PRESI                 
            NTBILBO.BAGGINS.FOR.PRESIDENTBILBO.                 
            GGINS.FOR.PRESIDENTBILBO.BAGGINS.FO                 
                            AGGINS                              
                            BILBO.                              
                            INS.FO                              
                            ESIDEN                              
                            BO.BAG                              
                      BILBO.BAGGINS.FOR.                        
                      INS.FOR.PRESIDENTB                        
                                                                
                                                                
                                                                
                            LBO.BA                              
                            S.FOR.                              
SIDE                        IDENTB                          BILB
O.BA                                                        INS.
FOR.                                                        ESID
                                                                
                                                               
                                                                

Twój program powinien odczytać jako dane kod źródłowy programu w języku Pascal, a następnie zliczyć następujące rzeczy:

1. Całkowitą liczbę wierszy w programie.
2. Liczbę pustych wierszy w programie.
3. Całkowitą liczbę znaków w programie.
4. Liczbę znaków w komentarzach łącznie ze znakami ograniczającymi komentarze.
5. Liczbę znaków białych (spacje) w programie, pomijając znaki białe w komentarzach lub w literałach łańcuchowych.
6. Liczbę pozostałych znaków w programie (bez znaków białych i z pominięciem komentarzy).

Twój program powinien wyświetlić każde z tych zliczeń z odpowiednim opisem.

Poniższa informacja może okazać się pomocna przy odświeżaniu twojej pamięci na temat struktury programów pascalowych. Program posiada swobodny format i wiersze mogą być dowolnie długie lub krótkie. Komentarz rozpoczyna się znakiem {, a kończy znakiem }. Wszystkie znaki pomiędzy tymi dwoma ogranicznikami są częścią komentarza, jak również same ograniczniki. Dla celów tego programu nie pojawią się komentarze zagnieżdżone. Literał łańcuchowy rozpoczyna się i kończy znakiem apostrofu ( ' ). Dwa sąsiednie apostrofy wewnątrz literału są interpretowane jako pojedynczy apostrof,  a nie ogranicznik kończący. Jednakże dla celów zliczania, licz dwa sąsiednie apostrofy jako dwa znaki. Klamry ( { lub } ) wewnątrz literału łańcuchowego nie są ogranicznikami komentarza, jak również apostrof wewnątrz komentarza nie jest ogranicznikiem literału łańcuchowego.

Zestawem danych dla tego problemu jest poprawny program pascalowy. Może być on dowolnie długi, a kończy się znacznikiem końca pliku. Żaden wiersz w zestawie danych nie posiada spacji końcowych. Jeśli wybierzesz rozwiązanie tego problemu, które wstawia spacje końcowe, to musisz je również usunąć. Żaden wiersz w zestawie danych nie przekracza 80 znaków. Nie powinny być w żaden sposób  zliczane znaki kontrolne, jak CR (ang. carriage return), LF (ang. line feed) lub NL (ang. new line). W zestawie danych nie będzie znaków tabulacji. Żadne poprawne zliczenie nie przekroczy maksymalnej wartości liczb całkowitych.

Przykładowe wejście:

program test ( input, output );

  { this is a data set
  }
var
    num  : integer;
    word : packed array [ 1..15 ] of char;
begin
  word := '.:.            ';  { this is a comment }
  for num := 1 to 5 do
      writeln ( 'Number is:', num * 4 : 3 );
  word := '{not a comment}';
end.  { end test }

Odpowiadające mu wyjście:

Total lines               13
Blank lines                1
Total characters         288
Blank characters          60
Comment characters        56
Other characters         172

Każdego dnia ze stacji centralnej B&O wyrusza specjalny transport z zaplanowanym ładunkiem samochodów, które mają być dostarczone do swoich zaplanowanych miejsc przeznaczenia. Każdego dnia może być do 100 samochodów dostarczanych do każdego z miejsc przeznaczenia od stacji centralnej i dostawa może iść do każdej ze stacji. Stacja centralna nie jest miejscem przeznaczenia żadnego samochodu.

Problem, o którego rozwiązanie poprosił cię zarząd B&O, dotyczy zaplanowania dziennych dostaw o minimalnym koszcie trasy dla codziennego pociągu. Minimalny koszt trasy jest zdefiniowany jako suma przebytych mil pomnożona przez liczbę przewożonych samochodów.  Ponieważ liczba samochodów dla każdego z miejsc przeznaczenia oraz liczba miejsc przeznaczenia różni się każdego dnia, konieczne będzie przeliczanie minimalnego kosztu trasy codziennie.

Specyfikacja wejścia:

W pliku znajduje się pojedynczy zestaw danych zorganizowany następująco:

Specyfikacja wyjścia:

Twój program ma określić trasę o minimalnym koszcie dla codziennego pociągu B&O oraz zapisać do pliku ten koszt minimalny oraz trasę do przebycia. Dokładny format dla twojego wyjścia jest pokazany na przykładowym wyjściu.

Przykład:

Przykładowy zestaw danych:

4
   70   50   16   21
    4    5    6    1
    4    4    5
    1    2
    3

Wyjście generowane przez powyższe dane:

Minimal cost is 795 car/miles.

Stop 1 is Station 4
Stop 2 is Station 2
Stop 3 is Station 3
Stop 4 is Station 1

System RSA jest systemem z dwoma kluczami. Klucz publiczny jest znany wszystkim użytkownikom. Następnie każdy indywidualny użytkownik otrzymuje klucz prywatny. Aby wysłać wiadomość, jest ona kodowana przy użyciu klucza publicznego należącego do zamierzonego odbiorcy i przesyłana do niego. Ten z kolei stosuje proces rozszyfrowywania wiadomości używając obu swoich kluczy, publicznego i prywatnego. Główną cechą systemu RSA jest to, iż rozszyfrowanie wiadomości przy użyciu tego samego klucza, którym została ona zaszyfrowana, nie daje oryginalnej wiadomości. W procesie rozszyfrowywania musi być użyty również klucz prywatny.

Masz opracować program implementujący ograniczoną wersję procesu rozszyfrowywania RSA. Stosowane klucze będą zbyt małe, aby zapewnić rozsądną integralność danych, lecz ta metoda jest poprawna.

Plik danych wejściowych jest plikiem tekstowym składającym się z listy zestawów danych, po jednym zestawie na każdy wiersz oryginalnej wiadomości. Każdy zestaw danych jest ciągiem wartości bezznakowych liczb całkowitych, po jednej na wiersz i wyrównanej prawostronnie w pierwszych pięciu kolumnach kolejnych wierszy wejściowych. Pierwsza wartość dla wszystkich zestawów danych z wyjątkiem ostatniego zawiera liczbę wartości w zestawie danych, łącznie z sobą samą. Ostatni zestaw danych składa się tylko z jednego wiersza, zawierającego wartość 0. Dla każdego zestawu danych liczby występujące po pierwszej są zaszyfrowanymi blokami do rozszyfrowania wg opisu podanego poniżej.

Rozszyfrowywanie zaszyfrowanego bloku jest procesem dwustopniowym. Najpierw zaszyfrowany blok, EB, jest dekodowany w blok zakodowany dziesiętnie, DEB, za pomocą przekształcenia,

DEB = ( EB ** DK ) mod EK  ,

gdzie DK jest prywatnym kluczem rozszyfrowania, EK jest kluczem publicznym szyfrowania, a "**" oznacza potęgowanie. Następnie nieujemna liczba dziesiętna DEB jest dekodowana w dwa znaki oryginalnej wiadomości. Kodem ASCII pierwszego znaku jest 31 plus liczba całkowita z zakresu od 0 do 99, której cyfry na pozycji dziesiątek i jedności są odpowiednio cyframi DEB na pozycji tysięcy i setek. Kod ASCII drugiego znaku jest równy 31 plus liczba całkowita z zakresu od 0 do 99, której cyfry na pozycji dziesiątek i jedności są cyframi DEB odpowiednio na pozycjach dziesiątek i jedności. Na przykład, używając prywatnego klucza rozszyfrującego 26787 i publicznego klucza szyfrującego 40753, zaszyfrowany blok 30239 daje dziesiętnie kodowany blok 4734, który następnie jest dekodowany w "NA", ponieważ kod ASCII litery N jest równy 31+47=78, a kod ASCII litery A jest równy 31+34=65.

W celu policzenia DEB=(EB**DK) mod EK bez przekraczania zakresu obliczeniowego komputera można użyć zmodyfikowanej wersji algorytmu "ruskich chłopów":

1. Niech DEB będzie równe 1.
2. Jeśli DK jest nieparzyste, to zmień DEB na (DEB * EB) mod EK.
3. Zmień EB na (EB * EB) mod EK.
4. Zmień DK na część całkowitą z (DK podzielone przez dwa).
5. Jeśli DK jest równe zero, zakończ. Inaczej powtarzaj od kroku 2.

Masz rozszyfrować, złożyć ponownie w całość i wydrukować każdą wiadomość zakodowaną przy pomocy kluczy wspomnianych w tym przykładzie. Zachowaj strukturę wiersza oryginalnej wiadomości. Załóż, iż żaden rozszyfrowany wiersz nie jest dłuższy od 80 znaków.

WSKAZÓWKA: Zauważ, iż DEB jest zawsze mniejsze niż EK. Przy wyborze swojej reprezentacji danych weź pod uwagę to oraz operacje arytmetyczne wymagane w algorytmie podanym powyżej.