Runda 4: Zagnieżdżone fory
27.10.2009 - Przemysław Uznański
Limit czasowy: 30 sekund Paweł wymyślił ciekawy algorytm na konferencję naukową. Niestety, nie jest w stanie oszacować jego złożoności — złożoność to liczba elementarnych operacji, jakie wykona algorytm w zależności od rozmiaru danych wejściowych. W tym przypadku rozmiar danych wejściowych to pojedyńcza zmienna całkowita - n.
Algorytm jest następującej postaci:
for (z1 = s1; z1 < k1; ++z1){ for (z2 = s2; z2 < k2; ++z2){ ... for (zt = st; zt < kt; zt++){ elementarna_operacja; } ... } }
WejścieW pierwszej linii wejścia znajduje się liczba naturalna k (1<=k<=20), oznaczająca liczbę testów. Opis pojedyńczego testu ma następującą postać: W pierwszej linii testu znajduje się liczba naturalna t (1<=t<=18), oznaczająca liczbę zagnieżdżonych forów. W t kolejnych liniach, występują dwa opisy wartości, najpierw startowej, potem końcowej. Opisują one od jakiej do jakiej wartości przebiega zmienna zadeklarowana w danej pętli. Opis pojedyńczej wartości, dla zmiennej zadeklarowanej w i-tej pętli, jest postaci: "0", lub "n", lub "v" i następująca zaraz po niej (bez spacji) liczba całkowita p (1<=p<i) . "0" oznacza wartość 0, "n" oznacza zmienną będącą parametrem programu, "v"+k oznacza k-tą zmienną (zadeklarowaną w k-tej pętli).
for (z1 = 0; z1 < n; ++z1){ for (z2 = 0; z2 < z1; ++z2){ for (z3 = 0; z3 < z2; ++z3){ elementarna_operacja; } } }
zostanie zakodowany jako:
Wyjście
Dla każdego testu w osobnej linii należy wypisać odpowiedź. Jako, że odpowiedzią jest wielomian stopnia co najwyżej t, to dla każdego testu program powinien wypisać w jednej linii t+1 liczb wymiernych — kolejne współczynniki wielomianu, w porządku od najmniej do najbardziej znaczących. Kolejne współczynniki powinny być oddzielone pojedyńczą spacją. Każdy współczynnik wielomianu powinien być wypisany w postaci "licznik/mianownik", gdzie licznik i mianownik są całkowite, względnie pierwsze oraz mianownik jest niezerowy.
PrzykładDla danych wejściowych:
1 3 0 n 0 v1 0 v2
poprawną odpowiedzią jest:
0/1 1/3 -1/2 1/6
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto. |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com