Polish version    English version  
  Historia OI -> V OI 1997/1998 -> 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
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Terminarz
Statystyki
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
V Olimpiada Informatyczna 1997/98

Zadanie: MAL
Autor: Wojciech Rytter
Pracownia malarska

Zawody I stopnia  
Plik źródłowy: MAL.??? (np. pas, c, cpp)
Plik wykonywalny: MAL.exe
Plik wejściowy: MAL.in
Plik wyjściowy: MAL.out

Pracownia malarska przygotowuje seryjną produkcję obrazów. Obrazy będą wykonywane za pomocą kwadratowych matryc o różnych stopniach. Matryca stopnia i składa się z 2^i wierszy i 2^i kolumn. Na przecięciu pewnych wierszy i pewnych kolumn znajdują się otwory. Matryca stopnia 0 ma jeden otwór. Dla i>0, matryca stopnia i składa się z czterech kwadratów o rozmiarach 2^(i-1)*2^(i-1).

[RYS. NR 1]

Oba prawe kwadraty oraz dolny lewy kwadrat są matrycami stopnia i-1. W górnym lewym kwadracie nie ma żadnych otworów. Obraz otrzymuje się w następujący sposób. Najpierw ustala się trzy nieujemne liczby całkowite n,x,y. Następnie umieszcza się dwie matryce stopnia n jedna na drugiej i górną matryce przesuwa się o x kolumn w prawo i o y wierszy w górę. Tak otrzymany wzorzec zostaje umieszczony na białym płótnie i na wspólną część obu matryc nanosi się żółtą farbę. W efekcie na płótnie pojawią się żółte plamy tylko w tych miejscach, w których w obu matrycach pokrywają się.

Przykład

Przyjrzyj się dwóm matrycom stopnia 2 przedstawionym na rysunku.

[RYS. NR 2]

Górna matryca została przesunięta o 2 kolumny w prawo i o 2 wiersze w górę. W trzech miejscach otwory z obu matryc pokrywają się.

Zadanie

Napisz program, który:

  • Wczytuje z pliku tekstowego MAL.IN stopień obu matryc, oraz współrzędne przesunięcia górnej matrycy
  • Oblicza liczbę żółtych plam na płótnie
  • Zapisuje wynik w pliku tekstowym MAL.OUT
Wejście

Pierwszy wiersz pliku tekstowego MAL.IN zawiera liczbę całkowitą n, 0<=n<=100. Jest to stopień matryc używanych w produkcji obrazów. W drugim wierszu zapisana jest liczba całkowita x, zaś w trzecim wierszu liczba całkowita y, 0<=x.y<=2^n. Liczba x jest liczbą kolumn, a y liczbą wierszy, o które należy przesunąć górną matrycę.

Wyjście

W pierwszym wierszu pliku wyjściowego MAL.OUT należy zapisać liczbę plam na płótnie.

Przykład

Dla pliku wejściowego MAL.IN

2
2
2

poprawnym rozwiązaniem jest plik wyjściowy MAL.OUT

3

Twój program powinien szukać pliku MAL.IN w katalogu bieżącym i tworzyć plik MAL.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę MAL.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku MAL.EXE





Wersja do druku