Editing 2007 - Numere 7

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

* în vârful triunghiului scrie valoarea <code>1</code>;
* 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 <code>5</code> linii, conținând numerele naturale de la <code>1</code> la <code>15</code>.

În acest triunghi copilul începe să construiască drumuri, respectând următoarele reguli:

* orice drum începe din <code>1</code>;
* din orice căsuță se poate deplasa fie în căsuța situată pe linia următoare în stânga sa (deplasare codificată cu <code>1</code>), fie în căsuța situată pe linia următoare în dreapta sa (deplasare codificată cu <code>2</code>);
* orice drum va fi descris prin succesiunea deplasărilor efectuate.

De exemplu, drumul ilustrat în figura 2 poate fi descris astfel: <code>1 2 2 2</code>.

= Cerința =
Scrieţi un program care rezolvă următoarele două cerințe:

1. citește descrierea unui drum și afișează numărul la care se termină drumul;

2. 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ă.

= Date de intrare =
Fișierul de intrare <code>numere17.in</code> conține pe prima linie un număr natural <code>C</code> reprezentând cerința din problemă care trebuie rezolvată (1 sau 2).

Dacă <code>C</code> este egal cu <code>1</code>, a doua linie din fișier conține un număr natural <code>N</code>, reprezentând lungimea drumului, iar a treia linie din fișier conţine descrierea drumului sub forma a <code>N</code> valori, <code>1</code> sau <code>2</code>, separate între ele prin câte un spațiu.

Dacă <code>C</code> este egal cu <code>2</code>, a doua linie din fișier conține numărul natural <code>K</code>.

= Date de ieșire =
Fișierul de ieșire <code>numere17.out</code> va conține o singură linie pe care va fi scris un singur număr natural. Dacă <code>C=1</code>, va fi scris numărul cu care se termină drumul descris în fișierul de intrare. Dacă <code>C=2</code>, va fi scrisă suma maximă a numerelor aflate pe un drum care se termină cu numărul <code>K</code>.

= Restricții și precizări =

* <code>1 ≤ n ≤ 10000</code>
* <code>1 ≤ K ≤ 10001*10002/2</code>
* Pentru rezolvarea corectă a cerinţei 1 se acordă 40 de puncte; pentru rezolvarea corectă a cerinței 2 se acordă 50 de puncte. În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

= Exemplul 1 =
<code>numere17.in</code>
 1 
 4
 1 2 1 2
<code>numere17.out</code>
 13

=== Explicație ===
Cerinţa este 1. Drumul descris are lungimea <code>4</code> și trece prin numerele <code>1,2,5,8,13</code>

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

sys.stdin = open('numere17.in', 'r')

sys.stdout = open('numere17.out', 'w')

n, c, k, x, cnt, m = 0, 0, 0, 0, 0, 1

c = int(input())

if c == 1:

    n = int(input())

    for i in range(1, n+1):

        x = int(input())

        cnt += 1

        if x == 1:

            m += cnt

        if x == 2:

            m += cnt+1

    print(m)

else:

    k = int(input())

    x, s, maxi = 1, 0, 0

    while maxi < k:

        maxi = maxi + x

        s += maxi

        x += 1

    s = s - (maxi - k) * (maxi - k + 1) // 2

    print(s)

</syntaxhighlight>