W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Liczby Fibonacciego definiujemy następująco:
Maszyna Fibonacciego operuje na -elementowym ciągu rejestrów całkowitoliczbowych , początkowo zawierających same zera. Umożliwia ona wykonywanie dwóch operacji:
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz (), oddzielone pojedynczym odstępem i oznaczające długość ciągu i liczbę operacji. W każdym z kolejnych wierszy znajduje się opis jednej operacji. Składa się on z (pooddzielanych pojedynczymi odstępami) znaku D lub S oraz dwóch liczb całkowitych i (). Znak D oznacza operację dodania 1 na przedziale , natomiast znak S - operację sumowania liczb Fibonacciego o indeksach z przedziału . Możesz założyć, że w ciągu operacji występuje co najmniej jedna operacja S.
Dla każdej operacji S na standardowe wyjście wypisz dokładnie jeden wiersz zawierający szukaną sumę liczb Fibonacciego. Wyniki należy podać modulo .
Dla danych wejściowych:
5 7 D 1 4 S 1 5 D 3 5 D 2 3 S 1 5 D 2 5 S 2 3
poprawną odpowiedzią jest:
4 6 5
Wyjaśnienie do przykładu: Po siedmiu operacjach ciąg rejestrów przyjmuje postać . Wynik dla ostatniego zapytania to .
Autor zadania: Tomasz Idziaszek.