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]

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

Date de intrare[edit]

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]

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

Restricții și precizări[edit]

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]

Intrare

15 2 3 5 2 30 20 50 100

Ieșire

Rezolvare[edit]

<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__":