Polish version    English version  
  Historia OI -> III OI 1995/1996 -> 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
IV OI 1996/1997
III OI 1995/1996
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
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
III Olimpiada Informatyczna 1995/96

Zadanie: NIE
Autor: Wojciech Rytter
Nie atakujące się skoczki

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

Skoczek jest figurą, która atakuje pola na szachownicy zgodnie z rysunkiem 1.

rysunek objaśniający, jak atakuje skoczek szachowy
Rysunek 1: Skoczek umieszczony w polu S atakuje pola oznaczone przez x.

Dana jest szachownica o rozmiarach 3 * n - mająca 3 wiersze i n kolumn, gdzie 1 <= n <= 100 - oraz zbiór Z pól na tej szachownicy. Wiersze na szachownicy są ponumerowane od góry do dołu liczbami od 1 do 3, a kolumny od lewej do prawej liczbami od 1 do n.

Na szachownicy wolno rozmieszczać skoczki tylko na polach nie należących do Z oraz tak, aby żadne dwa nie atakowały się nawzajem.

Zakładamy, że w każdej kolumnie co najwyżej jedno pole należy do Z. Zbiór Z można więc opisać w postaci ciągu: k1, k2, ... , kn, gdzie ki należy do {0, 1, 2, 3}. Wartość ki = 0 oznacza, że żadne pole w i-tej kolumnie nie należy do Z, zaś wartość ki > 0 jest numerem wiersza jedynego pola w tej kolumnie, które należy do Z.

Zadanie

Ułóż program, który:
  • wczytuje z pliku tekstowego NIE.IN liczbę kolumn na szachownicy n oraz opis zbioru pól Z,
  • znajduje maksymalną liczbę skoczków M, które można ustawić na szachownicy zgodnie z podanymi zasadami oraz liczbę L wszystkich takich ustawień M skoczków,
  • zapisuje wyniki w pliku tekstowym NIE.OUT.

Wejście

W pierwszym wierszu pliku tekstowego NIE.IN jest zapisana jedna liczba całkowita dodatnia n <= 100. Jest to liczba kolumn szachownicy.
W każdym z kolejnych n wierszy jest zapisana jedna liczba ze zbioru {0, 1, 2, 3}. Są to kolejne wyrazy ciągu będącego opisem zbioru pól Z.

Wyjście

W pliku tekstowym NIE.OUT należy zapisać dwie liczby całkowite M i L oddzielone odstępem.

Przykład

Dla pliku NIE.IN:
2
1
0
 
w pliku NIE.OUT należy zapisać:
4 2

Twój program powinien szukać pliku NIE.IN w katalogu bieżącym i tworzyć plik NIE.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę NIE.???, 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 NIE.EXE.




Wersja do druku