Runda 4: Zagnieżdżone fory

27.10.2009 - Przemysław Uznański
TrudnośćTrudnośćTrudnośćTrudność

Limit czasowy: 30 sekund
Limit pamięciowy: 32 MB

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;
      }
      ...
   }
}



z to w każdej pętli nowo zadeklarowana zmienna, s i k to w każdej pętli wartości początkowe i końcowe dla tej pętli. Możliwe watości dla zmiennych s i k to 0, n albo jakaś zmienna zadeklarowana w któreś z poprzednich pętli.

Interesuje nas, ile razy zostanie wykonana elementarna operacja w zależności od n. Można pokazać, że ta zależność jest wielomianem o współczynnikach wymiernych.

 

Wejście

W 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).

I tak, program:

 

for (z1 = 0; z1 < n; ++z1){
   for (z2 = 0; z2 < z1; ++z2){
      for (z3 = 0; z3 < z2; ++z3){
         elementarna_operacja;
      }
   }
}

 

zostanie zakodowany jako:

3
0 n
0 v1
0 v2

 

 

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ład

Dla 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.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com