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

== Restrictii si precizari ==

*1 ≤ N ≤ 100.000
*1 ≤ Q ≤ 300.000
*-1.000.000.000 ≤ vi , ti ≤ 1.000.000.000, vi ≠ 0 pentru orice i = 1..N
*-1.000.000.000 ≤ t ≤ 1.000.000.000 pentru orice interogare
*pentru teste în valoare de 32 de puncte 1 ≤ N ≤ 1000 și 1 ≤ Q ≤ 3000.

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

<syntaxhighlightlang="python3" line="1"

 class Masina:
    def __init__(self, moment, viteza):
        self.moment = moment
        self.viteza = viteza

   def pozitii_la_momentul_t(t, masini):
    pozitii = [(masina.viteza * masina.moment + masina.viteza * (t - masina.moment)) for masina in masini]
    return pozitii

 # Exemplu de folosire
 masina1 = Masina(1, 60)  # Mașina 1 detectată la t=1, v=60 km/h
 masina2 = Masina(2, 80)  # Mașina 2 detectată la t=2, v=80 km/h
 masina3 = Masina(3, 100)  # Mașina 3 detectată la t=3, v=100 km/h

 masini_detectate = [masina1, masina2, masina3]

 moment_t = 2  # Momentul de timp la care vrem să știm pozițiile mașinilor
 pozitii_la_t = pozitii_la_momentul_t(moment_t, masini_detectate)

 for i, pozitie in enumerate(pozitii_la_t, start=1):
    print(f"Mașina {i} este la poziția {pozitie} km la momentul {moment_t} ore.")




</syntaxhighlight>