Imprimă pagina

Titlul: Spioni
Scris de: Vidrean Mihai din Iulie 25, 2011, 12:04:52

Buna am si eu o problema de pe .campion si nush de ce imi pica la ultimu test la timpu de executie.... ](*,).....chiar nu stiu ce sa mai fac.......Ma puteti ajuta? http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=573 (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=573)

Cod:

#include<cstdio>
using namespace std;
int x[1001],y[1001],s[1001];
int main(){
	int n,xa=0,ya=0,k,i,j,gasit=0;
	char c;
	FILE * pFile;
	pFile=fopen("spioni.in","r");
	fscanf(pFile,"%d",&n);
	for(i=1;i<=n;i++){
		fscanf(pFile,"%d",&x[i]);
		fscanf(pFile,"%d",&y[i]);
	}
	for(j=1;j<=n;j++){
			if((x[j]==xa && y[j]==ya) || (x[j]==xa-1 && y[j]==ya-1) || (x[j]==xa && y[j]==ya-1) || (x[j]==xa+1 && y[j]==ya-1) || (x[j]==xa-1 && y[j]==ya) || (x[j]==xa+1 && y[j]==ya) || (x[j]==xa-1 && y[j]==ya+1) || (x[j]==xa && y[j]==ya+1) || (x[j]==xa+1 && y[j]==ya+1)){
				s[j]=1;gasit=1;}
		}
	fscanf(pFile,"%d",&k);
	for(i=1;i<=k+1;i++){
		fscanf(pFile,"%c",&c);
		switch(c){
		case 'N':ya++;break;
		case 'S':ya--;break;
		case 'V':xa--;break;
		case 'E':xa++;break;
		}
		for(j=1;j<=n;j++){
			if((x[j]==xa && y[j]==ya) || (x[j]==xa-1 && y[j]==ya-1) || (x[j]==xa && y[j]==ya-1) || (x[j]==xa+1 && y[j]==ya-1) || (x[j]==xa-1 && y[j]==ya) || (x[j]==xa+1 && y[j]==ya) || (x[j]==xa-1 && y[j]==ya+1) || (x[j]==xa && y[j]==ya+1) || (x[j]==xa+1 && y[j]==ya+1)){
				s[j]=1;gasit=1;}
		}
	}
	pFile=fopen("spioni.out","w");
	if(!gasit)fprintf(pFile,"-1");
	else {
	for(i=1;i<=n;i++){
		if(s[i])fprintf(pFile,"%d\n",i);
	}
	}
	return 0;
}

Titlul: Răspuns: Spioni
Scris de: FMI Ciprian Olariu din Iulie 25, 2011, 19:56:37

N-am apucat inca sa ma uit atent pe problema si pe sursa ta,dar din ce am zarit asa "dubios" in sursa, te-as sfatui sa incerci pe moment sa refaci portiunea unde ai folosit switch,intrucat contine 4 break-uri care in general sunt mari consumatoare de timp [-X Incearca cu if :-k

Titlul: Răspuns: Spioni
Scris de: Vidrean Mihai din Iulie 25, 2011, 20:42:37

Am incercat si cu if poate ca e un pic mai rapid,dar tot nu este de ajuns ca sa treaca testul :aha:

Titlul: Răspuns: Spioni
Scris de: Vidrean Mihai din Iulie 27, 2011, 10:52:53

Ma mai puteti ajuta cu ceva idei?? chiar nu stiu ce sa-i mai fac sa treaca la timpul de executie............ #-o

Titlul: Răspuns: Spioni
Scris de: Mihai Calancea din Iulie 27, 2011, 11:00:32

Pai ai O( n * k ), e prea mult. Fa o cautare binara or something, nu mai verifica toti spionii la fiecare pas.

Titlul: Răspuns: Spioni
Scris de: Vidrean Mihai din Iulie 27, 2011, 11:04:24

ok,o sa vad si ideea ta desi e cam greu pt. ca trebuie sa verific de fiecare data ca sa nu pierd solutii...dar am auzit ca este o modalitate de citire mai rapida ceva cu parsare,dar nu stiu cum sa fac:|

Titlul: Răspuns: Spioni
Scris de: Vidrean Mihai din Iulie 27, 2011, 12:54:20

Am incercat sa mai pun niste conditii ca sa nu verifice toti spionii,dar nu merge:| cred ca trebuie facut ceva la citire ca sa merga mai repede,dar nu stiu ce mai aveti ceva idei??ca la ultimul test trebuie citit 1000 de spioni + 100000 caractere

Titlul: Răspuns: Spioni
Scris de: Popescu Silviu din Iulie 30, 2011, 13:49:39

Da poti sa reduci complexitatea la O(n+k), daca ti o matrice [0..N-1][0..N-1] si in fiecare celula ti 0 daca nu e nici un spion acolo sau numarul spionului daca e. Apoi la fiecare pas verifici daca in vre-o casuta alaturata , sau chiar pe casuta curenta e vre-un spion si adaugi daca e cazul :D

Sper ca te ajuta

Da, n-am vazut dimensiunile, merge daca faci cautare binara :D

Titlul: Răspuns: Spioni
Scris de: Vidrean Mihai din August 09, 2011, 14:11:04

Buna am refacut problema.De data asta am facut os tructura de date in care am retinut toti spionii si dupaia am retinut toate punctele in care poate fi un spion si apoi vectorul acela care are toate punctele unde poate fi un spion l-am sortat si dupaia fac o cautare binara ca sa intersectez cei 2 vectori,dar nu stiu de ce cautarea mea binara nu functioneaza corect........ ](*,)
Ma puteti ajuta??

Cod:

#include<cstdio>
#include<algorithm>
using namespace std;
int m,i;
char c[100001];
struct spion{
	int x,y;
}a[1001],b[800001];
inline bool compare( const spion& p1, const spion& p2 )
{
       return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
}

int caut (int s, int d)
{
    if(s>d)
        return -1;
    else
        {
            m =(s+d)/2;
            if (a[i].x==b[m].x){
				if(a[i].y==b[m].y)return 1;
				if(a[i].y<b[i].y)return caut(s,m-1);
				if(a[i].y>b[i].y)return caut(m+1,d);
			}
            if (a[i].x<b[m].x){
                return caut(s,m-1);}
            if(a[i].x>b[m].x){
                return caut(m+1,d);}
        }
}
int main(){
	int n,k,s=-1,j,xa=0,ya=0,gasit=0;
	int dx[]={-1,0,1,-1,0,1,-1,0,1}, dy[]={-1,-1,-1,0,0,0,1,1,1};
	FILE * pFile;
	pFile=fopen("spioni.in","r");
	fscanf(pFile,"%d",&n);
	for(i=0;i<n;i++){
		fscanf(pFile,"%d%d",&a[i].x,&a[i].y);
	}
	fscanf(pFile,"%d",&k);
	fscanf(pFile,"%s",&c);
	for(j=0;j<9;j++){
			s++;
			b[s].x=xa+dx[j];
			b[s].y=ya+dy[j];
		}
	for(i=0;i<k;i++){
		if(c[i]=='N')ya++;
		if(c[i]=='S')ya--;
		if(c[i]=='V')xa--;
		if(c[i]=='E')xa++;
		for(j=0;j<9;j++){
			s++;
			b[s].x=xa+dx[j];
			b[s].y=ya+dy[j];
		}
	}
	sort( b, b+s+1, compare );
	pFile=fopen("spioni.out","w");
	for(i=0;i<n;i++){
		if(caut(1,s)==1){fprintf(pFile,"%d\n",i+1);gasit=1;}
	}
	if(!gasit)fprintf(pFile,"-1");
	
	return 0;
}

Titlul: Răspuns: Spioni
Scris de: Popescu Silviu din August 16, 2011, 13:58:51

Ok , mi se pare foarte dubios cum faci cautarea binara, in primul rand functiei tale trebuie sa-i dai un spion pe care sa-l cauti.
Antetul trebuie sa fie ceva de genu :

Cod:

int caut(int s,int d,spion spy);

si ca sa nu mai pui atatea if-uri poti sa folosesti functia de comparare pe care ai facut-o :D

sper ca te ajuta

infoarena

infoarena - concursuri, probleme, evaluator, articole => .CAMPION => Subiect creat de: Vidrean Mihai din Iulie 25, 2011, 12:04:52