4203 - Number of Points

În planul xOy se găsesc n puncte de coordonate numere naturale nenule, nu neapărat aflate pe poziții distincte.

Cerința

Pentru fiecare punct din plan de coordonate (x, y) trebuie să spuneți câte alte puncte au coordonatele (p, q) cu proprietatea că 1 ≤ p < x și 1 ≤ q ≤ y (atenție, p este strict mai mic decât x, iar q este mai mic sau egal cu y).

Date de intrare

Fișierul de intrare numberofpointsin.txt conține pe prima linie, separate prin câte un spațiu, numerele n, A, B, C, D, x1, y1, x2, y2, unde n este numărul de puncte din plan, (x1, y1) sunt coordonatele primului punct din plan, iar (x2, y2) sunt coordonatele celui de-al doilea punct. Coordonatele restului punctelor se generează după formulele:

• xi = (xi-2 * A + xi-1 * B + C) % D + 1, pentru orice i=3..n
• yi = (yi-2 * A + yi-1 * B + C) % D + 1, pentru orice i=3..n

Date de ieșire

Fișierul de ieșire numberofpointsout.txt va conține exact n linii, pe linia i (cu i = 1..n) se va afla un singur număr natural reprezentând numărul de puncte care au abscisa strict mai mică decât xi și ordonata mai mică sau egală decât yi.

Restricții și precizări

• 1 ≤ n ≤ 200.000
• 1 ≤ A, B, C, D, x1, y1, x2, y2 ≤ 1.000.000

Exemplul 1

numberofpointsin.txt

7 19 17 11 23 4 5 7 2

numberofpointsout.txt

1

1

2

2

4

0

5

Exemplul 2

numberofpointsin.txt

5 3 5 7 10 2 4 8 6

numberofpointsout.txt

0

1

2

3

3

Rezolvare

#4203 - Number of Points
def generate_coordinates(n, A, B, C, D, x1, y1, x2, y2):
    if not (1 <= n <= 200000 and 1 <= A <= 1000000 and 1 <= B <= 1000000 and 1 <= C <= 1000000 and 1 <= D <= 1000000 and 1 <= x1 <= 1000000 and 1 <= y1 <= 1000000 and 1 <= x2 <= 1000000 and 1 <= y2 <= 1000000):
        return False

    coordinates = [(x1, y1), (x2, y2)]

    for i in range(3, n + 1):
        xi = (coordinates[i - 3][0] * A + coordinates[i - 2][0] * B + C) % D + 1
        yi = (coordinates[i - 3][1] * A + coordinates[i - 2][1] * B + C) % D + 1
        coordinates.append((xi, yi))

    return coordinates

def count_points(coordinates):
    if not all(1 <= coord[0] <= 1000000 and 1 <= coord[1] <= 1000000 for coord in coordinates):
        return False

    result = []

    for i in range(len(coordinates)):
        count = sum(1 for j in range(i) if coordinates[j][0] < coordinates[i][0] and coordinates[j][1] <= coordinates[i][1])
        result.append(count)

    return result

def main():
    with open("numberofpointsin.txt", "r") as infile:
        n, A, B, C, D, x1, y1, x2, y2 = map(int, infile.readline().split())

    coordinates = generate_coordinates(n, A, B, C, D, x1, y1, x2, y2)
    if not coordinates:
        print("Fals")
        return

    result = count_points(coordinates)

    with open("numberofpointsout.txt", "w") as outfile:
        for count in result:
            outfile.write(str(count) + "\n")

if __name__ == "__main__":
    main()

 Explicatie 

Cele șapte puncte generate au coordonatele: (4, 5), (7, 2), (23, 3), (7, 9), (16, 15), (3, 1) și (22, 15). Primul punct, de coordonate (4, 5) are un singur punct care îndeplinește cerințele, anume cel de coordonate (3, 1). Al cincilea punct, de coordonate (16, 15) are 4 puncte care îndeplinesc condițiile, anume (4, 5), (7, 2), (7, 9) și (3, 1).