3704 - radar

== Cerinta ==

Să se răspundă la Q interogări de forma: dându-se t, care este la momentul t cea mai apropiată mașină de radar dintre cele detectate până atunci (inclusiv cele detectate fix la momentul t)? Dacă există mai multe mașini dintre cele detectate până la momentul t pentru care distanța față de radar este minimă, puteți afișa oricare dintre ele.

== Date de intrare ==

Prima linie conține numerele N și Q, numărul de mașini, respectiv numărul de interogări. Urmează N linii, pe a i-a dintre acestea se citesc doua numere ti, respectiv vi cu semnificația de mai sus (pentru orice i = 1..N). Ultima linie conține Q numere întregi, corespunzând celor Q interogări (pentru fiecare interogare se citește un număr corespunzător lui t cu semnificația de mai sus).

== Date de iesire ==

Se va afișa o singură linie ce va conține Q numere separate prin câte un spațiu, corespunzând răspunsurilor la interogări. Pentru fiecare interogare t se afișează indicele celei mai apropiate mașini față de radar la momentul t, dintre cele detectate până la momentul t (mașinile sunt indexate începând de la 1 în ordinea în care au fost citite). Dacă până la momentul t nu s-a detectat nicio mașină se va afișa -1 pentru interogarea respectivă.

== Exemplul 1 ==

; intrare

; 3 3

; 2 1

; 4 2

; -2 -1

; 1 3 4

; iesire

; Datele introduse corespund restrictiilor impuse.

; 3 1 2

== Exemplul 2 ==

; intrare

; 4 5

; 3 2

; 5 3

; - 3 - 2

; 2 4 5

; iesire

; Datele de intrare nu corespund restrictiilor impuse.

== Rezolvare ==

<syntaxhighlight lang="python3" line="1"

class Masina:

    def __init__(self, moment, pozitie):

        self.moment = moment

        self.pozitie = pozitie

def cea_mai_apropiata_masina(t, masini_detectate):

    distanta_minima = float('inf')

    cea_mai_apropiata = None

    for masina in masini_detectate:

        distanta = abs(masina.pozitie - t)

        if distanta < distanta_minima or (distanta == distanta_minima and masina.moment < cea_mai_apropiata.moment):

            distanta_minima = distanta

            cea_mai_apropiata = masina

    return cea_mai_apropiata

# Exemplu de folosire

masini_detectate = [Masina(1, 5), Masina(2, 10), Masina(3, 3), Masina(4, 8)]

t = 4

rezultat = cea_mai_apropiata_masina(t, masini_detectate)

print(f"La momentul {t}, cea mai apropiată mașină detectată este la poziția {rezultat.pozitie}.")

</syntaxhighlight>