3223 - Scobitoare: Difference between revisions

From Bitnami MediaWiki
Cata (talk | contribs)
No edit summary
Cata (talk | contribs)
No edit summary
 
Line 13: Line 13:


==Date de ieșire==
==Date de ieșire==
Fișierul de ieșire scobitoare.out va conține pe prima linie mesajul de validare a datelor ("Date de intrare valide" sau "Date de intrare invalide", în funcție de validitatea datelor), iar pe următorul rând numărul cerut.
Fișierul de ieșire scobitoare.out va conține numărul cerut, iar consola va afișa mesajul de validare a datelor ("Date de intrare valide" sau "Date de intrare invalide", în funcție de validitatea datelor).




Line 23: Line 23:
: 2 197
: 2 197
; scobitoare.out
; scobitoare.out
: 60
; Consolă
: Date de intrare valide
: Date de intrare valide
: 60


==Rezolvare==
==Rezolvare==
Line 65: Line 66:
         n = int(f.readline())
         n = int(f.readline())
         if not validate_input(n):
         if not validate_input(n):
             with open("scobitoare.out", "w") as g:
             print("Date de intrare invalide")
                g.write("Date de intrare invalide")
            return
                return
     return p, n
     return p, n


Line 73: Line 73:
def write_output(output):
def write_output(output):
     with open("scobitoare.out", "w") as g:
     with open("scobitoare.out", "w") as g:
        g.write("Date de intrare valide\n")
         g.write(str(output))
         g.write(str(output))
    print("Date de intrare valide\n")




Line 95: Line 95:
2. Funcția "validate_input(n)" returnează "True" dacă n se află între 1 și 1000 și "False" altfel.
2. Funcția "validate_input(n)" returnează "True" dacă n se află între 1 și 1000 și "False" altfel.


3. Funcția "read_input()" citește din fișierul "scobitoare.in" două numere întregi: "p" și "n". Funcția verifică dacă n este valid folosind funcția "validate_input(n)". În caz contrar, scrie în fișierul "scobitoare.out" mesajul "Date de intrare invalide" și se termină.
3. Funcția "read_input()" citește din fișierul "scobitoare.in" două numere întregi: "p" și "n". Funcția verifică dacă n este valid folosind funcția "validate_input(n)". În caz contrar, scrie în consolă mesajul "Date de intrare invalide" și se termină.


4. Funcția "write_output(output)" scrie valoarea "output" în fișierul "scobitoare.out".
4. Funcția "write_output(output)" scrie valoarea "output" în fișierul "scobitoare.out".


5. În blocul "if __name__ == '__main__':", funcția "read_input()" este apelată pentru a citi inputul. Dacă inputul este valid, se calculează valoarea lui "output" folosind funcția "T(n)" și se apelează funcția "write_output(output)" pentru a scrie outputul în fișierul "scobitoare.out". În cazul în care p este diferit de 1, se calculează diferența dintre T(n) și T(n-1).
5. În blocul "if __name__ == '__main__':", funcția "read_input()" este apelată pentru a citi inputul. Dacă inputul este valid, se calculează valoarea lui "output" folosind funcția "T(n)" și se apelează funcția "write_output(output)" pentru a scrie outputul în fișierul "scobitoare.out". În cazul în care p este diferit de 1, se calculează diferența dintre T(n) și T(n-1).

Latest revision as of 14:32, 14 May 2023

Cerința[edit | edit source]

Lui Ion îi plac scobitorile. Norocul său a fost că black friday tocmai a venit și a cumpărat un număr infinit de scobitori (să zicem că o duce destul de bine). Ținând cont că are extrem de multe scobitori, el a vrut să se joace cu ele, așa că a creat un joc.

La primul pas, el pune o singură scobitoare în mijlocul mesei. Începând cu al doilea pas, el pune câte o scobitoare la fiecare capăt liber al scobitorilor plasate până acum, astfel încât cele două scobitori sunt perpendiculare și mijlocul scobitorii noi se afla la vârful scobitorii vechi. Un vârf de scobitoare este liber dacă nu atinge o altă scobitoare.

Determinați

1. Numărul de scobitori aflate pe masă la pasul N.
2. Numărul de scobitori care au fost adăugate la pasul N.

Date de intrare[edit | edit source]

Fișierul de intrare scobitoare.in conține pe prima linie două numere: P, care va reprezenta cerința, și N, cu semnificația din enunț.


Date de ieșire[edit | edit source]

Fișierul de ieșire scobitoare.out va conține numărul cerut, iar consola va afișa mesajul de validare a datelor ("Date de intrare valide" sau "Date de intrare invalide", în funcție de validitatea datelor).


Restricții și precizări[edit | edit source]

  • 1 ⩽ n ⩽ 1000

Exemplu[edit | edit source]

scobitoare.in
2 197
scobitoare.out
60
Consolă
Date de intrare valide

Rezolvare[edit | edit source]

<syntaxhighlight lang="python"> import math

def T(n):

   if n == 1:
       return 1
   elif n == 2:
       return 3
   elif n == 3:
       return 7
   elif n == 4:
       return 11
   else:
       Puterea = 0
       PutereDeDoi = 1
       while PutereDeDoi < n:
           Puterea += 1
           PutereDeDoi *= 2
       if PutereDeDoi == n:
           return (int(math.pow(2, 2 * Puterea + 1)) + 1) // 3
       else:
           PutereDeDoi = PutereDeDoi // 2
           return T(PutereDeDoi) + 2 * T(n - PutereDeDoi) + T(n - PutereDeDoi + 1) - 1


def validate_input(n):

   if n < 1 or n > 1000:
       return False
   else:
       return True


def read_input():

   with open("scobitoare.in", "r") as f:
       p = int(f.readline())
       n = int(f.readline())
       if not validate_input(n):
           print("Date de intrare invalide")
           return
   return p, n


def write_output(output):

   with open("scobitoare.out", "w") as g:
       g.write(str(output))
   print("Date de intrare valide\n")


if __name__ == "__main__":

   inputs = read_input()
   if inputs:
       p, n = inputs
       if p == 1:
           output = T(n)
       else:
           output = T(n) - T(n - 1)
       write_output(output)

</syntaxhighlight>

Explicație cod[edit | edit source]

Acest cod este scris în limbajul Python și conține următoarele funcții:

1. Funcția "T(n)" calculează valoarea funcției T definită recursiv după cum urmează: T(1) = 1, T(2) = 3, T(3) = 7, T(4) = 11, T(n) = 2*T(n-1) + T(n-2) + T(n-3) - 1 pentru n > 4. În cazul în care n este o putere a lui 2, se aplică o formulă alternativă care folosește funcția "pow" din biblioteca Python "math".

2. Funcția "validate_input(n)" returnează "True" dacă n se află între 1 și 1000 și "False" altfel.

3. Funcția "read_input()" citește din fișierul "scobitoare.in" două numere întregi: "p" și "n". Funcția verifică dacă n este valid folosind funcția "validate_input(n)". În caz contrar, scrie în consolă mesajul "Date de intrare invalide" și se termină.

4. Funcția "write_output(output)" scrie valoarea "output" în fișierul "scobitoare.out".

5. În blocul "if __name__ == '__main__':", funcția "read_input()" este apelată pentru a citi inputul. Dacă inputul este valid, se calculează valoarea lui "output" folosind funcția "T(n)" și se apelează funcția "write_output(output)" pentru a scrie outputul în fișierul "scobitoare.out". În cazul în care p este diferit de 1, se calculează diferența dintre T(n) și T(n-1).