Andrada378: /* Rezolvare */

2024-01-03T20:47:48Z

Rezolvare

← Older revision		Revision as of 20:47, 3 January 2024
Line 63:		Line 63:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
			def validate_input(n, m, q):
			if not (1 <= n <= 100000 and 1 <= q <= 100000 and 1 <= m <= 1000000000):
			raise ValueError("Date de intrare invalide.")
	def cautare_binara(stanga, dreapta, valoare, inaltime):		def cautare_binara(stanga, dreapta, valoare, inaltime):
	raspuns = stanga - 1		raspuns = stanga - 1

Andrada378 at 22:49, 2 January 2024

2024-01-02T22:49:42Z

← Older revision		Revision as of 22:49, 2 January 2024
Line 1:		Line 1:
			== Enunț ==
	Se dă o matrice binară cu n coloane și m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m.		Se dă o matrice binară cu n coloane și m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m.

Andrada378: Pagină nouă: Se dă o matrice binară cu n coloane și m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m. Matricea dată are o formă particulară, astfel că pentru fiecare coloană i de la 1 la n toate elementele matricei de pe coloana respectivă au valoarea 1 pentru toate liniile cuprinse în intervalul [1, h[i]] și în rest valoarea 0. Valorile h[i] sunt numere naturale date în ordi...

2024-01-02T22:48:58Z

Pagină nouă: Se dă o matrice binară cu n coloane și m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m. Matricea dată are o formă particulară, astfel că pentru fiecare coloană i de la 1 la n toate elementele matricei de pe coloana respectivă au valoarea 1 pentru toate liniile cuprinse în intervalul [1, h[i]] și în rest valoarea 0. Valorile h[i] sunt numere naturale date în ordi...

New page

Se dă o matrice binară cu n coloane și m linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la n, iar liniile sunt numerotate de jos în sus cu valori de la 1 la m.

Matricea dată are o formă particulară, astfel că pentru fiecare coloană i de la 1 la n toate elementele matricei de pe coloana respectivă au valoarea 1 pentru toate liniile cuprinse în intervalul [1, h[i]] și în rest valoarea 0. Valorile h[i] sunt numere naturale date în ordine crescătoare (h[i-1] ≤ h[i], 1 ≤ i ≤ n).

== Cerința ==
Să se răspundă la q întrebări de forma: dându-se numerele A, B, C, D se cere suma elementelor din submatricea determinată de zona dreptunghiulară având colțul stânga-jos în coloana A și linia B, iar colțul dreapta-sus în coloana C și linia D.

== Date de intrare ==
Fișierul de intrare este tniain.txt.

* pe prima linie se găsesc două numere naturale n și m despărțite printr-un spațiu, cu semnificația de mai sus;
* pe a doua linie sunt cele n elemente h[i] ale vectorului despărțite prin câte un spațiu;
* pe a treia linie este un număr natural q ce reprezintă numărul de întrebări;
* pe următoarele q linii se găsesc câte patru numere A, B, C, D cu semnificația de mai sus, despărțite prin câte un spațiu.

== Date de ieșire ==
Fișierul de ieșire tniaout.txt va conține q linii reprezentând răspunsul pentru fiecare întrebare.

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

* 0 ≤ h[i] ≤ m, 1 ≤ n ≤ 100 000
* 1 ≤ q ≤ 100 000, 1 ≤ m ≤ 1 000 000 000
* Pentru 15 puncte: n, m, q ≤ 100
* Pentru alte 16 puncte: n, m, q ≤ 3000
* Pentru alte 16 puncte: n ≤ 100 000, m ≤ 1000 000 000, q ≤ 100
* În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru testul din exemplu.

== Exemplu: ==
'''tniain.txt'''

5 10

2 3 7 8 10

5

1 1 5 10

2 5 4 7

3 2 3 6

3 8 3 10

3 2 3 10

'''tniaout.txt'''

30

6

5

0

6

== Explicație ==
Zona dreptunghiulară având colțul stânga-jos la coloana 1 și linia 1 și colțul dreapta-sus la coloana 5 și linia 10 are suma elementelor 30. Analog, pentru celelalte patru întrebări, răspunsurile corecte sunt: 6, 5, 0 și 6.

== Rezolvare ==
<syntaxhighlight lang="python">
def cautare_binara(stanga, dreapta, valoare, inaltime):
raspuns = stanga - 1
while stanga <= dreapta:
mijloc = (stanga + dreapta) // 2
if inaltime[mijloc] < valoare:
raspuns = mijloc
stanga = mijloc + 1
else:
dreapta = mijloc - 1
return raspuns

def main():
with open("tniain.txt", "r") as fisier_intrare, open("tniaout.txt", "w") as fisier_iesire:
n, m = map(int, fisier_intrare.readline().split())
inaltime = [0] + list(map(int, fisier_intrare.readline().split()))
sume_partiale = [0] * (n + 1)

for i in range(1, n + 1):
sume_partiale[i] = sume_partiale[i - 1] + inaltime[i]

q = int(fisier_intrare.readline())
for _ in range(q):
x_jos, y_jos, x_sus, y_sus = map(int, fisier_intrare.readline().split())
pozitie1 = cautare_binara(x_jos, x_sus, y_jos, inaltime)
pozitie2 = cautare_binara(x_jos, x_sus, y_sus, inaltime)

rezultat = (
sume_partiale[pozitie2]
- sume_partiale[pozitie1]
- (pozitie2 - pozitie1) * (y_jos - 1)
+ (x_sus - pozitie2) * (y_sus - y_jos + 1)
)

fisier_iesire.write(f"{rezultat}\n")

if __name__ == "__main__":
main()
</syntaxhighlight>

2434 - Tnia - Revision history

Andrada378: /* Rezolvare */

Andrada378 at 22:49, 2 January 2024