Fişierul intrare/ieşire:fibo4.in, fibo4.outSursăInfoOltenia 2018 - Clasa a 10-a
AutorBogdan IordacheAdăugată deinfoolteniaInfo-Oltenia 2018 infooltenia
Timp execuţie pe test5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fibo4

Şirul Fibonacci este şirul dat prin recurenţa:

F0 = 0, F1 = 1, ..., Fn = Fn - 1 + Fn - 2

După cum probabil aţi ghicit, Fibo este pasionat de şirul Fibonacci, atât de pasionat încât mereu găseşte cele mai interesante probleme legate de acesta. Aşa că nu a ezitat o clipă atunci când l-am rugat să ne sară în ajutor cu o problemă pentru voi. Fibo vă dă un şir de N numere naturale (iniţial toate egale cu 0), apoi vă roagă să aplicaţi o secvenţă de M operaţii asupra acestuia. O operaţie este de forma st, dr, k, cu semnificaţia: pentru fiecare i (st ≤ i ≤ dr), la elementul din şir de la poziţia i se adună Fk+i-st. Fibo vă întreabă cum va arăta şirul după aplicarea celor M operaţii.

Cunoscându-se N, M şi cele M operaţii, determinaţi configuraţia finală a şirului.

Date de intrare

Prima linie a fişierului fibo4.in va conţine numerele N şi M cu semnificaţia din enunţ.
Pe fiecare dintre următoarele M linii se vor găsi 3 numere ( st, dr, k, cu semnificaţia din enunţ) reprezentând în ordine operaţiile.

Date de ieşire

În fişierul fibo4.out afişaţi pe prima linie N numere, reprezentând şirul după aplicarea celor M operaţii. Deoarece numerele pot fi mari, afişaţi pe fiecare dintre ele modulo 666013.

Restricţii

  • 1 ≤ st ≤ dr ≤ N
  • pentru 40% din punctaj: 1 ≤ N, M, k ≤ 1000
  • pentru 65% din punctaj 1 ≤ N, M, k ≤ 106
  • pentru 80% din punctaj 1 ≤ N, M ≤ 106 şi 1 ≤ k ≤ 109
  • pentru 100% din punctaj 1 ≤ N, M ≤ 106 şi 1 ≤ k ≤ 1018

Exemplu

fibo4.infibo4.out
5 3
1 5 1
2 3 3
4 4 6
1 3 5 11 5

Explicaţie

Şirul iniţial este (0, 0, 0, 0, 0).

La prima operaţie, elementului de la poziţia 1 i se adună F1, elementului de la poziţia 2 i se adună F2 , ... , elementului de la poziţia 5 i se adună F5. Obţinem (1, 1, 2, 3, 5).
La a doua operaţie, elementului de la poziţia 2 i se adună F3, iar elementului de la poziţia 3 i se adună F4 . Obţinem (1, 3, 5, 3, 5).
La ultima operaţie, elementului de la poziţia 4 i se adună F6. Obţinem (1, 3, 5, 11, 5).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?