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