Editing 3704 - radar

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

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

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

====== == Restrictii si precizari == ======

====== *<code>1 ≤ N ≤ 100.000</code> ======

====== <code>*1 ≤ Q ≤ 300.000</code> ======

====== <code>*-1.000.000.000 ≤ vi</code> <code>, ti</code> <code>≤ 1.000.000.000</code>, <code>vi ≠ 0</code> pentru orice <code>i = 1..N</code> ======

====== <code>*-1.000.000.000 ≤ t ≤ 1.000.000.000</code> pentru orice interogare ======

====== *pentru teste în valoare de 32 de puncte <code>1 ≤ N ≤ 1000</code> și <code>1 ≤ Q ≤ 3000</code>. ======

====== == Exemplul 1 == ======
<nowiki>;</nowiki> intrare

<nowiki>;</nowiki> 3 3

<nowiki>;</nowiki> 2 1

<nowiki>;</nowiki> 4 2

<nowiki>;</nowiki> -2 -1

<nowiki>;</nowiki> 1 3 4

<nowiki>;</nowiki> iesire 

<nowiki>;</nowiki> Datele introduse corespund restrictiilor impuse.

<nowiki>;</nowiki> 3 1 2

====== == Exemplul 2 == ======
<nowiki>;</nowiki> intrare

<nowiki>;</nowiki> 4 5

<nowiki>;</nowiki> 3 2

<nowiki>;</nowiki> 5 3

<nowiki>;</nowiki> - 3 - 2

<nowiki>;</nowiki> 2 4 5

<nowiki>;</nowiki> iesire

<nowiki>;</nowiki> 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

<nowiki>#</nowiki> 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}.")

<nowiki></syntaxhighlight></nowiki>