infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Noiembrie 19, 2007, 00:08:18


Titlul: 567 Flori2
Scris de: Adrian Diaconu din Noiembrie 19, 2007, 00:08:18
Aici puteţi discuta despre problema Flori2 (http://infoarena.ro/problema/flori2).

Titlul: Răspuns: 567 Flori2
Scris de: Casu-Pop Bogdan din Februarie 01, 2008, 17:24:46
 c tip de sortare sau ce functie de aflare a unghilui ati folosit k mie imi iese din timp cu mai multe variante ](*,) ?

Titlul: Răspuns: 567 Flori2
Scris de: Andrei Grigorean din Februarie 01, 2008, 21:24:03
Eu am sortat cu sort-ul din STL dupa functia atan2.

Titlul: Răspuns: 567 Flori2
Scris de: Casu-Pop Bogdan din Februarie 02, 2008, 20:44:00
am facut cum ai zis intra sub 1.4 sec dar da incorect.....m-am uitat si la solutie am facut ca acolo cu o precizie de 10^(-9) ....si altele...nush ce are de nu mere....poate un test cv mai complex daca poti sa imi dai k aglomerez degeaba evaluatoru  :-'

Titlul: Răspuns: 567 Flori2
Scris de: Andrei Grigorean din Februarie 02, 2008, 22:50:36
Eu am facut cu precizie de 10^-10

Titlul: Răspuns: 567 Flori2
Scris de: Dragos Oprica din Februarie 12, 2009, 18:30:02
ma ajuta cineva si pe mine?

eu icnerc sa fac altfel: pentru fiecare punct i aflu panta celorlalte puncte cu acesta - imi formez segmente cu un capat in punctul i si celalat in j si verifica apoi pentru fiecare punct i nr maxim de pante egale, dupa ce sortez

e gresit ceva in gandirea asta?

Titlul: Răspuns: 567 Flori2
Scris de: Andrei Grigorean din Februarie 12, 2009, 18:41:11
E buna ideea ta. M-am uitat peste codul tau si am gasit niste greseli:
Cod:
void check ()
{
    int i,nr;
    for (i=1; i<=m; ++i)
        // greseala 1: nu verifici daca i < m; alternativ ai putea sa faci forul doar pana cand i < m
        if (i < m && abs (a[i]-a[i+1])<0.00000001)
        {
            nr=1;
            // greseala 2: initial aveai la sfarsitul conditiei din while i < n
            while (abs (a[i]-a[i+1])<0.00000000001 && i<m)
            {
                ++i;
                ++nr;
            }
            if (nr>nmax)
                nmax=nr;
        }
}

Cu aceste doua modificari, vei obtine 100 de puncte.

Titlul: Răspuns: 567 Flori2
Scris de: Dragos Oprica din Februarie 13, 2009, 10:54:15
multumesc de ajutor :D
a iesit :yahoo:

Titlul: Răspuns: 567 Flori2
Scris de: Andrici Cezar din Aprilie 21, 2009, 22:12:25
Am facut un program care cauta in matrice elemente vecine

Cod:
#include<fstream.h>

long long a[1001],b[1001],x,y,i,l,n,k,lm,t,j;
int main()

{

ifstream f("flori2.in");
ofstream g("flori2.out");
f>>t;
for(i=1;i<=t;i++)
	{
	lm=0;
	f>>n;
	for(j=1;j<=n;j++)
	    f>>a[j]>>b[j];
	//in sus
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
	       if ((x-1==a[k])&&(y==b[k]))
			{
			l++;
			x=a[k];
			}
	   if (l>lm) lm=l;
	   }
	//in jos
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x+1==a[k])&&(y==b[k]))
			{
			l++;
			x=a[k];
			}
	   if (l>lm) lm=l;
	   }
	//diagonala stanga jos
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x+1==a[k])&&(y-1==b[k]))
			{
			l++;
			x=a[k];
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//diagonala stanga sus
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x-1==a[k])&&(y-1==a[k]))
			{
			l++;
			x=a[k];
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//diagonala dreapta jos
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x+1==a[k])&&(y+1==a[k]))
			{
			l++;
			x=a[k];
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//diagonala dreapta sus
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x-1==a[k])&&(y+1==a[k]))
			{
			l++;
			x=a[k];
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//dreapta
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x==a[k])&&(y-1==a[k]))
			{
			l++;
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	//stanga
	for(j=1;j<=n;j++)
	   {
	   x=a[j];y=b[j];
	   l=1;
	   for(k=1;k<=n;k++)
		if ((x==a[k])&&(y+1==a[k]))
			{
			l++;
			y=b[k];
			}
	   if (l>lm) lm=l;
	   }
	g<<lm;
	g<<'\n';
	}
f.close();
g.close();
return 0;
}
e cel mai banal mod de a cauta si nici nu iese din timp, adica pentru 11 teste si cate 1000 de flori pentru fiecare test face in total 88.008.000 de operatii deci e foarte putin se incadreaza in timp, dar zicetimi ce e gresit :oops: va rog :)

[...]

Am gasit greseala

Titlul: Răspuns: 567 Flori2
Scris de: Tirca Bogdan din Decembrie 25, 2009, 01:52:21
Puteti sa-mi lasati si mie niste teste? Ca pe ce am incercat eu imi merge algoritmul dar se incadreaza la limita. Si cand se incadreaza imi da WA(ca sa intre in timp folosesc stable_sort din stl )
Problema e ca fac N (N+NlogN+N).Dar pentru a lua pe rand punctele mie imi mai trebuie un vector identic cu cel de puncte numai ca fac swap(aux[0],aux) pentru a putea sorta apoi...
Cod:
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
				aux[j]=a[j];
			swap(aux[0],aux[i]);
			sort(aux+1,aux+n+1,cmp);//cu stable_sort intra-n timp
                        .... mai jos fiind parcurgerea liniara
Am incercat si cu memcpy si degeaba :(
Iar la comparare fac produsul mezilor cu extremii ca sa nu pierd precizie...
Cod:
inline ll calc(p x,p y)
{
	return (ll)(x.second-aux[0].second)*(y.first-aux[0].first);
}
inline int cmp(p x, p y)
{
	return calc(x,y)<calc(y,x);
}


L.E. Dupa mai multe modificari dar nu prea esentiale am descoperit greseala :)) Citeam n si daca era 1 sau 2 afisam 1 respectiv 2 si treceam la testul urmator fara sa mai citesc elementele (1 respectiv 2)  ](*,) ](*,) ](*,)

Titlul: Răspuns: 567 Flori2
Scris de: alexandru din Ianuarie 06, 2010, 17:14:18
Imi poateti spune ce este gresit la urmatoarea sursa  :fighting:. Am dat zeci si zeci de teste si imi afiseaza corect ( am verificat cu o sursa destul de simplu de scris  folosind un map< double, int > :) )
Cod:
inline ll get( pr p1, pr p2 ) //pr pair< int, int >
{
    return (ll) ( (ll)(p1.first-p0.first)*(ll)(p2.second-p0.second) );
}
inline bool cmp( pr p1, pr p2 )
{
    return get( p1, p2 ) < get( p2, p1 );
}
inline int max( int x, int y )
{
    return x^( (x^y) & -(x<y) );
}
int main()
{pr v[Nmax], v2[Nmax];
int n, t, i, j, k, maxim, length;
    freopen("flori2.in", "rt", stdin );
    freopen("flori2.out", "wt", stdout );
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d", &n );
        for( i=0; i < n; ++i )
            scanf("%d%d", &v[i].first, &v[i].second );
        maxim=0;
        for( i=0; i < n; ++i )
        {p0=v[i]; length=0;
            for( j=0; j < n; ++j )
                if( i != j )
                    v2[length]=v[j], ++length;
            stable_sort( v2, v2+length, cmp );
            for( j=0; j < length; j=k )
            {
                for( k=j+1; k < length && get( v2[k], v2[j]) == get( v2[j], v2[k] ); ++k );
                maxim=max( maxim, k-j );
            }
        }
        printf("%d\n", maxim+1 );
    }
    return 0;
}

Titlul: Răspuns: 567 Flori2
Scris de: Farcasanu Alexandru Ciprian din Martie 05, 2010, 10:35:38
Nu uitati cazul cand N = 1 :thumbup:

Titlul: Răspuns: 567 Flori2
Scris de: Oncescu Costin din Mai 29, 2012, 10:57:42
Imi poate spune si mie cineva ce am gresit,am facut cu ideea lui Dragos Oprica si testele pe care le-am dat mi-au mers.

Cod:
scanf("%d",&n);
for(i=1;i<=n;i++)
{
	scanf("%d",&x[i]);
	scanf("%d",&y[i]);
}
maxi1=0;
for(i=1;i<=n;i++)
{
	for(j=1;j<=n;j++)
		if(i!=j)
		{
			if(x[j]!=x[i]) m[j]=(double)(y[j]-y[i])/(x[j]-x[i]);
			else m[j]=-10000002;
		}
	m[i]=-10000004;
	sort(m+1,m+n+1);
	nr=1;
	maxi=0;
	for(j=2;j<=n;j++)
	{
		if(abs(m[j]-m[j-1])<=0.0000001) nr++;
		else
		{
			if(nr>maxi) maxi=nr;
			nr=1;
		}
	}
	if(nr>maxi) maxi=nr;
	if(maxi>maxi1) maxi1=maxi;
}
printf("%d\n",maxi1+1);

Editat de admin: foloseste tagul "code" cand postezi surse.

Titlul: Răspuns: 567 Flori2
Scris de: Bejenariu Ionut Daniel din Martie 23, 2016, 11:38:50
Cam ce complexitate ar trebui sa am?

Eu am O(T*N*N*logN)

Titlul: Răspuns: 567 Flori2
Scris de: Mihai Calancea din Martie 23, 2016, 11:45:38
Ar trebui să fie ok complexitatea asta, tu probabil iei TLE fiindcă apelezi de prea multe ori atan2(), care e cam înceată. Încearcă să precalculezi o singură dată atan2()-urile într-un array, iar apoi să folosești acest array pentru sortare și pentru comparațiile ulterioare.

Poți să ajungi și la $O(T * N * N)$ dacă pui pantele în ceva hash-like ca să le contorizezi frecvențele (spre exemplu un unordered_map). Eu aș încerca ambele variante.


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines