In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule. Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
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 .