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.
Maszyna Fibonacciego operuje na -elementowym ciągu rejestrów całkowitoliczbowych
, początkowo zawierających same zera.
Umożliwia ona wykonywanie dwóch operacji:
dodanie jedynki do każdego rejestru z przedziału , tzn. do rejestrów
;
obliczenie sumy liczb Fibonacciego, których indeksami są rejestry
o numerach z przedziału , tzn. wartości
Twoim zadaniem jest napisanie symulatora maszyny Fibonacciego.
Wejście
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.
Wyjście
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 .
Przykład
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 .