4267 - Perechi Puncte
De la Universitas MediaWiki
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 de7
ori punctul(9,2)
, atunci se obțin5 * 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
55
Rezolvare
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()