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ă.

Cerința

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 2⁶³.

Exemplu

miere.in

miere.out

2
1

Explicație

În prima zi camionul colectează în întregime cantitatea de miere din primii 2 stupi. La finalul celei de-a doua zile, cantităţile de miere din fiecare stup sunt: 3 4 2 8. Camionul, care vine în a doua zi are capacitatea 6, deci el colectează mierea din primul stup dar nu mai poate colecta în întregime din al doilea, aşa că se întoarce şi pleacă.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Miere:

#include <stdio.h>
#define DIM 50010
long long S[DIM];
long long N, M, i, p, u, m, x;

int main(){
    FILE *f = fopen("miere.in","r");
    FILE *g = fopen("miere.out","w");
    fscanf(f,"%lld",&N);
    for (i=1, S[0] = 0;i<=N;i++){
        fscanf(f,"%lld",&x);
        S[i] = S[i-1] + x;
    }

    fscanf(f,"%lld",&M);
    for (i=0;i<M;i++) {
        fscanf(f,"%lld",&x);
        p = 1; u = N;
        while (p<=u) {
            m = (p+u)/2;
            if (S[m]+i*m <= x)
                p = m+1;
            else
                u = m-1;
        }
        if (S[u]<=x)
            fprintf(g,"%lld
",u);
        else
            fprintf(g,"%lld
",p);
    }
    
    fclose(f);
    fclose(g);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #734 Miere

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #734 Miere de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #734 Miere