Oros Ioana Diana at 14:15, 18 May 2024

2024-05-18T14:15:29Z

← Older revision		Revision as of 14:15, 18 May 2024
Line 11:		Line 11:

	= Date de ieșire =		= Date de ieșire =
	Fișierul de ieșire <code>numberofpointsOUT.txt</code> va conține exact <code>n</code> linii, pe linia <code>i</code> (cu <code>i = 1..n</code>) se va afla un singur număr natural reprezentând numărul de puncte care au abscisa strict mai mică decât <code>xi</code> și ordonata mai mică sau egală decât <code>yi</code>.		Fișierul de ieșire <code>numberofpointsOUT.txt</code> va conține exact <code>n</code> linii, pe linia <code>i</code> (cu <code>i = 1..n</code>) se va afla un singur număr natural reprezentând numărul de puncte care au abscisa strict mai mică decât <code>xi</code> și ordonata mai mică sau egală decât <code>yi</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

	= Restricții și precizări =		= Restricții și precizări =

Oros Ioana Diana at 14:15, 18 May 2024

2024-05-18T14:15:17Z

Show changes

Oros Ioana Diana at 20:36, 8 January 2024

2024-01-08T20:36:23Z

← Older revision		Revision as of 20:36, 8 January 2024
Line 11:		Line 11:
	*'''1 ≤ n ≤ 200.000'''		*'''1 ≤ n ≤ 200.000'''
	*'''1 ≤ A, B, C, D, x1, y1, x2, y2 ≤ 1.000.000'''		*'''1 ≤ A, B, C, D, x1, y1, x2, y2 ≤ 1.000.000'''
	== ~~Exemplu~~ 1 ==		== Exemplul 1 ==
	; numberofpointsin.txt		; numberofpointsin.txt
	: 7 19 17 11 23 4 5 7 2		: 7 19 17 11 23 4 5 7 2
Line 23:		Line 23:
	: 5		: 5
	<br>		<br>
	== ~~Exemplu~~ 2 ==		== Exemplul 2 ==
	; numberofpointsin.txt		; numberofpointsin.txt
	: 5 3 5 7 10 2 4 8 6		: 5 3 5 7 10 2 4 8 6

Oros Ioana Diana: Pagină nouă: Î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...

2024-01-08T20:36:02Z

Pagină nouă: Î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...

New page

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

4203 - Number of Points - Revision history

Oros Ioana Diana at 14:15, 18 May 2024

Oros Ioana Diana at 14:15, 18 May 2024

Oros Ioana Diana at 20:36, 8 January 2024