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

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:

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

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

Exemplu:

Intrare

15 2 3 5 2 30 20 50 100

Ieșire

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

   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>

@@ 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.
-== 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.
-== 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
+2 3 5 2 30 20 50 100
+Ieșire
+<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():
-     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
-     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__":