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

# 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")