Polish version    English version  
  Historia OI -> X OI 2002/2003 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
X Olimpiada Informatyczna 2002/2003

Zadanie: kry
Autor: Marcin Stefaniak
Kryształ

Zawody III stopnia, dzień drugi  
Plik źródłowy: kry.xxx (xxx=pas,c,cpp)

Alternatywne formaty: PostScript | PDF

Bajtoccy fizycy prowadzą badania nad kryształami bitanium. Atomy w kryształach bitanium tworzą sieć w kształcie kwadratowej kraty o prostopadłych osiach. Kryształy te mają dwie prostopadłe osie. Każdy atom w krysztale wiruje "w miejscu" wokół jednej z osi kryształu, w jedną lub w drugą stronę. Jako że mamy dwie osie i dwa kierunki wirowania, każdy atom może być w danej chwili w jednym z czterech stanów.

Jeśli dwa atomy wirują wzdłuż tej samej osi, ale w przeciwnych kierunkach, to mówimy, że wirują one przeciwnie. Dwa atomy sąsiadujące ze sobą wzdłuż osi kryształu lub po przekątnej mogą tworzyc parę stabilną lub niestabilną. Jeśli takie atomy wirują przeciwnie, to mówimy, że tworzą parę niestabilną. W przeciwnym wypadku mówimy, że tworzą parę stabilną.

Bajtoccy fizycy potrafią tak umieścić kwadratowy kryształ bitanium w spolaryzowanym polu bitomagnetycznym, że atomy na brzegach kryształu tworzą pary stabilne i nie zmieniają swoich stanów, a ponadto atomy położone na brzegu kryształu, symetrycznie względem jego środka, wirują przeciwnie. Teoria mówi, że w takim krysztale w każdej chwili musi się gdzieś znajdować niestabilna para atomów. Nie wiadomo tylko gdzie, ponieważ wewnątrz kryształu atomy bezustannie zmieniają swoje stany.

Ostatnio opracowano technikę "zamrażania" atomów w krysztale. Zamrożony atom nie zmienia już swojego stanu. Nie da się przewidzieć w jakim stanie zostanie zamrożony, ale można ten stan poznać po jego zamrożeniu. Umieszczenie kryształu w polu bitomagnetycznym zamraża atomy znajdujące się na brzegu kryształu. Dodatkowo można zamrozić pewne atomy w krysztale, niestety nie wszystkie. W kwadratowym krysztale bitanium o wymiarach n * n atomów można zamrozić dodatkowo (poza brzegiem) co najwyżej 3n atomów.

Zadanie

Napisz program sterujący aparaturą w laboratorium. Twój program powinien:

  • pobrać z aparatury informacje o stanach atomów na brzegu kryształu,
  • sterować zamrażaniem atomów i badać stany zamrożonych atomów,
  • doprowadzić do zamrożenia niestabilnej pary atomów i podać współrzędne takiej pary.

Na potrzeby tego zadania, otrzymasz uproszczony moduł sterujący aparaturą, który pozwoli Ci przetestować swoje rozwiązanie.

Opis interfejsu aparatury

Twój program powinien komunikować się ze "światem zewnętrznym" tylko i wyłacznie poprzez wywołania funkcji i procedur modułu (krysztal.pas w Pascalu, krysztal.h w C/C++). Oznacza to, że nie wolno otwierać żadnych plików ani też korzystać ze standardowych strumieni wejścia/wyjścia.

        (* Pascal *)
        function rozmiar: integer; 
        function zamroz (x, y : integer) : integer; 
        procedure niestabilna (x1, y1, x2, y2 : integer);
        /* C/C++ */
        int rozmiar(void);
        int zamroz (int x, int y);
        void niestabilna (int x1, int y1, int x2, int y2);

Twój program powinien najpierw uruchomić aparaturę wywołując funkcję rozmiar, której wynikiem jest rozmiar kryształu n, 3 <= n <= 10000. Badany kryształ ma wymiary n * n atomów. Atomy w krysztale identyfikujemy za pomocą współrzędnych całkowitych (x, y), 1 <= x, y <= n.

Wywołanie funkcji zamroz(x, y) (dla 1 <= x, y <= n) powoduje zamrożenie atomu o współrzędnych (x, y), a wynikiem funkcji jest stan zamrożonego atomu. Stany atomów są reprezentowane przez liczby -2, -1, 1 lub 2. Wartość bezwzględna liczby określa oś wokół której wiruje atom, a jej znak określa kierunek wirowania atomu. (Zwróć uwagę, że nie ma znaczenia, która oś jest reprezentowana przez liczby 1 i -1, a która przez 2 i -2, oraz który kierunek wirowania jest reprezentowany przez liczby ujemne, a który przez dodatnie.) Atomy na brzegu kryształu w momencie uruchomienia aparatury są już zamrożone. Zamrożenie już zamrożonego atomu nie zmienia jego stanu. Można co najwyżej 3n razy wywołać funkcję zamroz dla atomów położonych we wnętrzu kryształu. Dla atomów położonych na brzegu kryształu można ją wywoływać dowolnie wiele razy.

Po wyznaczeniu niestabilnej pary (x1, y1), (x2, y2), Twój program powinien wywołać procedurę niestabilna (x1, y1, x2, y2). Wywołanie tej procedury kończy działanie programu. Jeśli w krysztale jest wiele par niestabilnych atomów, to Twój program powinien wskazać jedną z nich.

Przykład

Przykładowa interakcja z programem może wyglądać następująco:

        rozmiar() = 5
        zamroz (1, 1) = 1
        zamroz (1, 2) = 1
        zamroz (1, 3) = 1
        zamroz (1, 4) = 1
        zamroz (1, 5) = 2
        zamroz (2, 5) = 2
        zamroz (3, 5) = 2
        zamroz (4, 5) = 2
        zamroz (3, 3) = 2
        zamroz (2, 2) = 1
        zamroz (4, 2) = -1
        zamroz (3, 2) = -2
        niestabilna (3, 2, 3, 3)



Wersja do druku