Fişierul intrare/ieşire:numere9.in, numere9.outSursănumere8
AutorCerasela-Daniela Cardas, Cristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Numere9 (clasa a 8-a)

Notă: aceasta este problema numere8 dată la OJI 2017 clasa a 5-a, punctul 2, cu modificări de restricţii: K este acum mult mai mare.

Un copil construieşte un triunghi cu numerele naturale nenule astfel:

  • în vârful triunghiului scrie valoarea 1;
  • completează liniile triunghiului de sus în jos, iar căsuţele de pe aceeaşi linie de la stânga la dreapta cu numere naturale consecutive, ca în figurile următoare.

În figura 1 este ilustrat un astfel de triunghi având 5 linii, conţinând numerele naturale de la 1 la 15. În acest triunghi copilul începe să construiască drumuri, respectând următoarele reguli:

  • orice drum începe din 1;
  • din orice căsuţă se poate deplasa fie în căsuţa situată pe linia următoare în stânga sa, fie în căsuţa situată pe linia următoare în dreapta sa

Cerinţă

Scrieţi un program care citeşte un număr natural nenul K, determină un drum care se termină cu numărul K pentru care suma numerelor prin care trece drumul este maximă şi afişează această sumă. Deoarece suma poate fi foarte mare ea se va afişa modulo 1953752261.

Date de intrare

Fişierul de intrare numere9.in conţine pe prima linie numărul natural K.

Date de ieşire

Fişierul de ieşire numere9.out va conţine o singură linie pe care va fi scris un singur număr natural, suma maximă a numerelor aflate pe un drum care se termină cu numărul K. Suma se va afişa modulo 1953752261.

Restricţii

  • 1 ≤ K ≤ 1 000 000 000 * 1 000 000 001 / 2

Exemplu

numere9.innumere9.outExplicaţii
9
19
Suma maximă se obţine pe drumul care trece prin
numerele 1,3,6,9 (1+3+6+9=19)
Trebuie sa te autentifici pentru a trimite solutii. Click aici