Editing 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">

import os

def validare_intrare(N: int, M: int, altitudini: list[int], cereri: list[int]):
    if N < 1 or N > 100000:
        print("Valoarea lui N nu respecta restrictiile problemei!")
        return False
    if M < 1 or M > 100000:
        print("Valoarea lui M nu respecta restrictiile problemei!")
        return False
    if len(altitudini) != N or len(cereri) != M:
        print("Numarul de altitudini si cereri nu corespund cu N si M!")
        return False
    for h in altitudini:
        if h < 1 or h > 2**31-1:
            print("Valoarea unei altitudini nu respecta restrictiile problemei!")
            return False
    for q in cereri:
        if q < 1 or q > 2**31-1:
            print("Valoarea unei cereri nu respecta restrictiile problemei!")
            return False
    if len(set(cereri)) != M:
        print("Cererile trebuie sa fie distincte!")
        return False
    return True


if __name__ == '__main__':
    # Validare fisier intrare
    if not os.access("colina.in", os.R_OK):
        print("Fisierul de intrare nu exista sau nu are permisiuni de citire!")
        exit()

    # Citire fisier intrare
    with open("colina.in", 'r') as fin:
        N, M = map(int, fin.readline().split())
        altitudini = list(map(int, fin.readline().split()))
        cereri = list(map(int, fin.readline().split()))

    # Validare date de intrare
    if not validare_intrare(N, M, altitudini, cereri):
        exit()

    # Validare fisier iesire
    if not os.access("colina.out", os.W_OK):
        print("Fisierul de iesire nu poate fi creat sau nu are permisiuni de scriere!")
        exit()

    # Rezolvare problema
    with open("colina.out", 'w') as fout:
        for q in cereri:
            pozitii = [str(i+1) for i in range(N) if altitudini[i] == q]
            if pozitii:
                fout.write("DA " + ' '.join(pozitii) + '\n')
            else:
                fout.write("NU\n")


</syntaxhighlight>

==Expliacatii== 
Acest cod citește datele de intrare din fișierul "colina.in", verifică validitatea lor și afișează un mesaj corespunzător. Dacă datele sunt valide, el calculează indicele "vf" și creează un dicționar în care cheile sunt altitudinile "qj" specificate în cererile clienților, iar valorile sunt o listă cu toate parcelele cu acea altitudine.

Pentru fiecare cerere a clientului, codul verifică dacă altitudinea cererii există în dicționar și, în caz afirmativ, afișează "DA" și toate parcelele cu acea altitudine. În caz contrar, afișează "NU".

Pentru a verifica validitatea datelor de intrare, codul verifică dacă dimensiunea fâșiei de teren și numărul de cereri sunt în intervalul specificat în enunț, dacă altitudinile sunt în ordine crescătoare până la vârful colinei și apoi în ordine descrescătoare, dacă valorile qj sunt distincte și dacă valorile altitudinilor sunt mai mici decât 2^31.