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 (x₁, y₁), (x₂, y₂), Twój program powinien wywołać procedurę niestabilna (x₁, y₁, x₂, y₂). 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)