3704 - radar: Difference between revisions

Revision as of 19:46, 13 December 2023

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>

@@ Line 1: / Line 1: @@
-====== == Cerinta == ======
+== 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 == ======
+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.
-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 intrare ==
-====== == Date de iesire == ======
+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).
-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 == ======
+== Date de iesire ==
-====== *<code>1 ≤ N ≤ 100.000</code> ======
+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ă.
-====== <code>*1 ≤ Q ≤ 300.000</code> ======
+== Restrictii si precizari ==
-====== <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> ======
+*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.
-====== <code>*-1.000.000.000 ≤ t ≤ 1.000.000.000</code> pentru orice interogare ======
+== Exemplul 1 ==
-====== *pentru teste în valoare de 32 de puncte <code>1 ≤ N ≤ 1000</code> și <code>1 ≤ Q ≤ 3000</code>. ======
+; intrare
+:3 3
-====== == Exemplul 1 == ======
+:2 1
-<nowiki>;</nowiki> intrare
-<nowiki>;</nowiki> 3 3
+:4 2
-<nowiki>;</nowiki> 2 1
+:-2 -1
-<nowiki>;</nowiki> 4 2
+:1 3 4
-<nowiki>;</nowiki> -2 -1
+; iesire
-<nowiki>;</nowiki> 1 3 4
+: Datele introduse corespund restrictiilor impuse.
-<nowiki>;</nowiki> iesire
+:3 1 2
-<nowiki>;</nowiki> Datele introduse corespund restrictiilor impuse.
+ == Exemplul 2 ==
-<nowiki>;</nowiki> 3 1 2
+; intrare
-====== == Exemplul 2 == ======
+:4 5
-<nowiki>;</nowiki> intrare
-<nowiki>;</nowiki> 4 5
+:3 2
-<nowiki>;</nowiki> 3 2
+:5 3
-<nowiki>;</nowiki> 5 3
+:- 3 - 2
-<nowiki>;</nowiki> - 3 - 2
+: 2 4 5
-<nowiki>;</nowiki> 2 4 5
+; iesire
-<nowiki>;</nowiki> iesire
+: Datele de intrare nu corespund restrictiilor impuse.
-<nowiki>;</nowiki> Datele de intrare nu corespund restrictiilor impuse.
+ == Rezolvare ==
+<syntaxhighlightlang="python3" line="1"
-====== == Rezolvare == ======
-<syntaxhighlight lang="python3" line="1"
 class Masina:
+    def __init__(self, moment, pozitie):
-    def __init__(self, moment, pozitie):
+        self.moment = moment
+        self.pozitie = pozitie
-        self.moment = moment
-        self.pozitie = pozitie
 def cea_mai_apropiata_masina(t, masini_detectate):
+    distanta_minima = float('inf')
+    cea_mai_apropiata = None
-    distanta_minima = float('inf')
+    for masina in masini_detectate:
+        distanta = abs(masina.pozitie - t)
-    cea_mai_apropiata = None
+        if distanta < distanta_minima or (distanta == distanta_minima and masina.moment < cea_mai_apropiata.moment):
+            distanta_minima = distanta
-    for masina in masini_detectate:
+            cea_mai_apropiata = masina
-        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
+# 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>
+</syntaxhighlight>