Se dă un şir cu n numere naturale nenule. Aflaţi câte secvenţe din şir au produsul mai mic decât un număr natural p dat.
Date de intrare
Fișierul de intrare produs2.in conține pe prima linie numerele n şi p, iar pe a doua linie n numere naturale nenule separate prin spații, reprezentând elementele şirului.
Date de ieșire
Fișierul de ieșire produs2.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir având produsul mai mic decât p.
Restricții și precizări
1 ≤ n ≤ 1.000.000
1 < p ≤ 2.000.000.000
numerele din şir vor fi mai mici decât 1.000
Exemplu
produs2.in
5 10
1 2 3 4 2
produs2.out
9
Explicație
Avem 9 secvenţe în şir cu produsul mai mic decât 10:
1 2 1,2 1,2,3 2,3 3 4 4,2 2
Răspunsuri la întrebare
Răspuns de
1
In timp ce citesti numerele cu un for tii minte intr-un vector produsul tuturor numerelor pana la momentul actual:
f>>x;
Prod[i]=Prod[i-1]*x;
Trebuie memorat Prod[0]=1; inainte
Dupa care cu doua for-uri imbricate: unul cu i de la 1 la n si al doilea cu j de la i+1 la n verifici practic produsul tuturor secventelor posibile astfel:
If(Prod[j]/Prod[i-1] < p)
f>>x;
Prod[i]=Prod[i-1]*x;
Trebuie memorat Prod[0]=1; inainte
Dupa care cu doua for-uri imbricate: unul cu i de la 1 la n si al doilea cu j de la i+1 la n verifici practic produsul tuturor secventelor posibile astfel:
If(Prod[j]/Prod[i-1] < p)
ionutg38:
In acest fel, produsul nu ajunge la valori imense
ok
Am incercat si eu o solutie dupa indicatiile autorului, dar cred ca gresesc undeva pt ca n-a mers decat pe testul din exemplu
#include <fstream>
using namespace std;
ifstream f("produs2.in");
ofstream g("produs2.out");
long long a[1000001];
long long n,p,i,j,x,s,prod,st,dr,k;
int main()
{
f>>n>>p;
for(i=1;i<=n;++i) f>>a[i];
st=1; dr=0;
prod=1;
while(prod*a[dr+1]<=p && dr+1<=n)
{
++dr;
prod*=a[dr];
}
s+=(dr-st+1)*(dr-st+2)/2;
while(dr<=n && st<=n)
{
prod/=a[st];
st++;
while(prod*a[dr+1]<=p && dr+1<=n)
{
prod*=a[dr+1];
dr++;
s+=dr-st+1;
}
}
g<<s;
return 0;
}
using namespace std;
ifstream f("produs2.in");
ofstream g("produs2.out");
long long a[1000001];
long long n,p,i,j,x,s,prod,st,dr,k;
int main()
{
f>>n>>p;
for(i=1;i<=n;++i) f>>a[i];
st=1; dr=0;
prod=1;
while(prod*a[dr+1]<=p && dr+1<=n)
{
++dr;
prod*=a[dr];
}
s+=(dr-st+1)*(dr-st+2)/2;
while(dr<=n && st<=n)
{
prod/=a[st];
st++;
while(prod*a[dr+1]<=p && dr+1<=n)
{
prod*=a[dr+1];
dr++;
s+=dr-st+1;
}
}
g<<s;
return 0;
}
Ce am facut acolo:
iau prima data si aflu prima secventa(care incepe de pe poz 1) maxima ca lungime care are produsul <=p. Numarul de secvente in total pe o secventa de lungime n este n*(n+1)/2,
deoarece sunt n secvente de lungime 1, sunt n-1 secvente de lungime 2 [...] e o singura secventa de lungime n. De la prima secventa gasita, tai pe rand cate un numar din stanga si dupa ce l-am taiat inaintez la dreapta cat timp produsul este <=p.
Pentru fiecare numar adaugat la dr apar lungimeaNoiiSecvente (dr-st+1) noi secvente (o secventa de lungime 1+o secventa de lungime 2+o secventa de lungime 3+ ...+ o secventa de lungime dr-st+1=dr-st+1 secvente) . si tot fac asta cat timp pot sa merg la dreapta mai departe. Asta spune si in indiciul de rezolvare, dar nu-ti da toate detaliile fiindca sunt sadici
Da, ai dreptate. E perfect asa. Multumesc!
Cu mare placere!
Alte întrebări interesante
Matematică,
9 ani în urmă
Limba română,
9 ani în urmă
Limba română,
9 ani în urmă
Biologie,
9 ani în urmă