3704 - radar: Difference between revisions

Latest revision as of 20:13, 13 December 2023

Cerinta[edit]

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[edit]

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[edit]

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[edit]

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[edit]

intrare

3 3

2 1

4 2

-2 -1

1 3 4

iesire

Datele introduse corespund restrictiilor impuse.

3 1 2

Exemplul 2[edit]

intrare

4 5

3 2

5 3

- 3 - 2

2 4 5

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare[edit]

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

@@ 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 ==
-====== == Rezolvare == ======
+<syntaxhighlightlang="python3" line="1"
-<syntaxhighlight lang="python3" line="1"
-class Masina:
+ class Masina:
+    def __init__(self, moment, viteza):
+        self.moment = moment
+        self.viteza = viteza
-    def __init__(self, moment, pozitie):
+   def pozitii_la_momentul_t(t, masini):
+    pozitii = [(masina.viteza * masina.moment + masina.viteza * (t - masina.moment)) for masina in masini]
+    return pozitii
-        self.moment = moment
+ # 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
-        self.pozitie = pozitie
+ masini_detectate = [masina1, masina2, masina3]
-def cea_mai_apropiata_masina(t, masini_detectate):
+ 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)
-    distanta_minima = float('inf')
+ 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.")
-    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):
+</syntaxhighlight>
-            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>