3223 - Scobitoare: Difference between revisions

From Bitnami MediaWiki
Sinn Erich (talk | contribs)
Ștergerea conținutului paginii
Tag: Blanking
Cata (talk | contribs)
No edit summary
Line 1: Line 1:
==Cerința==
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
==Date de intrare==
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==
Fișierul de ieșire scobitoare.out va conține pe prima linie numărul cerul.
==Restricții și precizări==
* 1 ⩽ n ⩽ 1000
==Exemplu==
scobitoare.in
2 197
scobitoare.out
60
==Rezolvare==
<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:
        raise ValueError("n must be between 1 and 1000")
def read_input():
    with open("scobitoare.in", "r") as f:
        p = int(f.readline())
        n = int(f.readline())
        validate_input(n)
    return p, n
def write_output(output):
    with open("scobitoare.out", "w") as g:
        g.write(str(output))
if __name__ == "__main__":
    p, n = read_input()
    if p == 1:
        output = T(n)
    else:
        output = T(n) - T(n - 1)
    write_output(output)
</syntaxhighlight>

Revision as of 11:52, 20 April 2023

Cerința

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


Date de intrare

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

Fișierul de ieșire scobitoare.out va conține pe prima linie numărul cerul.


Restricții și precizări

  • 1 ⩽ n ⩽ 1000

Exemplu

scobitoare.in

2 197

scobitoare.out

60

Rezolvare

<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:
       raise ValueError("n must be between 1 and 1000")


def read_input():

   with open("scobitoare.in", "r") as f:
       p = int(f.readline())
       n = int(f.readline())
       validate_input(n)
   return p, n


def write_output(output):

   with open("scobitoare.out", "w") as g:
       g.write(str(output))


if __name__ == "__main__":

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

</syntaxhighlight>