| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_18_03 - Flaga |
W Bajtocji nadszedł dzień Święta Wojska Bajtockiego. Pan Bajteusz postanowił wywiesić przed domem flagę swej ojczyzny. Jest tylko jeden mały problem. Otóż Bajtocja nie posiada flagi jako takiej... Flagą Bajtocji nazwiemy dowolną flagę złożoną z pionowych pasków o kolorze czerwonym, zielonym lub niebieskim oraz czarnej obwódce, spełniającą podane warunki:
1. Dwa paski o tym samym kolorze nie mogą ze sobą sąsiadować.
2. Pasek w kolorze niebieskim musi znajdować się bezpośrednio pomiędzy paskami z których jeden ma kolor zielony, a drugi - czerwony (czyli niepoprawną flagą jest CZNZ).
Pan Bajteusz chciałby wiedzieć ile jest możliwych flag Bajtocji o podanej długości - w ten sposób będzie wiedział, czy uda mu się wywiesić je wszystkie.
Wejście
Wejście rozpoczyna liczba testów 1 ≤ t ≤ 500 000. Następnie każdy test w oddzielnej linii. Pojedynczy test składa się z jednej liczby całkowitej 1 ≤ n ≤ 106.
Wyjście
Dla każdego testu odpowiedź w oddzielnej linii - liczba możliwych flag Bajtocji składających się z n pasków modulo 1015.
Przykład
Wejście: 1
3
Wyjście: 4
Wyjaśnienie do przykładu:
Są 4 takie flagi: RGR, GBR, RBG, GRG
| Dodane przez: | Adam Bąk |
| Data dodania: | 2014-08-29 |
| Limit czasu wykonania programu: | 1s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
| Pochodzenie: | ALGOLIGA |
ukryj komentarze
|
2019-10-03 21:08:32 Sebastian Toton
@Adam Bąk Może lekkie zmniejszenie limitu czasowego? Rozwiązanie w Javie nie za bardzo chce przejść :/ |
|
|
2014-10-03 22:36:01 Marcin Kasprowicz
W tym zadaniu należy użyć scanf i printf lub fast I/O |