1833 - N Consecutive

Cerința

Într-­o zi frumoasă de vara, Gigel l­a auzit pe fratele mai mare spunând că ştie să scrie numărul 600 ca sumă de numere consecutive în 5 moduri distincte. Deoarece Gigel este ambiţios, doreşte să poată să facă şi el astfel de afirmaţii. Mai exact, el îşi doreşte să poată să spună care este cel mai mic număr natural care poate fi descompus ca sumă de două sau mai multe numere naturale consecutive în exact N moduri şi care sunt acele moduri.

Să se determine cel mai mic număr natural care respectă condițiile lui Gigel.

Date de intrare

Fișierul de intrare consecutive.in conține pe prima linie numărul N, reprezentând numărul de moduri în care numărul găsit de Gigel să poată fi scris ca suma de numere consecutive

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se va afișa numărul x, reprezentând numărul găsit de Gigel, iar pe următoarele N rânduri va fi afișat câte un număr, reprezentând lungimea secvenţei.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ≤ n ≤ 100

• Se garantează că soluţia e mai mică decât 1.000.000

Exemplu 1

Intrare

2

Ieșire

9

2

3

Explicație

9 = 4 + 5 (secventa de lungime 2 care incepe de la 4)

9 = 2 + 3 + 4 (secventa de lungime 3 care incepe de la 2)

Exemplu 2

Intrare

500

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 1833 N Consecutive

from math import sqrt

def cerinte(nr):

   return 1 <= nr <= 100

def suma_aritmetic(a, b):

   return (b * (b + 1)) // 2 - ((a - 1) * a) // 2

def n_consecutive(nr):

   val_max = 1_000_000
   sume = [0] * (val_max + 1)

   for i in range(2, val_max):
       for stanga in range(1, val_max):
           dreapta = stanga + i - 1
           if suma_aritmetic(stanga, dreapta) > val_max:
               break
           sume[suma_aritmetic(stanga, dreapta)] += 1

   for i in range(3, val_max):
       if sume[i] == nr:
           print(i)

           for stanga in range(i // 2, 0, -1):
               ec_patrata = 1 - 4 * (stanga - stanga * stanga - 2 * i)
               dreapta = (-1 + sqrt(ec_patrata)) / 2
               if dreapta == int(dreapta):
                   print(int(dreapta - stanga + 1))
           break

if __name__ == "__main__":

   nr = int(input())

   if not cerinte(nr):
       print("Datele de intrare nu corespund restricțiilor impuse.")
   else:
       print("Datele de intrare corespund restricțiilor impuse.")
       n_consecutive(nr)

</syntaxhighlight>