1833 - N Consecutive: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: ==Cerința== Într-­o zi frumoasă de vara, Gigel l­a auzit pe fratele mai mare spunând că ştie să scrie numărul <code>600</code> ca sumă de numere consecutive în <code>5</code> 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 <co...
Tag: visualeditor
 
No edit summary
Tag: visualeditor
 
(4 intermediate revisions by the same user not shown)
Line 7: Line 7:
Fișierul de intrare <code>consecutive.in</code> conține pe prima linie numărul <code>N</code>, reprezentând numărul de moduri în care numărul găsit de Gigel să poată fi scris ca suma de numere consecutive
Fișierul de intrare <code>consecutive.in</code> conține pe prima linie numărul <code>N</code>, 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==
==Date de ieșire==
Fișierul de ieșire <code>consecutive.out</code> va conține pe prima linie numărul <code>x</code>, reprezentând numărul găsit de Gigel, iar pe următoarele <code>N</code> linii va fi afișat câte un număr, reprezentând lungimea secvenţei.
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 <code>x</code>, reprezentând numărul găsit de Gigel, iar pe următoarele <code>N</code> 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==
==Restricții și precizări==
Line 19: Line 23:
:2
:2
;Ieșire
;Ieșire
:Datele de intrare corespund restricțiilor impuse.
:9
:9
:2
:2
Line 32: Line 37:
:500
:500
;Ieșire
;Ieșire
:Date de intrare gresite!
:Datele de intrare nu corespund restricțiilor impuse.


==Rezolvare==
==Rezolvare==
<syntaxhighlight lang="python" line="1">
<syntaxhighlight lang="python" line="1">
#1833 Consecutive N
#1833 N Consecutive
import math
from math import sqrt
 


   
def cerinte(nr):
def cerinte(nr):
     return 1 <= nr <= 100
     return 1 <= nr <= 100
Line 45: Line 50:


def suma_aritmetic(a, b):
def suma_aritmetic(a, b):
    # Formula sumei aritmetice
     return (b * (b + 1)) // 2 - ((a - 1) * a) // 2
     return (b * (b + 1)) // 2 - ((a - 1) * a) // 2




def main():
def n_consecutive(nr):
    nr = int(input())
 
    if not cerinte(nr):
        return print("Date de intrare gresite!")
 
     val_max = 1_000_000
     val_max = 1_000_000
     sume = [0] * (val_max + 1)
     sume = [0] * (val_max + 1)


    # Iterăm peste toate secvențele consecutive posibile (adică punctele de început și de sfârșit)
     for i in range(2, val_max):
     for i in range(2, val_max):
         for stanga in range(1, val_max):
         for stanga in range(1, val_max):
             dreapta = stanga + i - 1
             dreapta = stanga + i - 1
            # Dacă suma acestei secvențe este mai mare decât val_max, nu mai iterăm peste punctele de început
             if suma_aritmetic(stanga, dreapta) > val_max:
             if suma_aritmetic(stanga, dreapta) > val_max:
                 break
                 break
            # Incrementăm numărul de apariții ale sumei acestei secvențe în lista sume
             sume[suma_aritmetic(stanga, dreapta)] += 1
             sume[suma_aritmetic(stanga, dreapta)] += 1


    # Căutăm prima sumă a unei secvențe consecutive care apare de nr ori în lista sume
     for i in range(3, val_max):
     for i in range(3, val_max):
         if sume[i] == nr:
         if sume[i] == nr:
             print(i)
             print(i)


            # Căutăm o secvență consecutivă care se adună la i iterând peste toate punctele de început posibile
            # și rezolvând o ecuație de gradul 2 pentru a găsi punctul de sfârșit
             for stanga in range(i // 2, 0, -1):
             for stanga in range(i // 2, 0, -1):
                 ec_patrata = 1 - 4 * (stanga - stanga * stanga - 2 * i)
                 ec_patrata = 1 - 4 * (stanga - stanga * stanga - 2 * i)
                 dreapta = (-1 + math.sqrt(ec_patrata)) / 2
                 dreapta = (-1 + sqrt(ec_patrata)) / 2
                # Dacă punctul de sfârșit este un număr întreg, afișăm lungimea secvenței consecutive
                 if dreapta == int(dreapta):
                 if dreapta == int(dreapta):
                     print(int(dreapta - stanga + 1))
                     print(int(dreapta - stanga + 1))
Line 77: Line 85:


if __name__ == "__main__":
if __name__ == "__main__":
     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>
</syntaxhighlight>

Latest revision as of 11:41, 6 May 2023

Cerința[edit]

Î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[edit]

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[edit]

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[edit]

  • 1 ≤ n ≤ 100
  • Se garantează că soluţia e mai mică decât 1.000.000

Exemplu 1[edit]

Intrare
2
Ieșire
Datele de intrare corespund restricțiilor impuse.
9
2
3

Explicație[edit]

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[edit]

Intrare
500
Ieșire
Datele de intrare nu corespund restricțiilor impuse.

Rezolvare[edit]

<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):

   # Formula sumei aritmetice
   return (b * (b + 1)) // 2 - ((a - 1) * a) // 2


def n_consecutive(nr):

   val_max = 1_000_000
   sume = [0] * (val_max + 1)
   # Iterăm peste toate secvențele consecutive posibile (adică punctele de început și de sfârșit)
   for i in range(2, val_max):
       for stanga in range(1, val_max):
           dreapta = stanga + i - 1
           # Dacă suma acestei secvențe este mai mare decât val_max, nu mai iterăm peste punctele de început
           if suma_aritmetic(stanga, dreapta) > val_max:
               break
           # Incrementăm numărul de apariții ale sumei acestei secvențe în lista sume
           sume[suma_aritmetic(stanga, dreapta)] += 1
   # Căutăm prima sumă a unei secvențe consecutive care apare de nr ori în lista sume
   for i in range(3, val_max):
       if sume[i] == nr:
           print(i)
           # Căutăm o secvență consecutivă care se adună la i iterând peste toate punctele de început posibile
           # și rezolvând o ecuație de gradul 2 pentru a găsi punctul de sfârșit
           for stanga in range(i // 2, 0, -1):
               ec_patrata = 1 - 4 * (stanga - stanga * stanga - 2 * i)
               dreapta = (-1 + sqrt(ec_patrata)) / 2
               # Dacă punctul de sfârșit este un număr întreg, afișăm lungimea secvenței consecutive
               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>