4267 - Perechi Puncte: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: 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 coordonate...)
 
Fără descriere a modificării
 
Linia 1: Linia 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.
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.
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
15 2 3 5 2 30 20 50 100
Ieșire
55<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():
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
         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__":
if __name__ == "__main__":

Versiunea curentă din 18 mai 2024 14:09

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 

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()
Adus de la „http://wiki.universitas.ro/index.php?title=4267_-_Perechi_Puncte&oldid=9797”