ZigZag Topcoder

[•yrar]

Am luat problema ZigZag de pe topcoder, http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493 , am facut (bine, zic eu) algoritmul dar nu merge bine afisarea.

Cod:

#include <fstream>
#define k 300

using namespace std;

int l[k], a[k], p[k], n, lmax, val=-1;
// p[i] = valoarea precedenta de a[i]

ifstream f("sec.in");
ofstream g("sec.out");

int sc(int a, int b)
{
	if(b-a>0) return 0;
	return 1;
}
// sc returneaza 0 sau 1, in functie de diferenta (pozitiva sau negativa)

int afis(int poz)
{   
	if(poz==1) return 0;
	if(!lmax)
	{	if(val!=-1)
			while(l[poz] != lmax || ( sc(p[poz], a[poz]) == sc(a[poz], a[val]) )) poz--;
		g << a[poz] << " ";
		lmax--;
		val = poz;
		afis(poz-1);
	}
}
//afisul, care afiseaza dupa pozitie

int main()
{
	int i, j, x, y, poz;
	f >> n;
	for(i=1; i<=n; i++) f >> a[i];
	l[1] = 1;
	l[2] = 2;
	p[1] = 0; 
	p[2] = a[1];
	for(i=3; i<=n; i++)
	{	l[i] = 1;
		for(j=1; j<i; j++)
		{   
			x = sc(a[j], a[i]);
		        y = sc(p[j], a[j]);
			if(l[j]+1>l[i] && x!=y)
			{	l[i] = l[j]+1;
				p[i] = a[j];
				if(lmax<l[i]) lmax=l[i], poz=i;
			}
		}
	}
	//afisarea
	afis(poz);
	f.close();
	g.close();
	return 0;
}

ma poate ajuta cineva cu o idee ceva la afis? nu inteleg de ce nu merge... algoritmul zic ca ii bun

[•SpiderMan]

Cred ca aici e problema, la functia afisare:(ceea ce trebuie e pus in BOLD)
while((l[poz] != lmax) || ( sc(p[poz], a[poz]) == sc(a[poz], a[val]) )) poz--;

[•toni2007]

La TopCoder nu se folosesc fisiere. Ar fi fost mult mai simplu daca ne dadeai direct clasa respectiva, ca sa putem testa in arena.

[•yrar]

Nu fac problema sa o trimit la topcoder.. am pus ca si cum mi s-ar fi dat in fisier si fac eu niste teste..
^^ la fel, nu merge..
are altcineva vreo idee? sau o alta idee de rezolvare

[•SpiderMan]

Dar ce nu merge bine?

[•yrar]

afisul. nu afiseaza nimic

[•SpiderMan]

Sigur Returnurile din programul de afisare sunt bune? Fa afisare cu o functie VOID.

[•alexandru92]

Problema se poate rezolva mult mai usor decat cum ai facut-o. Retine in dif[ i ] diferetna dintre v[ i ]-v[i-1]. Restul ar trebuie sa fie evident

[•yrar]

Problema se poate rezolva mult mai usor decat cum ai facut-o. Retine in dif[ i ] diferetna dintre v[ i ]-v[i-1]. Restul ar trebuie sa fie evident

da acum iese, mersi