Editing 3219 - Colina

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