Editing 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'''
== Exemplu 1 ==
; numberofpointsin.txt
: 7 19 17 11 23 4 5 7 2
; numberofpointsout.txt
: 1
: 1
: 2
: 2
: 4
: 0
: 5
<br>
== Exemplu 2 ==
; numberofpointsin.txt
: 5 3 5 7 10 2 4 8 6
; numberofpointsout.txt
: 0
: 1
: 2
: 3
: 3
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#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()

</syntaxhighlight>

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