0734 - Miere

Cerința

La marginea unei păduri sunt N stupi aşezaţi în linie. Ei au asociate numere de ordine de la 1 la N, în ordinea în care apar. Fiind sezonul florii de salcâm, albinele colectează foarte repede mierea. La finalul fiecărei zile, din satul aflat în apropiere vine un apicultor la volanul unui camion pentru a o recolta. Capacităţile camioanelor pot fi diferite. Procesul de strângere a mierii decurge astfel: camionul pleacă din dreptul stupului 1 şi încarcă întreaga cantitate de miere din acesta, apoi trece la stupul 2 şi procedează la fel şi aşa mai departe. Dacă odată ajuns la un stup camionul nu poate colecta întreaga cantitate de miere din acel stup, acesta întrerupe acţiunea de colectare şi se întoarce în sat. În ziua următoare, albinele din stupii de unde s-a recoltat refac cantitatea de miere din ziua anterioara. În plus, în fiecare stup cantitatea de miere creşte cu un kilogram faţă de ziua anterioară. Dându-se N, numărul de stupi, cantitatea de miere existentă în fiecare la finalul primei zile, numărul M de zile în care se face colectarea mierii şi capacitatea camionului care trece în fiecare zi, se cere numărul de stupi din care se recoltează miere în fiecare dintre cele M zile.

Date de intrare

Fişierul miere.in are următoarea structură:

• pe prima linie N, numărul de stupi;
• pe linia a 2-a, N numere naturale, separate prin câte un spaţiu. Numerele reprezintă cantitatea de miere din cei N stupi la finalul primei zile, în ordinea de la 1 la N;
• pe linia a 3-a M, numărul de camioane;
• pe linia a 4-a, M numere naturale separate prin câte un spaţiu. Numerele reprezintă capacităţile camioanelor, în ordinea în care sosesc.

Date de ieșire

Fişierul miere.out conţine M numere naturale, fiecare pe câte o linie. Pe linia i se află numărul de stupi din care colectează miere camionul i.

Restricții și precizări

• cantităţile de miere produse de fiecare stup şi capacităţile camioanelor sunt precizate în kilograme.
• 1 <= N, M <=50000
• e posibil ca un camion sa nu poată colecta miere din niciun stup sau sa poată colecta mierea din toţi stupii
• suma cantităţilor de miere din toţi stupii din fiecare moment şi capacităţile camioanelor sunt numere naturale strict pozitive şi mai mici decât 263.

Exemplu 1

Intrare

4
2 3 1 7
2
5 6

Iesire

2
1

Rezolvare

<syntaxhighlight lang="python" line> def main():

   # Citirea datelor de intrare
   with open("miere.in", "r") as f:
       N = int(f.readline().strip())
       cantitati_initiale = list(map(int, f.readline().strip().split()))
       M = int(f.readline().strip())
       capacitati_camioane = list(map(int, f.readline().strip().split()))

   assert 1 <= N <= 50000, "N trebuie să fie între 1 și 50000"
   assert 1 <= M <= 50000, "M trebuie să fie între 1 și 50000"
   assert all(1 <= x < 2**63 for x in cantitati_initiale), "Cantitățile trebuie să fie între 1 și 2^63 - 1"
   assert all(1 <= x < 2**63 for x in capacitati_camioane), "Capacitățile trebuie să fie între 1 și 2^63 - 1"

   # Copierea cantităților inițiale de miere
   cantitati = cantitati_initiale[:]

   # Lista pentru a păstra numărul de stupi din care colectează fiecare camion
   rezultat = []

   # Simularea colectării mierii pentru fiecare camion
   for capacitate in capacitati_camioane:
       stupi_colectati = 0
       for i in range(N):
           if cantitati[i] > 0 and capacitate >= cantitati[i]:
               capacitate -= cantitati[i]
               cantitati[i] = 0
               stupi_colectati += 1
           else:
               cantitati[i] -= capacitate
               capacitate = 0
               if cantitati[i] > 0:
                   break
       rezultat.append(stupi_colectati)
       # Actualizarea cantității de miere din stupi
       for i in range(N):
           if cantitati[i] == 0:
               cantitati[i] = cantitati_initiale[i] + 1

   # Afișarea rezultatului
   with open("miere.out", "w") as f:
       for res in rezultat:
           f.write(f"{res}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>