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

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

1. 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()

</syntaxhighlight>