Imprimă pagina - Problema mobile

Titlul: Problema mobile
Scris de: Vidrean Mihai din Ianuarie 04, 2012, 11:42:17

Buna am incercat sa rezolv aceasta problema :http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=606 (http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=606) .Ideea mea a fost sa fac o simulare pas cu pas si sa vad unde se intalnesc mobilele,dar am observat ca ideea nu este optima.Ma puteti ajuta cu idee de rezolvare care sa se si incadreze in timp??(nu prea mai am alte idei cum s-ar putea rezolva:D)

Titlul: RÄƒspuns: Problema mobile
Scris de: FMI Ciprian Olariu din Ianuarie 04, 2012, 13:58:54

Tot cu simulare se face,numai ca nu pas cu pas.Incearca sa faci simularea cu pasi de tipul "ma opresc cu pasul curent(pentru a verifica eventuale intersectii) atunci cand unul din mobile a ajuns la o margine , apoi ii fac trecerea pe cealalta linie/coloana si schimb sensul,verificand si aici o eventuala intersectie (apoi continui la fel,pana termin)". Sper ca ai inteles ce vreau sa zic :thumbup:

Titlul: RÄƒspuns: Problema mobile
Scris de: Vidrean Mihai din Ianuarie 04, 2012, 20:57:02

Nu am inteles foarte bine :? Deci tu zici sa fac un "for" care merge pe linii si la fiecare linie sa fac o verificare daca se poate intalni cu coloana.Imi poti descrie un pic mai detaliat ideea ta si cum pot face verificare aceea ?? :D

Titlul: RÄƒspuns: Problema mobile
Scris de: FMI Ciprian Olariu din Ianuarie 05, 2012, 10:00:43

Citat din mesajul lui: Vidrean Mihai din Ianuarie 04, 2012, 20:57:02

Deci voi avea mai degraba un while (cat timp mobilele n-au ajuns amandoua la sfarsit).La un pas curent as avea ceva de genul :
1.gasesc minimul dintre distanta primul mobil pana la capatul liniei pe care se afla si distanta celui de-al doilea mobil pana la capatul coloanei pe care se afla. (ai grija la sensul de mers,ca se schimba)
2.(sa presupunem ca minimul e pentru mobilul care merge pe linie)
3.duc primul mobil la capatul liniei si mut si al doilea mobil pe coloana lui cu acelasi numar de pasi facuti de primul mobil
4.gasesc intersectia dintre linia si coloana pe care s-au miscat cele doua mobile
5.daca intersectia se afla intre pozitia de start si de final (din pasul curent) a ambelor mobile,atunci a fost o intersectie si o retin
6.mut primul mobil acum pe linia urmatoare(deci se mai face un pas,si voi muta un pas si al doilea mobil),schimbandu-i bineinteles si sensul
7.verific daca nu cumva dupa pasul asta facut s-au intersectat mobilele (verific aici daca se afla pe aceeasi pozitie)
Si continui tot asa,pana ambele mobile si-au terminat traseul.

Titlul: RÄƒspuns: Problema mobile
Scris de: Vidrean Mihai din Ianuarie 05, 2012, 17:28:32

Am incercat sa fac cu ai spus tu insa nu stiu de ce nu merge....pe exemplu imi da: 1 si 1 , 2 si 2 , 3 si 3 in loc de: 1 si 1 , 3 si 4 ](*,)
nu stiu ce am gresit :-k ca am incercat sa urmez pasii pe care mi-ai dat......daca ai timp uitate te rog peste cod poate observi ce nu e bine

Cod:

#include<cstdio>
using namespace std;
int min(int a,int b){
	if(a<b)
		return a;
	return b;
}
int main(){
	int n,m,m1=1,n1=1,m2=1,n2=1,min1,min2,p,n3,m3,nr=0,mat[10000][2],i;
	FILE * pFile;
	pFile=fopen("mobile.in","r");
	fscanf(pFile,"%d%d",&m,&n);
	while(m2!=m || n2!=n){
		if(m1%2==0)
			min1=n1-1;
		else
			min1=n-n1;
		if(n2%2==0)
			min2=m2-1;
		else
			min2=m-m2;
		p=min(min1,min2);
		n3=n1;
		m3=m2;
		if(m1%2==0)
			n1=n1-p;
		else
			n1=n1+p;
		if(n2%2==0)
			m2=m2-p;
		else
			m2=m2+p;
		if(m1%2==0 && n2%2==0){
			if((m2<=m1 && m1<=m3) && (n2<=n3 && n1<=n2)){
				nr++;
				mat[nr][0]=m1;
				mat[nr][1]=n2;
			}
		}
		if(m1%2!=0 && n2%2!=0){
			if((m2>=m1 && m1>=m3) && (n2>=n3 && n1>=n2)){
				nr++;
				mat[nr][0]=m1;
				mat[nr][1]=n2;
			}
		}
		if(m1%2!=0 && n2%2==0){
			if((m2<=m1 && m1<=m3) && (n2>=n3 && n1>=n2)){
				nr++;
				mat[nr][0]=m1;
				mat[nr][1]=n2;
			}
		}
		if(m1%2==0 && n2%2!=0){
			if((m2>=m1 && m1>=m3) && (n2<=n3 && n1<=n2)){
				nr++;
				mat[nr][0]=m1;
				mat[nr][1]=n2;
			}
		}
		if(n1==n || n1==1){
			m1++;m2++;
		}
		else if(m2==m || m2==1){
				n2++;n1++;}
		if(m1==m2 && n1==n2){
			nr++;
			mat[nr][0]=m1;
			mat[nr][1]=n2;
		}
	}
	pFile=fopen("mobile.out","w");
	fprintf(pFile,"%d\n",nr);
	for(i=1;i<=nr;i++)
		fprintf(pFile,"%d %d\n",mat[i][0],mat[i][1]);
	return 0;
}

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Vidrean Mihai din Ianuarie 04, 2012, 11:42:17