821 Expresie

[•stef2n]

Aici puteti discuta despre problema Expresie.

[•Procopliuc]

Pentru cei care iau incorect la testele 7 si 8:
raspunsul depaseste int, declarati long long

[•noru]

iau 60 de puncte, imi da gresit si la primul test 
daca bag manual testele imi afiseaza bine si, bineinteles, se incadreaza si in timp 
care ar fi problema?
http://infoarena.ro/job_detail/541993

[•skull]

Nu-ti putem vedea sursa si oricum nu cred ca are cineva timp sa faca debugging. Ar fi mai bine daca ne-ai spune ideea ta de rezolvare.

[•david_rauca]

Ma poate ajuta cnv cu idee pentru testele 7-8...am pus long long si tot nu le iau ...

[•Oancea.Catalin]

Atentie cand inmultirile sunt una dupa alta! Nu pot vedea acele teste si nu iti pot vedea nici sursa.

[•noru]

testul 1 este
5
12
5
1
3
5

metoda la care m-am gandit este sa fac maximul a 3 elemente citite consecutiv si inca 2 maximuri a cate 2 elemente citite consecutiv, respectiv le retin indicii.
pt exemplul de sus ar fi max1=12*5*1 (maximul a 3 elemente) si max2=12*5 si max3=3*5( celelalte 2 maximuri).
intreb care e mai mare (max1 sau max2+max3)
pun intr-un S pe cel mai mare, si fac, cu ajutorul indicilor retinuti mai sus, elementele inmultite ale numarului mai mare egale cu 0 in vectorul in care am citit toate numerele.
daca initial este v: 12 5 1 3 5, dupa va fi v: 0 0 1 0 0
apoi fac suma.
nu prea ma  pricep sa explic, sunt si in clasa a 9a (am inceput informatica de anul asta) asa ca ...

EDIT:

Cod:

#include<fstream.h>
int a[1001];
int main()
{
	int n,x,i,k1,k2,k3,k4,k5,k6,k7;
	long long max1=0,max2=0,max3=0,s=0;
	ifstream f("expresie.in");
	ofstream g("expresie.out");
	f>>n;
	k1=k2=k3=k4=k5=k6=k7=0;
	for (i=1;i<=n;i++)
		f>>a[i];
	for (i=2;i<=n-1;i++)
	{
		if (a[i-1]*a[i]*a[i+1]>max1)
		{
			max1=a[i-1]*a[i]*a[i+1];
			k1=i-1;
			k2=i;
			k3=i+1;
		}
		if (a[i]>max2)
		{
			max3=max2;
			max2=a[i];
			k5=k4;
			k4=i;
		}
		else if (a[i]>max3)
		{
			max3=a[i];
			k5=i;
		}
	}
	if (a[k4]*a[k4+1]>a[k4-1]*a[k4]) {max2=a[k4]*a[k4+1];k6=k4+1;}
	else {max2=a[k4]*a[k4-1];k6=k4-1;}
	if (a[k5]*a[k5+1]>a[k5-1]*a[k5]) {max3=a[k5]*a[k5+1];k7=k5+1;}
	else {max3=a[k5]*a[k5-1];k7=k5-1;}
	if (max2+max3>max1) 
	{
		a[k4]=0;
		a[k5]=0;
		a[k6]=0;
		a[k7]=0;
		s+=max2+max3;
	}
	else
	{
		a[k1]=0;
		a[k2]=0;
		a[k3]=0;
		s+=max1;
	}
	for (i=1;i<=n;i++)
		s+=a[i];
	g<<s;
	f.close();
	g.close();
	return 0;
}

EDIT II:
am vazut unde buseam:D eu aflam cele mai mari 2 numere nu produsul cel mai mare a 2 numere consecutive ... mda, mersi oricum 80p, gresit testul 7 si 8 unde cred ca trebuie facut cu suma si produs de numere mari (in vector).

[•skull]

Nu e nevoie de numere mari. Suma intra in long long.

[•noru]

trebuia sa declar vectorul cu long long 
eh, sunt incepator
mersi

[•maritim]

Imi poate explica si mie cineva de ce trebuia declarat vectorul long long, deoarece 1...10000 intra si in int!

[•Smaug-]

Doar sa clarific de ce multora le merge dupa ce declara vectorul long long:

Cod:

int A[MAXN];
long long product = A[i]*A[i-1]*A[i-2];

Daca vectorul A contine valori indeajuns de mari inmultirea va face overflow si valoarea alocata lui product va fi eronata. Corect scris ar fi;

Cod:

int A[MAXN];
long long product = (long long)A[i]*(long long)A[i-1]*(long long)A[i-2];

[•Eby7]

Are cineva idee de ce imi da gresit la testul 9?

[•danalex97]

Poti sa rezolvi problema http://infoarena.ro/problema/evaluare la care ai teste disponibile si apoi poti reveni la problema asta. Asa sigur iti vei da seama unde gresesti.  

Daca nici asa nu te descurci vezi ca problema s-a dat la oji deci ar trebui sa fie testele pe http://olimpiada.info.

[•vendetta]

Poti sa rezolvi problema http://infoarena.ro/problema/evaluare la care ai teste disponibile si apoi poti reveni la problema asta. Asa sigur iti vei da seama unde gresesti.  

Care e legatura dintre cele 2 probleme?

[•danalex97]

Pardon  . Am citit la repezeala si , cum am vazut ca e oji , aveam impresia ca e evaluare de expresie fara paranteze. Desi nu are nici cea mai vaga legatura.  

[•georgerapeanu]

Salut.Ma poate ajuta cineva?
Am 2 surse.una in care am declarat totul cu int, si una in care am declarat totul cu long long
Cea care e cu int da 80 de puncte,cu incorect pe 7 si 8.
Dar cea cu long long imi da 0 la toate,chiar daca e exeact aceasi sursa.
Am facut o programare dinamica unde M[j]=suma maxima pana in elementul j avand folosite doar i inmultiri
Cod:
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f=fopen("expresie.in","r");
FILE *g=fopen("expresie.out","w");
long long N,i,j;
long long V[1005];
long long M[3][1005];
int main()
{
    fscanf(f,"%lld",&N);
    for(i=1;i<=N;i++)
    {
        fscanf(f,"%lld",&V);
        M[0]=M[0][i-1]+V;
        M[1]=max(M[1][i-1]+V,M[0][i-2]+V[i-1]*V);
        M[2]=max(M[2][i-1]+V,max(M[1][i-2]+V[i-1]*V,M[0][i-3]+V[i-2]*V[i-1]*V));
    }
    fprintf(g,"%lld",M[2][N]);
    fclose(f);
    fclose(g);
    return 0;
}

[•AlexandruValeanu]

M[0][i-3] sau V[i-2] s-ar putea sa nu existe si accesezi zone din memorie intr-un mod relativ dubios (cel mai probabil intri peste alt vector si-l suprascrii).