1594 - Maraton

Cerința

Ajutați-l pe Costy să răspundă la cele Q întrebări.

Date de intrare

Fișierul maratonin.txt conține:

• pe prima linie numărul N, reprezentând numărul de maratoniști;
• pe următoarele N linii, câte 2 numere, Xi Yi, reprezentând distanța fată de linia de sosire și viteza fiecărui maratonist;
• pe următoarea linie, numărul Q reprezentând numărul de întrebări;
• pe următoarele Q linii se află câte un număr Qi reprezentând întrebarea i;

Date de ieșire

Fișierul de ieșire maratonout.txt conţine:

• Q linii, linia i reprezentând răspunsul la întrebarea i;

Restricții și precizări

• 1 <= N, Q, Qi, Xi <= 100 000
• 1 <= Yi <= 1000

Exemplul 1

maratonin.txt

5

100 4

12 3

101 5

20 1

44 7

4

20

12

7

21

maratonout.txt

Datele introduse corespund restricțiilor impuse.

3

2

2

4

Explicație

• La secunda 20 au trecut linia de sosire maratoniștii cu indicii 2, 4, 5.
• La secunda 12 au trecut linia de sosire maratoniștii cu indicii 2, 5.
• La secunda 7 au trecut linia de sosire maratoniștii cu indicii 2, 5.
• La secunda 21 au trecut linia de sosire maratoniștii cu indicii 2, 3, 4, 5.

Exemplul 2

maratonin.txt

6

100 4

12 3

101 5

20 1

44 7

200000 2

4

20

12

7

21

maratonout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 1594 - Maraton

def validare(n_maratonisti, lista_maratonisti, n_intrebari, lista_intrebari): # functia de validare

   if n_maratonisti > 100000 or n_intrebari > 100000:
       raise ValueError

   for distanta, viteza in lista_maratonisti:
       if distanta > 100000 or viteza > 1000:
           raise ValueError

   for intrebare in lista_intrebari:
       if intrebare > 100000:
           raise ValueError

   file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def maraton(lista_maratonisti, lista_intrebari): # functia de rezolvare

   rezultate_maraton = []
   for intrebare in lista_intrebari:
       nr_maratonisti_sositi = 0
       for distanta, viteza in lista_maratonisti:
           if distanta / viteza <= intrebare:
               nr_maratonisti_sositi += 1
       rezultate_maraton.append(nr_maratonisti_sositi)
   return rezultate_maraton

if __name__ == '__main__':

   file_in = open("maratonin.txt", "r")  # declararea fisierelor
   file_out = open("maratonout.txt", "w")  # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       nr_maratonisti = int(file_in.readline())
       maratonisti = []
       for _ in range(nr_maratonisti):
           x, y = map(int, file_in.readline().split())
           maratonisti.append((x, y))

       nr_intrebari = int(file_in.readline())
       intrebari = [int(file_in.readline()) for _ in range(nr_intrebari)]

       validare(nr_maratonisti, maratonisti, nr_intrebari, intrebari)  # apelul functiei de validare
       rezultate = maraton(maratonisti, intrebari)  # apelul functiei de rezolvare

       for rezultat in rezultate:
           file_out.write(str(rezultat) + "\n")

   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>