Polish version    English version  
  Historia OI -> IX OI 2001/2002 -> 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
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
Statystyki
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
IX Olimpiada Informatyczna 2001/2002

Zadanie: pro
Autor: Marcin Stefaniak
Protokoły

Zawody II stopnia, dzień drugi  
Plik źródłowy: pro.??? (np. pas, c, cpp)
Plik wejściowy: pro.in
Plik wyjściowy: pro.out

Pan Półsieć pracuje w firmie telekomunikacyjnej Bajkotel i jest projektantem protokołów sieciowych. Obecnie zajmuje się on protokołem umożliwiającym przesyłanie danych z jednego komputera do drugiego za pomocą kabla nowej generacji. Kablem takim można przesyłać sygnał o k różnych poziomach napięcia, przy czym napięcie to może się zmieniać co 1/n sekundy (1/n sekundy w trakcie której napięcie musi być stałe nazywamy impulsem). Dane przesyłane są w postaci paczek obejmujących m kolejnych impulsów (czyli przesłanie jednej paczki zajmuje m/n sekund).

Ze względów technicznych, w obrębie każdej paczki napięcie nie może być stałe, lecz co jakiś czas musi się zmieniać. Mówiąc ściślej, nie można przesyłać paczek danych zawierających l kolejnych impulsów o takim samym poziomie napięcia.

Jeżeli protokół umożliwia przesłanie x różnych paczek, to mówimy, że w jednej paczce możemy zakodować log2x bitów informacji. Pan Półsieć zastanawia się, ile bitów informacji można przesłać maksymalnie w ciągu jednej sekundy.

Przykład

Załóżmy, że kablem można przesyłać sygnał o 2 różnych poziomach napięcia (k=2), które oznaczamy 0 i 1. Jeżeli napięcie może się zmieniać 20 razy na sekundę (n=20), paczki obejmują po 4 impulsy (m=4) i w obrębie każdej paczki żadne 3 kolejne impulsy nie mogą mieć takiego samego napięcia (l=3), to nie można przesyłać paczek: 0000, 0001, 1000, 1111, 1110, 0111. Można natomiast przesyłać paczki: 0010, 0011, 0100, 0110, 0101, 1101, 1100, 1011, 1001 i 1010. Ponieważ można przesyłać 10 różnych rodzajów paczek, więc w każdej paczce można zakodować log210 bitów informacji. W ciągu sekundy można przesłać 20/4 = 5 paczek, czyli 5*log210 ~ 16.6096 bitów informacji.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego pro.in liczby k, n, m i l opisujące protokół,
  • obliczy maksymalną liczbę bitów informacji, jakie można przesłać w ciągu sekundy,
  • zapisze w pliku tekstowym pro.out obliczoną liczbę bitów zaokrągloną w dół do najbliższej liczby całkowitej.

Wejście

W pierwszym wierszu pliku tekstowego pro.in zapisane są cztery liczby całkowite, pooddzielane pojedynczymi odstępami:

  • liczba poziomów napięcia k (2 <= k <= 10),
  • częstotliwość impulsów n (1 <= n <= 1000),
  • rozmiar paczki danych m (1 <= m <= 100),
  • liczbę l kolejnych impulsów w paczce, w obrębie których musi nastąpić zmiana napięcia (2 <= l <= m),
Dodatkowo przyjmujemy, że n/m jest liczbą całowitą mniejszą lub równą 10.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu pliku tekstowego pro.out jedną liczbę całkowitą: maksymalną liczbę bitów, jakie można przesłać w ciągu sekundy, zaokrągloną w dół do najbliższej liczby całkowitej.

Przykład

Dla pliku wejściowego pro.in

2 20 4 3

poprawną odpowiedzią jest plik wyjściowy pro.out:

16



Wersja do druku