FRAKTAL - konkurs programistyczny

Twoim zadaniem będzie napisanie prostego programu komputerowego umożliwiającego symulowanie przebiegu epidemii. Ogólnie rzecz ujmując, będzie on wczytywał ze standardowego wejścia różne zdarzenia, np. ruchy ludzi, a także polecenia do wykonania, np. wyświetlenie informacji o liczbie osób zarażonych. Poniżej przedstawiona jest szczegółowa specyfikacja tego programu. Dostępne są również przykładowe testy do pobrania (archiwum .zip).

• Rozpoczęcie symulacji
  

  START <n> <m> <WALL | BORDER | GLUE> <t>

  Rozpoczynamy lub kontynuujemy symulację na planszy o wymiarach n wierszy na m kolumn (0 < n * m ≤ 10⁸). Określamy sposób traktowania wyjścia osoby poza planszę (tzn. na pola, których choć jedna współrzędna jest ujemna lub pola o odpowiednich współrzędnych większych bądź równych n i m) jako:
  1. WALL, epidemiologicznie odpowiadający kordonowi sanitarnemu, kiedy próba wyjścia poza planszę (patrz: polecenie MOVE) jest niemożliwa więc taki ruch ignorujemy,
  2. BORDER, epidemiologicznie odpowiadający swobodnej migracji osób do innych obszarów, kiedy próba wyjścia poza planszę odpowiada usunięciu danej jednostki z symulacji,
  3. GLUE, odpowiadający szachownicy "nałożonej" na sferę, gdy wyjście poza planszę prowadzi do pojawienia się osoby na przeciwległym krańcu planszy.
  Ponadto zakładamy, że po spotkaniu się osoby zarażającej i osób zdrowych, osoby zdrowe zostają zarażone i zaczną zarażać innych po t (0 < t < 100) krokach symulacji. Polecenie START może zostać wykonane wielokrotnie, tzn. w czasie symulacji zmianie może ulec rozmiar planszy oraz działanie jej granic (np. wskutek wprowadzenia kwarantanny ludzie nie będą mogli opuścić osiedla), a także (np. w wyniku mutacji patogenu) zaraza może szybciej lub wolniej roznosić się między ludźmi. W tym drugim przypadku zakładamy, że aktualizacja parametru t dotyczy ewentualnych przyszłych zachorowań. Jeżeli polecenie START nie zostało jeszcze wykonane, należy zignorować wszystkie polecenia inne niż zapytania (QUERY). Jeżeli ponowne wykonanie polecenia START spowoduje, iż pewne osoby znajdą się poza obszarem symulacji, należy je usunąć (patrz: polecenie DELETE).

• Zatrzymanie symulacji
  

  STOP

  Czyścimy planszę wraz ze wszystkimi danymi dotyczącymi osób uczestniczących w symulacji, a także zapominamy ewentualne parametry symulacji wprowadzone przy użyciu polecenia START. Innymi słowy, usuwamy wszystkie osoby, a także przerywamy symulację.

• Wyczyszczenie planszy
  

  CLEAR

  Czyścimy planszę wraz ze wszystkimi danymi dotyczącymi osób uczestniczących w symulacji, ale nie zapominamy danych wczytanych poleceniem START. Innymi słowy, usuwamy wszystkie osoby, ale nie przerywamy symulacji.

• Dodanie osoby
  

  NEW <x>, <y> <FINE | ILL | CONTAGIOUS> <id> [CONTAGIOUS AFTER <t>]

  Na planszy, w pozycji (x, y) (0 ≤ x, y ≤ 10⁸), gdzie x oznacza wiersz, a y – kolumnę, staramy się wprowadzić nową osobę o unikatowym (pośród obecnych w symulacji w danej chwili), będącym ciągiem alfanumerycznym zawierającym od jednego do dziesięciu znaków alfanumerycznych ID id. Osoba ta może być zdrowa (FINE) lub nie, przy czym rozróżniamy osoby zarażające innych (CONTAGIOUS) od pozostałych chorych (ILL). W ostatnim przypadku możliwe jest podanie parametru t (0 < t < 100) określającego, po jakim czasie osoba ta zacznie zarażać innych. Jeżeli parametr ten nie zostanie podany, należy skorzystać z wartości wprowadzonej poleceniem START. Jeżeli niemożliwe jest umieszczenie osoby we wskazanej pozycji, gdyż znalazłby się poza planszą, należy zignorować polecenie NEW. Kilka osób może zajmować tę samą pozycję na planszy. Jeżeli na danej pozycji znajdą się osoby zdrowe (FINE) oraz osoby chore zakażające innych (CONTAGIOUS), do infekcji dochodzi natychmiast, tzn. stan osób zdrowych zmienia się na ILL. Po upływie czasu określonego w poleceniu START, stan ILL przejdzie w CONTAGIOUS. Ponowne wykonanie polecenia START nie wpłynie na pozostały czas przejścia między tymi stanami w przypadku osób, które już są zarażone (ILL). Wpłynie jednak na czas w przypadku ewentualnych przyszłych infekcji. Niedopuszczalne jest "nadkażenie" – osoba zarażona (ILL) nie może zarazić się ponownie w wyniku kontaktu z osobą zarażającą (CONTAGIOUS). Takie przypadki należy zignorować.

• Usunięcie osoby
  

  DELETE <id>

  Osoba o unikatowym ID id zostaje usunięta z symulacji, tym samym zwalniając zajęte ID dla ewentualnych przyszłych osób wprowadzonych poleceniem NEW. Jeżeli polecenie zostanie wykonane z nieistniejącym w danej chwili ID, należy je zignorować.

• Przemieszczenie osoby
  

  MOVE <id> <UP | DOWN | LEFT | RIGHT>

  Osoba o unikatowym ID id wykona ruch w jednym z czterech możliwych kierunków (UP, DOWN, LEFT, RIGHT), o ile jest to możliwe. Jeżeli ruch zostanie wykonany, a choć jedna osoba na docelowym polu jest zakażona oraz może już zarażać innych, czyni to natychmiast. (Więcej informacji o zarażaniu znajdziesz w opisie polecenia NEW). Jeżeli ruch prowadzi do wyjścia poza planszę, którą utworzono podając parametr GLUE, należy przenieść poruszającą się osobę na przeciwległy koniec planszy. Parametr BORDER wymusza usunięcie osoby z symulacji tak, jak robi się to przy użyciu polecenia DELETE. (Więcej informacji na temat parametrów WALL, BORDER oraz GLUE przedstawiono opisując polecenie START).

• Zainfekowanie osoby
  

  INFECT <id> [CONTAGIOUS AFTER <t>]

  Osoba o unikatowym ID id została zainfekowana bez udziału osób postronnych (np. zjadła skażoną żywność), przy czym zdolność do zarażania innych zyska po czasie t (0 < t < 100) kroków symulacji. Sposób wprowadzenia i interpretacji opcjonalnego parametru t jest identyczny jak w przypadku polecenia NEW. Polecenie zastosowane wobec osób chorych lub nieistniejących należy zignorować.

• Zapytanie o osobę
  

  QUERY <id>

  Pytamy o stan zdrowia osoby o unikatowym ID id. Zwracamy jedną z odpowiedzi:
  1. FINE, gdy osoba jest zdrowa,
  2. ILL, gdy jest zakażona, ale jeszcze nie zaraża,
  3. INFECTS, gdy jest zakażona i już zaraża,
  4. ???, gdy na chwilę obecną osoba o wczytanym ID nie istnieje.
  Jeżeli osoba istnieje, odpowiedź tę należy poprzedzić wskazaniem jej pozycji. Wyjątkiem jest przypadek, gdy symulacja nie jest aktywna, tzn. nie zostało wykonane polecenie START lub wykonano polecenie STOP, po którym nie nastąpiło polecenie START. W takiej sytuacji należy wyświetlić napis: "Not started yet!".

• Zapytanie ogólne
  

  QUERY

  Pytamy o stan zdrowia każdej osoby na planszy. Odpowiedzią jest napis postaci: "FINE: <liczba osób zdrowych> ILL: <liczba osób chorych, ale nie zarażających> INFECTS: <liczba osób zarażających>". Wyjątkiem jest przypadek, gdy symulacja nie jest aktywna, tzn. nie zostało wykonane polecenie START lub wykonano polecenie STOP, po którym nie nastąpiło polecenie START. W takiej sytuacji należy wyświetlić napis: "Not started yet!".

• Zapytanie o pozycję
  

  QUERY <x>, <y>

  Pytamy o stan zdrowia każdej osoby znajdującej się na pozycji (x, y) (0 ≤ x, y ≤ 10⁸), gdzie x oznacza wiersz, a y – kolumnę. Odpowiedzią jest napis postaci: "FINE: <liczba osób zdrowych> ILL: <liczba osób chorych, ale nie zarażających> INFECTS: <liczba osób zarażających>". Wyjątkiem jest przypadek, gdy żadna osoba nie przebywa na wskazanej pozycji, kiedy to należy wyświetlić napis: "Empty!". Wyjątkiem jest również przypadek, gdy symulacja nie jest aktywna, tzn. nie zostało wykonane polecenie START lub wykonano polecenie STOP, po którym nie nastąpiło polecenie START. W takiej sytuacji należy wyświetlić napis: "Not started yet!". Jeżeli zaszły oba przypadki jednocześnie, należy wyświetlić napis: "Not started yet!".

• Komentarz
  

  #[treść komentarza]

  Komentarz, który bez zmian należy wyświetlić na wyjściu. Komentarz zaczyna się od znaku '#', po którym wystąpi ciąg utworzony z liter alfabetu angielskiego, cyfr, znaków interpunkcyjnych oraz spacji.

Wejście

W pierwszej linii wejścia liczby n oraz m (0 < n * m ≤ 10⁸). Następnie, w kolejnych liniach, podane będą zdarzenia lub zapytania w formacie zgodnym ze specyfikacją. Przyjmujemy, że każda linia wejścia to jeden kolejny krok symulacji, za wyjątkiem linii będącej komentarzem. Innymi słowy, kolejny krok upływa po kolejnym znaku końca linii, o ile znak ten nie kończy polecenia zaczynającego się od znaku "#". Długość żadnego komentarza nie przekracza 200 znaków, a liczba linii do przetworzenia jest nie większa niż 10⁵.

Wyjście

Na wyjściu, w oddzielnych liniach, należy wyświetlać kolejne komunikaty zgodnie ze specyfikacją przedstawioną w treści zadania. W zadaniu włączony jest sędzia dokładny – nadmiarowe lub pominięte znaki, w tym znaki białe, poskutkują odrzuceniem zgłoszonego rozwiązania. Każda linia wyjścia, w tym ostatnia, musi kończyć się znakiem nowej linii (\n).

Przykład

#Uwaga na biale znaki 
QUERY
START 4 8 GLUE 5
QUERY Alek
QUERY 100, 100
NEW 10, 10 ILL Alicja6
QUERY
NEW 0, 0 ILL Alicja
MOVE Alicja LEFT
QUERY Alicja
MOVE Alicja DOWN
QUERY Alicja
QUERY
NEW 3, 7 FINE Adam
QUERY Alicja
QUERY Adam
QUERY 3, 7
#
#
DELETE Alicja
CLEAR
NEW 2, 2 ILL Alicja CONTAGIOUS AFTER 3
NEW 0, 0 ILL Felicja CONTAGIOUS AFTER 3
START 1 1 BORDER 999
QUERY
QUERY 0, 0
INFECT Damian CONTAGIOUS AFTER 99
STOP
QUERY

#Uwaga na biale znaki 
Not started yet!
???
Empty!
FINE: 0 ILL: 0 INFECTS: 0
0 7 ILL
3 7 ILL
FINE: 0 ILL: 0 INFECTS: 1
3 7 INFECTS
3 7 ILL
FINE: 0 ILL: 1 INFECTS: 1
#
#
FINE: 0 ILL: 1 INFECTS: 0
FINE: 0 ILL: 0 INFECTS: 1
Not started yet!