| 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: ASM64 GOSU |
| Pochodzenie: | ALGOLIGA |
ukryj komentarze
|
2014-09-01 18:01:29 Adam B±k
@Jarosław Kończak, ze względu na ilość testów, najlepiej było spamiętać wyniki w tablicy dla każdego n i odpowiadać na każdy test w czasie stałym. |
|
|
2014-08-31 22:24:40 Jaroslaw Konczak
Zastanawiam się czy korzystanie z wyników poprzednich testów w kolejnych było konieczne do uzyskania AC. |
|
|
2014-08-31 17:20:45 Piotr KÄ…kol
Jak ktoś uważa, że ma NAC (nie-AC) niezasłużonego, to piszcie, a je Wam zdyskwalifikuję. Już 3 submity zdyskwalifikowałem, bo SPOJ nawalił. |
|
|
2014-08-31 15:48:41 Piotr KÄ…kol
Nadal jest źle? Wydaje się, że wszystko jest ok. |
|
|
2014-08-31 15:33:12 Filip £ubniewski
Czy z silnikiem spoja jest wszystko ok? Same błędy wywala. Ideone, z tego co widzę, też http://ideone.com/recent/1-cpp |
|
|
2014-08-30 16:21:35 Gabriela Gierasimiuk
Ech, a ja próbuje odbugować błędną wersję, ale dzięki za poprawkę. |
|
|
2014-08-30 16:09:50 Piotr KÄ…kol
Słuszna wątpliwość. Poprawiłem treść. Pasek niebieski MUSI bezpośrednio sąsiadować z czerwonym i zielonym. |
|
|
2014-08-30 16:06:44 Gabriela Gierasimiuk
Dla pewności: pasek niebieski nie musi bezpośrednio sąsiadować z paskiem czerwonym oraz zielonym? |
RSS