przekroczenie limitu czasowego
Ostatnio zmodyfikowano 2014-01-06 22:13
szirot Temat założony przez niniejszego użytkownika |
przekroczenie limitu czasowego » 2014-01-06 17:38:33 tresc: Agnieszka tak polubiła ciągi rekurencyjne, że nie zastanawia się już dłużej nad królikami, tylko analizuje same wzory. Tym razem prosi o obliczenie wartości elementów ciągu określonego wzorami: A(0)=4, A(1)=7, A(n)=2A(n-1)+5A(n-2) dla n>=2. Agnieszka zdaje sobie sprawę, że taki ciąg rośnie bardzo szybko, a więc chciałaby poznać tylko reszty z dzielenia jego wyrazów przez 2011.
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowita t<=10 oznaczająca liczbę testów. W kolejnych liniach znajdują się poszczególne testy. Każdy z nich składa się z jednej liczby całkowitej n (0<=n<=100).
Wyjście
Dla każdego testu wypisz w osobnej linii resztę z dzielenia wartości A(n) przez 2011.
Przykład
Wejście: 3 0 1 2
Wyjście: 4 7 34 |
moj kod : #include <iostream>
using namespace std;
int fib( int n ) { if( n == 0 ) return 4; if( n == 1 ) return 7; return 2 * fib( n - 1 ) + 5 * fib( n - 2 ); }
int main() { int x; cin >> x; for( int i = 0; i < x; i++ ) { int n; cin >> n; cout << fib( n ) % 2011; } return 0; } kod ogolnie dziala, tylko kiedy wrzucam na sprawdzarke nie akceptuje ona tego i wyskakuje ze przekroczono limit czasowy. Prosilbym o pomoc. Z gory dzieki. |
|
pekfos |
» 2014-01-06 17:48:53 Przede wszystkim, w tego typu zadaniach nie używa się strumieni C++, bo są za wolne. Użyj biblioteki standardowej C. Implementacja ciągu też nie jest optymalna. Najlepiej zaimplementuj w oparciu o programowanie dynamiczne. |
|
Monika90 |
» 2014-01-06 22:13:16 najlepsze są rozwiązania najprostsze main = do putStr "#include <stdio.h>\nint a[] = {\n" let a = 4 : 7 : zipWith (\a0 a1 -> 2 * a1 + 5 * a0) a (tail a) mapM_ (putStr . (++ ",") . show . (`mod` 2011)) $ take 101 a putStr "\n};\n\ \int main() {\n\ \ int n;\n\ \ scanf(\"%i\", &n);\n\ \ for (int i = 0; i < n; ++i) {\n\ \ int j;\n\ \ scanf(\"%i\", &j);\n\ \ printf(\"%i\\n\", a[j]);\n\ \ }\n\ \}"
|
|
« 1 » |