3219 - Colina - Revision history

Cuceu Andrei at 17:53, 30 April 2023

2023-04-30T17:53:36Z

@@ Line 48: / Line 48: @@
 <syntaxhighlight lang="python" line="1" start="1">
-def can_build_house(q, h):
+import os
 </syntaxhighlight>

Vardai Erwin: /* Exemplu */

2023-04-22T18:54:32Z

Exemplu

← Older revision		Revision as of 18:54, 22 April 2023
Line 41:		Line 41:
	:DA 3		:DA 3
	:NU		:NU
			;Ieșire
			:Datele de intrare corespund restricțiilor impuse.

	==Rezolvare==		==Rezolvare==

Vardai Erwin: /* Date de ieșire */

2023-04-22T18:54:12Z

Date de ieșire

← Older revision		Revision as of 18:54, 22 April 2023
Line 13:		Line 13:

	==Date de ieșire==		==Date de ieșire==
			Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse."
	Fișierul de ieșire '''colina.out''' va conține '''M''' linii. Pe linia '''j (1 ≤ j ≤ M)''' va fi scris mesajul '''NU''', dacă nu este posibilă construirea unei case la altitudinea '''qj'''. În caz contrar, pe linia '''j''' va fi scris mesajul '''DA''', urmat de un spațiu, apoi de indicii '''i''' pentru care '''hi = qj''', separați de asemenea prin câte spațiu și scriși în ordine crescătoare.		Fișierul de ieșire '''colina.out''' va conține '''M''' linii. Pe linia '''j (1 ≤ j ≤ M)''' va fi scris mesajul '''NU''', dacă nu este posibilă construirea unei case la altitudinea '''qj'''. În caz contrar, pe linia '''j''' va fi scris mesajul '''DA''', urmat de un spațiu, apoi de indicii '''i''' pentru care '''hi = qj''', separați de asemenea prin câte spațiu și scriși în ordine crescătoare.
			În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

	==Restricții de precizări==		==Restricții de precizări==

Vardai Erwin: /* Date de intrare */

2023-04-22T18:53:54Z

Date de intrare

← Older revision		Revision as of 18:53, 22 April 2023
Line 9:		Line 9:

	==Date de intrare==		==Date de intrare==
	~~Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse."~~
	Fișierul de intrare '''colina.in''' conține pe prima linie două numere naturale '''N''' şi '''M''' ce reprezintă numărul de parcele şi respectiv numărul de cereri înregistrate. Pe a doua linie se găsesc '''N''' numere naturale '''h1, h2, …, hN''', reprezentând altitudinile parcelelor. Pe ultima linie se găsesc '''M''' numere naturale '''q1, q2, …, qM''', reprezentând altitudinile din cererile clienților. Numerele aflate pe aceeași linie sunt separate prin spații. ~~În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."~~		Fișierul de intrare '''colina.in''' conține pe prima linie două numere naturale '''N''' şi '''M''' ce reprezintă numărul de parcele şi respectiv numărul de cereri înregistrate. Pe a doua linie se găsesc '''N''' numere naturale '''h1, h2, …, hN''', reprezentând altitudinile parcelelor. Pe ultima linie se găsesc '''M''' numere naturale '''q1, q2, …, qM''', reprezentând altitudinile din cererile clienților. Numerele aflate pe aceeași linie sunt separate prin spații.

	==Date de ieșire==		==Date de ieșire==

Vardai Erwin: /* Date de intrare */

2023-04-22T18:53:35Z

Date de intrare

← Older revision		Revision as of 18:53, 22 April 2023
Line 9:		Line 9:

	==Date de intrare==		==Date de intrare==
			Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse."
	Fișierul de intrare '''colina.in''' conține pe prima linie două numere naturale '''N''' şi '''M''' ce reprezintă numărul de parcele şi respectiv numărul de cereri înregistrate. Pe a doua linie se găsesc '''N''' numere naturale '''h1, h2, …, hN''', reprezentând altitudinile parcelelor. Pe ultima linie se găsesc '''M''' numere naturale '''q1, q2, …, qM''', reprezentând altitudinile din cererile clienților. Numerele aflate pe aceeași linie sunt separate prin spații.		Fișierul de intrare '''colina.in''' conține pe prima linie două numere naturale '''N''' şi '''M''' ce reprezintă numărul de parcele şi respectiv numărul de cereri înregistrate. Pe a doua linie se găsesc '''N''' numere naturale '''h1, h2, …, hN''', reprezentând altitudinile parcelelor. Pe ultima linie se găsesc '''M''' numere naturale '''q1, q2, …, qM''', reprezentând altitudinile din cererile clienților. Numerele aflate pe aceeași linie sunt separate prin spații. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."


	==Date de ieșire==		==Date de ieșire==

Vardai Erwin: /* Enunt */

2023-03-27T12:33:24Z

Enunt

← Older revision		Revision as of 12:33, 27 March 2023
Line 1:		Line 1:
	==~~Enunt~~==		==Enunț==

	O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune '''1 × N''', fiind apoi împărțit în parcele de dimensiune '''1 x 1'''. Pe fiecare dintre cele '''N''' parcele de dimensiune '''1 × 1''' firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive de la '''1 la N''', altitudinile asociate acestor parcele vor fi în ordine strict crescătoare până la o anumită poziție, unde se atinge altitudinea maximă a acestui teren, iar pentru pozițiile următoare altitudinile sunt în ordine strict descrescătoare, fiind de partea cealaltă a vârfului colinei. Mai precis, dacă notăm în ordine cu '''h1''', '''h2''', …,''' hN''' altitudinile parcelelor, există un indice '''vf, 1 ≤ vf ≤ N''',astfel încât '''h1 < h2 <... < hvf-1 < hvf > hvf+1 > ... > hN'''.		O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune '''1 × N''', fiind apoi împărțit în parcele de dimensiune '''1 x 1'''. Pe fiecare dintre cele '''N''' parcele de dimensiune '''1 × 1''' firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive de la '''1 la N''', altitudinile asociate acestor parcele vor fi în ordine strict crescătoare până la o anumită poziție, unde se atinge altitudinea maximă a acestui teren, iar pentru pozițiile următoare altitudinile sunt în ordine strict descrescătoare, fiind de partea cealaltă a vârfului colinei. Mai precis, dacă notăm în ordine cu '''h1''', '''h2''', …,''' hN''' altitudinile parcelelor, există un indice '''vf, 1 ≤ vf ≤ N''',astfel încât '''h1 < h2 <... < hvf-1 < hvf > hvf+1 > ... > hN'''.
	Clienții au înregistrat deja cereri de construcție pentru M case. Fiecare dintre aceste cereri specifică însă o restricție mai ciudată, și anume faptul că doresc ca parcela de construcție să se afle exact la altitudinea '''qj (1 ≤ j ≤ M)'''.		Clienții au înregistrat deja cereri de construcție pentru M case. Fiecare dintre aceste cereri specifică însă o restricție mai ciudată, și anume faptul că doresc ca parcela de construcție să se afle exact la altitudinea '''qj (1 ≤ j ≤ M)'''.


	==Cerință==		==Cerință==

Cuceu Andrei: Pagină nouă: ==Enunt== O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune '''1 × N''', fiind apoi împărțit în parcele de dimensiune '''1 x 1'''. Pe fiecare dintre cele '''N''' parcele de dimensiune '''1 × 1''' firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive d...

2023-03-25T13:53:38Z

Pagină nouă: ==Enunt== O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune '''1 × N''', fiind apoi împărțit în parcele de dimensiune '''1 x 1'''. Pe fiecare dintre cele '''N''' parcele de dimensiune '''1 × 1''' firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive d...

New page

==Enunt==

O firmă de construcții imobiliare a achiziționat recent un teren dreptunghiular de forma unei fâșii de dimensiune '''1 × N''', fiind apoi împărțit în parcele de dimensiune '''1 x 1'''. Pe fiecare dintre cele '''N''' parcele de dimensiune '''1 × 1''' firma poate construi câte o casă, dacă există clienți interesați. Terenul este amplasat pe una dintre cele șapte coline ale unui oraș vestit. Astfel, dacă numerotăm parcelele cu numere consecutive de la '''1 la N''', altitudinile asociate acestor parcele vor fi în ordine strict crescătoare până la o anumită poziție, unde se atinge altitudinea maximă a acestui teren, iar pentru pozițiile următoare altitudinile sunt în ordine strict descrescătoare, fiind de partea cealaltă a vârfului colinei. Mai precis, dacă notăm în ordine cu '''h1''', '''h2''', …,''' hN''' altitudinile parcelelor, există un indice '''vf, 1 ≤ vf ≤ N''',astfel încât '''h1 < h2 <... < hvf-1 < hvf > hvf+1 > ... > hN'''.
Clienții au înregistrat deja cereri de construcție pentru M case. Fiecare dintre aceste cereri specifică însă o restricție mai ciudată, și anume faptul că doresc ca parcela de construcție să se afle exact la altitudinea '''qj (1 ≤ j ≤ M)'''.

==Cerință==

Scrieți un program care determină pentru fiecare cerere '''j (1 ≤ j ≤ M)''' dacă firma poate îndeplini restricția respectivă, mai exact dacă există măcar o parcelă '''i (1 ≤ i ≤ N)''' pentru care '''hi = qj'''.

==Date de intrare==

Fișierul de intrare '''colina.in''' conține pe prima linie două numere naturale '''N''' şi '''M''' ce reprezintă numărul de parcele şi respectiv numărul de cereri înregistrate. Pe a doua linie se găsesc '''N''' numere naturale '''h1, h2, …, hN''', reprezentând altitudinile parcelelor. Pe ultima linie se găsesc '''M''' numere naturale '''q1, q2, …, qM''', reprezentând altitudinile din cererile clienților. Numerele aflate pe aceeași linie sunt separate prin spații.

==Date de ieșire==

Fișierul de ieșire '''colina.out''' va conține '''M''' linii. Pe linia '''j (1 ≤ j ≤ M)''' va fi scris mesajul '''NU''', dacă nu este posibilă construirea unei case la altitudinea '''qj'''. În caz contrar, pe linia '''j''' va fi scris mesajul '''DA''', urmat de un spațiu, apoi de indicii '''i''' pentru care '''hi = qj''', separați de asemenea prin câte spațiu și scriși în ordine crescătoare.

==Restricții de precizări==

*'''1 ≤ N, M ≤ 100.000'''
*'''0 < hi, qj < 231''' pentru orice '''1 ≤ i ≤ N și 1 ≤ j ≤ M'''.
*Valorile '''qj''' sunt distincte (nu s-au acceptat cereri identice).
*Pentru teste în valoare de '''20''' puncte: '''N × M ≤ 100.000'''
*Pentru teste în valoare de '''40''' puncte: '''hmax ≤ 100.000''' unde '''hmax''' este altitudinea maximă a parcelelor.

==Exemplu==
===Exemplul 1===

; '''colina.in'''
:6 5
:1 5 9 7 2 1
:5 6 1 9 4

; '''colina.out'''
:DA 2
:NU
:DA 1 6
:DA 3
:NU

==Rezolvare==
===Rezolvare ver. 1===
<syntaxhighlight lang="python" line="1" start="1">

def can_build_house(q, h):
"""Verifică dacă există o parcelă cu altitudinea q pe terenul dat de altitudinile h."""
n = len(h)
lo, hi = 0, n-1

# Cautarea binara a altitudinii q
while lo <= hi:
mid = (lo + hi) // 2
if h[mid] == q:
return True, mid+1 # returnează True și indicele parcelii
elif h[mid] < q:
lo = mid + 1
else:
hi = mid - 1

# Dacă nu există o parcelă cu altitudinea q, returnează False
return False, None

if __name__ == "__main__":
# Citire date de intrare
with open("colina.in", "r") as fin:
n, m = map(int, fin.readline().split())
h = list(map(int, fin.readline().split()))
q = list(map(int, fin.readline().split()))

# Verificare restricții
assert 1 <= n <= 100_000, "n invalid"
assert 1 <= m <= 100_000, "m invalid"
assert len(h) == n, "dimensiunea listei h nu corespunde valorii lui n"
assert len(q) == m, "dimensiunea listei q nu corespunde valorii lui m"
assert all(0 < hi < 2**31 for hi in h), "altitudine invalidă în h"
assert all(0 < qi < 2**31 for qi in q), "altitudine invalidă în q"
assert len(set(q)) == m, "valorile din q nu sunt distincte"
assert h == sorted(h) or h == sorted(h, reverse=True), "lista h nu are forma specificată"

# Determinare răspunsuri
for qi in q:
can_build, indices = can_build_house(qi, h)
if can_build:
print("DA", *indices)
else:
print("NU")

</syntaxhighlight>