405 Secv7

[•DITzoneC]

Aici puteţi discuta despre problema Secv7.

[•greco]

Cred ca daca bagati testul

1 5 5 5 5 5 5 1

o sa busiti niste surse.

[•DITzoneC]

Am bagat un test asemanator si am reevaluat sursele. (Stiam de mai demult ca trebuie bagat un astfel de test, dar am tot amanat )

[•toni2007]

imi buseste pe testul 1... e ceva mai special?

Gata: nu mai e nevoie... am aflat. cine e interesat sa-mi dea un pm

[•alex_mircescu]

un test ... relativ naspa:

4
1 4 3 2

raspuns

7
1 3

[•scipianus]

Ce are asa special testul 1  ?

1   4ms   372kb   Secventa nu obtine minim!   0

[•toni2007]

Eu cand luam wa pe testul #1, greseam cand ma uitam daca maximul e in a doua secventa, pentru ca nu verificam daca e in capete.

[•scipianus]

Ce are asa special testul 1   ?

1   4ms   372kb   Secventa nu obtine minim!   0

Gata,mi-a iesit si testul ala  
Problema era ca numerotasem de la 0 la n-1 cand am facut-o pt campion(de 100 - si pe infoarena 70 cu WA pe testul 1),iar acum cand sa o modific cu de la 1 la n sa-mi vina mai usor sa gasesc greseala am vazut ca undeva facusem o prostie la niste indici

[•ctlin04]

Mda, iau incorect la problema asta desi merge bine pe testul de pe site si pe niste teste allcatuita de mine, imi puteti sugera ceva?
Apropo pe testul
4
1 4 3 2
nu ar trebui sa fie
7
1 4
 

[•Mitza444]

Cum as putea sa optimizez urmatoarea varianta de rezolvare(iau 60p).Functioneaza corect da pica la timp.Am considerat pe rand ultimele n-i secvente si am facut maximul din pe cele 3 cazuri daca max e in secv 1 ,2 sau 3.Imi puteti da o idee de optimizare a cautarii?
Codul:

Cod:

#include<cstdio>
using namespace std;
int n,v[30001];
int caut(int x,int y){
	int max=-10001,i;
	for(i=x;i<=y;i++)
		if(v[i]>max)
			max=v[i];
	return max;
}
int main(){
	int max=-10001,p,i,smin=0x3f3f3f3f,p1,p2,aux;
	freopen("secv.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]),v[i]>max ? max=v[i],p=i:0;
	fclose(stdin);
	for(i=1;i<=n-2;i++){
		if(p>=n-i+1){
			aux=max+v[n-i]+caut(1,n-i-1);
			if(aux<smin)
				smin=aux,p2=n-i,p1=n-i-1;
		}
		else if(p==n-i){
			aux=max+v[1]+v[n];
			if(aux<smin)
				smin=aux,p1=1,p2=n-1;
		}
		else if(p<n-i){
			aux=max+v[n-i]+caut(n-i+1,n);
			if(aux<smin)
				smin=aux,p2=n-i,p1=n-i-1;
		}
	}
	freopen("secv.out","w",stdout);
	printf("%d\n%d %d",smin,p1,p2);
	fclose(stdout);
	return 0;
}

[•mihnea_info]