Editing 4267 - Perechi Puncte

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 =
Să se determine numărul perechilor de puncte simetrice.

= Date de intrare =
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:

* <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 =

* <code>10 ≤ n ≤ 6.000.000</code>
* <code>0 ≤ x1, y1, x2, y2 ≤ 30.000</code>
* <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>.

= Exemplu: =
Intrare
 15 2 3 5 2 30 20 50 100
Ieșire
 55<br>

== 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>