3394 - Mere 1

Cerința

Scrieţi un program care să găsească numărul de mere culese de fiecare dintre cei K prieteni selectați de Cosmin.

Date de intrare

Fișierul de intrare merein.txt conține: - Pe prima linie, N T K, trei numere întregi reprezentând numărul de prieteni, numărul de zile în care se vor culege mere și numărul de întrebări ale lui Cosmin. - Pe următoarele T linii, câte două numere întregi, separate printr-un spațiu, Xi și Yi, reprezentând indicele prietenul ce va intra primul în grădina, respectiv numărul de mere ce vor fi culese în ziua Ti. - Pe ultima linie, K numere întregi, Qi, reprezentând indicii prietenilor lui Cosmin, pentru care se dorește aflarea numărului de mere culese.

Date de ieșire

Fișierul de ieșire mereout.txt va conţine K numere întregi, pe o singură linie, separate printr-un spațiu, reprezentând răspunsurile la cele K întrebări.

Restricții și precizări

• 1 ≤ Xi ≤ N ≤ 10.000.000
• 1 ≤ T ≤ 200.000
• 1 ≤ K ≤ 100.000
• 1 ≤ Yi ≤ 1.000.000
• Pentru teste în valoare de 30 puncte: 1 ≤ Xi ≤ N ≤ 100, 1 ≤ T ≤ 100, 1 ≤ K ≤ 100, 1 ≤ Yi ≤ 1.000
• Pentru teste în valoare de 50 puncte: 1 ≤ Xi ≤ N ≤ 200.000, 1 ≤ T ≤ 10.000, 1 ≤ K ≤ 10.000
• Pentru teste în valoare de 70 puncte: 1 ≤ Xi ≤ N ≤ 1.000.000, 1 ≤ T ≤ 100.000

Exemplul 1

merein.txt

5 3 4

1 2

3 5

2 7

2 4 1 2

mereout.txt

Datele introduse corespund restricțiilor impuse.

4 2 3 4

Explicație

5 persoane vor culege mere timp de 3 zile, astfel: În prima zi, vor culege 2 mere persoanele cu indicii 1 și 2 În a doua zi, vor culege 5 mere persoanele cu indicii 3, 4, 5, 1 și 2 În a treia zi, vor culege 7 mere persoanele cu indicii 2, 3, 4, 5, 1, 2, 3. Așadar, numărul de mere culese de fiecare persoană de la 1 la N este: 1 -> 3, 2 -> 4, 3 -> 3, 4 -> 2, 5 -> 2.

Exemplul 2

merein.txt

6 3 4

1 2

3 5

2 7

2 4 1 7

mereout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 3394 - Mere 1
def validare(n_validare, t_validare, k_validare, zile_validare, intrebari_validare, fisier):
    # Verificam daca datele de intrare respecta restrictiile impuse
    if (n_validare < 1 or n_validare > 10000000 or t_validare < 1 or t_validare > 200000 or
            k_validare < 1 or k_validare > 100000):
        raise ValueError
    for zi in zile_validare:
        if zi[0] < 1 or zi[0] > n_validare or zi[1] < 1 or zi[1] > 1000000:
            raise ValueError
    for intrebare in intrebari_validare:
        if intrebare < 1 or intrebare > n_validare:
            raise ValueError
    # Daca datele de intrare sunt valide, afisam un mesaj corespunzator
    fisier.write("Datele de intrare corespund restrictiilor impuse\n")


def mere_culese(n_culese, zile_culese, intrebari_culese, fisier):
    # Initializam un vector de zero-uri de lungimea numarului de prieteni plus unu
    mere = [0] * (n_culese + 1)
    # Parcurgem fiecare zi
    for zi in zile_culese:
        # Stabilim indicele prietenului care incepe culesul
        idx = zi[0]
        # Parcurgem numarul de mere culese in ziua respectiva
        for _ in range(zi[1]):
            # Adaugam un mar la prietenul cu indicele idx
            mere[idx] += 1
            idx += 1
            if idx > n_culese:
                idx = 1
    for intrebare in intrebari_culese:
        fisier.write(str(mere[intrebare]) + " ")


if __name__ == '__main__':
    fisier_intrare = open("merein.txt", "r")
    with open("mereout.txt", "w") as fisier_iesire:
        try:
            # Citim datele de intrare
            n, t, k = map(int, fisier_intrare.readline().split())
            zile = [list(map(int, fisier_intrare.readline().split())) for _ in range(t)]
            intrebari = list(map(int, fisier_intrare.readline().split()))
            # Validam datele de intrare
            validare(n, t, k, zile, intrebari, fisier_iesire)
            # Rezolvam problema
            mere_culese(n, zile, intrebari, fisier_iesire)
        # Tratam eventualele erori
        except ValueError:
            fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")
        except IndexError:
            fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")
    fisier_intrare.close()