4267 - Perechi Puncte

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

Exemplul 1

Intrare

15 2 3 5 2 30 20 50 100

Ieșire

55

Exemplul 2

Intrare

8 1 1 1 1 2 1 3 10

Ieșire

6

Rezolvare

<syntaxhighlight lang="python" line>

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

def count_symmetric_pairs(coordinates):

   point_count = {}
   symmetric_pairs = 0

   for point in coordinates:
       symmetric_pairs += point_count.get((point[1], point[0]), 0)
       point_count[point] = point_count.get(point, 0) + 1

   return symmetric_pairs

def main():

   n, x1, y1, x2, y2, A, B, C, D = map(int, 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):
       print("Fals")
       return

   coordinates = generate_coordinates(n, x1, y1, x2, y2, A, B, C, D)
   result = count_symmetric_pairs(coordinates)

   print(result)

if __name__ == "__main__":

   main()

</syntaxhighlight>