4267 - Perechi Puncte: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: Se dau n puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale (x, y), unde x și y sunt numere naturale. Spunem că două puncte (x, y) și (i, j) sunt simetrice dacă x = j și y = i. == Cerința == Să se determine numărul perechilor de puncte simetrice. == Date de intrare == Programul citește de la tastatură, separate prin spații, numerele naturale n, x1, y1, x2, y2, A, B, C, D, unde n este numărul de puncte, (x1, y1) sunt coordonate...
 
No edit summary
 
Line 1: Line 1:
Se dau n puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale (x, y), unde x și y sunt numere naturale. Spunem că două puncte (x, y) și (i, j) sunt simetrice dacă x = j și y = i.
Se dau <code>n</code> puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale <code>(x, y)</code>, unde <code>x</code> și <code>y</code> sunt numere naturale. Spunem că două puncte <code>(x, y)</code> și <code>(i, j)</code> sunt simetrice dacă <code>x = j</code> și <code>y = i</code>.
== Cerința ==
 
= Cerința =
Să se determine numărul perechilor de puncte simetrice.
Să se determine numărul perechilor de puncte simetrice.
== Date de intrare ==
 
Programul citește de la tastatură, separate prin spații, numerele naturale n, x1, y1, x2, y2, A, B, C, D, unde n este numărul de puncte, (x1, y1) sunt coordonatele primului punct, (x2, y2) sunt coordonatele celui de-al doilea punct, iar restul punctelor (x[i], y[i]) se generează după formulele:
= Date de intrare =
*'''x[i] = (x[i - 1] * A + x[i - 2] * B + C) % D, i = 3..n'''
Programul citește de la tastatură, separate prin spații, numerele naturale <code>n</code>, <code>x1</code>, <code>y1</code>, <code>x2</code>, <code>y2</code>, <code>A</code>, <code>B</code>, <code>C</code>, <code>D</code>, unde <code>n</code> este numărul de puncte, <code>(x1, y1)</code> sunt coordonatele primului punct, <code>(x2, y2)</code> sunt coordonatele celui de-al doilea punct, iar restul punctelor <code>(x[i], y[i])</code> se generează după formulele:
*'''y[i] = (y[i - 1] * A + y[i - 2] * B + C) % D, i = 3..n'''
 
== Date de ieșire ==  
* <code>x[i] = (x[i - 1] * A + x[i - 2] * B + C) % D</code>, <code>i = 3..n</code>
* <code>y[i] = (y[i - 1] * A + y[i - 2] * B + C) % D</code>, <code>i = 3..n</code>
 
= Date de ieșire =
Programul va afișa pe ecran numărul perechilor de puncte simetrice.
Programul va afișa pe ecran numărul perechilor de puncte simetrice.
== Restricții și precizări ==
*'''10 ≤ n ≤ 6.000.000'''
*'''0 ≤ x1, y1, x2, y2 ≤ 30.000'''
*'''2 ≤ A, B, C, D ≤ 30.000'''
*Punctele generate nu sunt neapărat distincte. Dacă de exemplu se generează de 5 ori punctul (2,9) și de 7 ori punctul (9,2), atunci se obțin 5 * 7 = 35 de perechi simetrice.
*Simetricul punctului (x, x) este un alt punct (x, x).
== Exemplul 1 ==
; Intrare
: 15 2 3 5 2 30 20 50 100
; Ieșire
: 55
<br>
== Exemplul 2 ==
; Intrare
: 8 1 1 1 1 2 1 3 10
; Ieșire
: 6
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#4267 - Perechi Puncte
def generate_coordinates(n, x1, y1, x2, y2, A, B, C, D):
    coordinates = [(x1, y1), (x2, y2)]
    for i in range(3, n + 1):
        xi = (coordinates[i - 1][0] * A + coordinates[i - 2][0] * B + C) % D
        yi = (coordinates[i - 1][1] * A + coordinates[i - 2][1] * B + C) % D
        coordinates.append((xi, yi))


    return coordinates
= Restricții și precizări =


def count_symmetric_pairs(coordinates):
* <code>10 ≤ n ≤ 6.000.000</code>
    point_count = {}
* <code>0 ≤ x1, y1, x2, y2 ≤ 30.000</code>
    symmetric_pairs = 0
* <code>2 ≤ A, B, C, D ≤ 30.000</code>
* Punctele generate nu sunt neapărat distincte. Dacă de exemplu se generează de <code>5</code> ori punctul <code>(2,9)</code> și de <code>7</code> ori punctul <code>(9,2)</code>, atunci se obțin <code>5 * 7 = 35</code> de perechi simetrice.
* Simetricul punctului <code>(x, x)</code> este un alt punct <code>(x, x)</code>.


    for point in coordinates:
= Exemplu: =
        symmetric_pairs += point_count.get((point[1], point[0]), 0)
Intrare
        point_count[point] = point_count.get(point, 0) + 1
15 2 3 5 2 30 20 50 100
Ieșire
55<br>


     return symmetric_pairs
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(n, X, Y, X_, Y_, a, b, c, d):
     if not (10 <= n <= 6000000):
        return False
    if not (0 <= X <= 30000 and 0 <= Y <= 30000 and 0 <= X_ <= 30000 and 0 <= Y_ <= 30000):
        return False
    if not (2 <= a <= 30000 and 2 <= b <= 30000 and 2 <= c <= 30000 and 2 <= d <= 30000):
        return False
    return True


def main():
def main():
     n, x1, y1, x2, y2, A, B, C, D = map(int, input().split())
     data = input("").split()
 
   
     if not (10 <= n <= 6_000_000 and 0 <= x1 <= 30_000 and 0 <= y1 <= 30_000 and 0 <= x2 <= 30_000 and 0 <= y2 <= 30_000 and 2 <= A <= 30_000 and 2 <= B <= 30_000 and 2 <= C <= 30_000 and 2 <= D <= 30_000):
     n = int(data[0])
         print("Fals")
    X = int(data[1])
    Y = int(data[2])
    X_ = int(data[3])
    Y_ = int(data[4])
    a = int(data[5])
    b = int(data[6])
    c = int(data[7])
    d = int(data[8])
   
    if not verifica_restrictii(n, X, Y, X_, Y_, a, b, c, d):
         print("Datele nu corespund restrictiilor impuse")
         return
         return
 
   
     coordinates = generate_coordinates(n, x1, y1, x2, y2, A, B, C, D)
    from collections import defaultdict
    result = count_symmetric_pairs(coordinates)
     points = defaultdict(int)
 
   
     print(result)
    points[(X, Y)] += 1
    points[(X_, Y_)] += 1
   
    simetrice = 0
   
    if X == Y_ and Y == X_:
        simetrice += 1
   
    for i in range(3, n + 1):
        x, y = X, Y
        X, Y = X_, Y_
        X_ = (X * a + x * b + c) % d
        Y_ = (Y * a + y * b + c) % d
       
        simetrice += points[(Y_, X_)]
        points[(X_, Y_)] += 1
   
     print(f"{simetrice}")


if __name__ == "__main__":
if __name__ == "__main__":

Latest revision as of 14:09, 18 May 2024

Se dau n puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale (x, y), unde x și y sunt numere naturale. Spunem că două puncte (x, y) și (i, j) sunt simetrice dacă x = j și y = i.

Cerința[edit | edit source]

Să se determine numărul perechilor de puncte simetrice.

Date de intrare[edit | edit source]

Programul citește de la tastatură, separate prin spații, numerele naturale n, x1, y1, x2, y2, A, B, C, D, unde n este numărul de puncte, (x1, y1) sunt coordonatele primului punct, (x2, y2) sunt coordonatele celui de-al doilea punct, iar restul punctelor (x[i], y[i]) se generează după formulele:

  • x[i] = (x[i - 1] * A + x[i - 2] * B + C) % D, i = 3..n
  • y[i] = (y[i - 1] * A + y[i - 2] * B + C) % D, i = 3..n

Date de ieșire[edit | edit source]

Programul va afișa pe ecran numărul perechilor de puncte simetrice.

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

  • 10 ≤ n ≤ 6.000.000
  • 0 ≤ x1, y1, x2, y2 ≤ 30.000
  • 2 ≤ A, B, C, D ≤ 30.000
  • Punctele generate nu sunt neapărat distincte. Dacă de exemplu se generează de 5 ori punctul (2,9) și de 7 ori punctul (9,2), atunci se obțin 5 * 7 = 35 de perechi simetrice.
  • Simetricul punctului (x, x) este un alt punct (x, x).

Exemplu:[edit | edit source]

Intrare

15 2 3 5 2 30 20 50 100

Ieșire

55

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line="1"> def verifica_restrictii(n, X, Y, X_, Y_, a, b, c, d):

   if not (10 <= n <= 6000000):
       return False
   if not (0 <= X <= 30000 and 0 <= Y <= 30000 and 0 <= X_ <= 30000 and 0 <= Y_ <= 30000):
       return False
   if not (2 <= a <= 30000 and 2 <= b <= 30000 and 2 <= c <= 30000 and 2 <= d <= 30000):
       return False
   return True

def main():

   data = input("").split()
   
   n = int(data[0])
   X = int(data[1])
   Y = int(data[2])
   X_ = int(data[3])
   Y_ = int(data[4])
   a = int(data[5])
   b = int(data[6])
   c = int(data[7])
   d = int(data[8])
   
   if not verifica_restrictii(n, X, Y, X_, Y_, a, b, c, d):
       print("Datele nu corespund restrictiilor impuse")
       return
   
   from collections import defaultdict
   points = defaultdict(int)
   
   points[(X, Y)] += 1
   points[(X_, Y_)] += 1
   
   simetrice = 0
   
   if X == Y_ and Y == X_:
       simetrice += 1
   
   for i in range(3, n + 1):
       x, y = X, Y
       X, Y = X_, Y_
       X_ = (X * a + x * b + c) % d
       Y_ = (Y * a + y * b + c) % d
       
       simetrice += points[(Y_, X_)]
       points[(X_, Y_)] += 1
   
   print(f"{simetrice}")

if __name__ == "__main__":

   main()

</syntaxhighlight>