3219 - Colina

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

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. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

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

Ieșire

Datele de intrare corespund restricțiilor impuse.

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>