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>