Triunghi
- Adăugată de :
- sorynsoo
- Sursă :
- XOR2011
- Autor :
- -
- Grupă :
- Mica
- Punctaj :
- 0 pc
Considerăm următorul triunghi:
0
1 1
2 2 2
3 4 4 3
4 7 8 7 4
5 11 15 15 11 5
...................................................
Numerotăm liniile triunghiului cu numere naturale începând de la 1. De exemplu, pe linia 1 se află numai numărul 0, pe linia 2 se află 1 1, pe linia 5 se află numerele 4 7 8 7 4.
Cerinţa
Deduceţi regula după care este construit triunghiul şi determinaţi suma numerelor pe pe o anumită linie a triunghiului. Pentru că acest număr poate fi foarte mare, se va calcula suma modulo 2011 (restul împărţirii sumei la 2011).
Date de intrare
Fişierul de intrare conţine pe prima linie numărul natural n reprezentând numărul liniei de pe care se va calcula suma numerelor.
Date de iesire
Fişierul de intrare va conţine un singur număr natural reprezentând suma modulo 2011 a numerelor de pe linia n din triunghi.
Restricţii şi precizări:
- 1 <= n <= 10 000 000
- Pentru calculul sumei modulo 2011, se pot utiliza relaţiile:
- (a + b) mod 2011 = (a mod 2011 + b mod 2011) mod 2011
- (a * b) mod 2011 = (a mod 2011 * b mod 2011) mod 2011
Exemple
Date de intrare |
Date de iesire |
Explicaţii |
5 |
30 |
Suma elementelor de pe linia 5 este 4+7+8+7+4 = 30, iar 30 mod 2011 = 30. |
Date de intrare |
Date de iesire |
Explicaţii |
13 |
146 |
Suma elementelor de pe linia 13 este 8190. 8190 mod 2011 = 146 |
Indicații rezolvare
Nu există indicații de rezolvare
Comentarii
Adauga un comentariu: Click !