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.